Constraint satisfaction for planning and scheduling problems

The areas of planning and scheduling (from the Artificial Intelligence point of view) have seen important advances thanks to application of constraint satisfaction techniques. Currently, many important real-world problems require efficient constraint handling for planning, scheduling and resource allocation to competing goal activities over time in the presence of complex state-dependent constraints. Solutions to these problems require integration of resource allocation and plan synthesis capabilities. Hence to manage such complex problems planning, scheduling and constraint satisfaction must be interrelated. This special issue on Constraint Satisfaction for Planning and Scheduling Problems compiles a selection of papers dealing with various aspects of applying constraint satisfaction techniques in planning and scheduling. The core of submitted papers was formed by the extended versions of papers presented at COPLAS??2009: ICAPS 2009 Workshop on Constraint Satisfaction Techniques for Planning and Scheduling Problems. This issue presents novel advances on planning, scheduling, constraint programming/constraint satisfaction problems (CSPs) and many other common areas that exist among them. On the whole, this issue mainly focus on managing complex problems where planning, scheduling, constraint satisfaction and search must be combined and/or interrelated, which entails an enormous potential for practical applications and future research.     

Introduction to planning, scheduling and constraint satisfaction

Planning, scheduling and constraint satisfaction are important areas in artificial intelligence (AI). Many real-world problems are known as AI planning and scheduling problems, where resources must be allocated so as to optimize overall performance objectives. Therefore, solving these problems requires an adequate mixture of planning, scheduling and resource allocation to competing goal activities over time in the presence of complex state-dependent constraints. Constraint satisfaction plays also an important role to solve real-life problems, so that integrated techniques that manage planning and scheduling with constraint satisfaction remains necessary. This special issue on Planning, Scheduling and Constraint Satisfaction compiles a selection of papers of CAEPIA’2007 workshop on Planning, Scheduling and Constraint Satisfaction and COPLAS’2007: CP/ICAPS 2007 Joint Workshop on Constraint Satisfaction Techniques for Planning and Scheduling Problems. This issue presents novel advances on planning, scheduling, constraint programming/constraint satisfaction problems (CSPs) and many other common areas that exist among them. On the whole, this issue mainly focus on managing complex problems where planning, scheduling, constraint satisfaction and search must be combined and/or interrelated, which entails an enormous potential for practical applications and future research. Furthermore, this issue also includes a complete survey about constraint satisfaction, planning, scheduling and integration among these areas.     

Localized event-based reasoning for multiagent domain1

This paper presents the GEM concurrency model and GEMPLAN, a multiagent planner based on this model. Unlike standard state-based AI representations, GEM is unique in its explicit emphasis on events and domain structure. In particular, a world domain is modeled as a set of regions composed of interrelated events. Event-based temporal-logic constraints are then associated with each region to delimit legal domain behavior. The GEMPLAN planner directly reflects this emphasis on domain structure and constraints. It can be viewed as a general-purpose constraint satisfaction facility which constructs a network of interrelated events (a “plan”) that is subdivided into regions (“subplans”), satisfies all applicable regional constraints, and also achieves some stated goal. GEMPLAN extends and generalizes previous planning architectures in the range of constraint forms it handles and in the flexibility of its constraint satisfaction search strategy. One critical aspect of our work has been an emphasis on localized reasoning—techniques that make explicit use of domain structure. For example, GEM localizes the applicability of domain constraints and imposes additional “locality constraints” on the basis of domain structure. Together, constraint localization and locality constraints provide semantic information that can be used to alleviate several aspects of the frame problem for multiagent domains. The GEMPLAN planner reflects the use of locality by subdividing its constraint satisfaction search space into regional planning search spaces. Utilizing constraint and property localization, GEMPLAN can pinpoint and rectify interactions among these regional search spaces, thus reducing the burden of “interaction analysis” ubiquitous to most planning systems. Because GEMPLAN is specifically geared towards parallel, multiagent domains, we believe that its natural application areas will include scheduling and other forms of organizational coordination.     

炼铸轧集成计划与调度组批模型及算法

为提高热装批量计划的调度可行性,构建一种集成批量计划类型及部分调度约束的批量计划约束满足模型,并采用显性基因的约束遗传算法进行优化求解。在优化过程中,采用一种以提高批量计划的调度可行性的基于邻域连通的快速判定方法,同时利用判定返回的信息构建显性基因指导优化过程。最后利用实际生产数据进行测试,结果表明,所提出的模型和算法能够提高热装率和批量计划调度的可行性,并且算法的执行效率可满足实际应用的要求。     

A constraint programming formulation for planning: from plan scheduling to plan generation

Planning research is recently concerned with the resolution of more realistic problems as evidenced in the many works and new extensions to the Planning Domain Definition Language (PDDL) to better approximate real problems. Researchers’ works to push planning algorithms and capture more complex domains share an essential ingredient, namely the incorporation of new types of constraints. Adding constraints seems to be the way of approximating real problems: these constraints represent the duration of tasks, temporal and resource constraints, deadlines, soft constraints, etc., i.e. features that have been traditionally associated to the area of scheduling. This desired expressiveness can be achieved by augmenting the planning reasoning capabilities, at the cost of slightly deviating the planning process from its traditional implicit purpose, that is finding the causal structure of the plan. However, the resolution of complex domains with a great variety of different constraints may involve as much planning effort as scheduling effort (and perhaps the latter being more prominent in many problems). For this reason, in this paper we present a general approach to model those problems under a constraint programming formulation which allows us to represent and handle a wide range of constraints. Our work is based on the original model of , an optimal temporal planner, and it extends the ’s formulation to deal with more expressive constraints. We will show that our general formulation can be used for planning and/or scheduling, from scheduling a given complete plan to generating the whole plan from scratch. However, our contribution is not a new planner but a constraint programming formulation for representing highly-constrained planning + scheduling problems.     

Block assembly planning in shipbuilding using case-based reasoning

A process planning system using case-based reasoning (CBR) is developed for block assembly in shipbuilding. A block assembly planning problem is modeled as a constraint satisfaction problem where the precedence relations between operations are considered constraints. In order to find similar cases, we propose two similarity coefficients for finding similar cases and for finding similar relations. Due to the limited number of operation types, the process planning system first matches the parts of the problem and those of the case-based on their roles in the assembly, and then it matches the relations related to the matched part–pairs. The parts involved in more operations are considered first. The process planning system is applied to simple examples for verification and comparison. An interface system is also developed for extracting information from CAD model, for preparing data for process planning, and for visually verifying the assembly sequence.     

An improved constraint satisfaction adaptive neural network for job-shop scheduling

This paper presents an improved constraint satisfaction adaptive neural network for job-shop scheduling problems. The neural network is constructed based on the constraint conditions of a job-shop scheduling problem. Its structure and neuron connections can change adaptively according to the real-time constraint satisfaction situations that arise during the solving process. Several heuristics are also integrated within the neural network to enhance its convergence, accelerate its convergence, and improve the quality of the solutions produced. An experimental study based on a set of benchmark job-shop scheduling problems shows that the improved constraint satisfaction adaptive neural network outperforms the original constraint satisfaction adaptive neural network in terms of computational time and the quality of schedules it produces. The neural network approach is also experimentally validated to outperform three classical heuristic algorithms that are widely used as the basis of many state-of-the-art scheduling systems. Hence, it may also be used to construct advanced job-shop scheduling systems.     

A Survey of Automated Timetabling

The timetabling problem consists in scheduling a sequence of lectures between teachers and students in a prefixed period of time (typically a week), satisfying a set of constraints of various types. A large number of variants of the timetabling problem have been proposed in the literature, which differ from each other based on the type of institution involved (university or school) and the type of constraints. This problem, that has been traditionally considered in the operational research field, has recently been tackled with techniques belonging also to Artificial Intelligence (e.g., genetic algorithms, tabu search, and constraint satisfaction). In this paper, we survey the various formulations of the problem, and the techniques and algorithms used for its solution.     

Experimental Analysis of Numeric and Symbolic Constraint Satisfaction Techniques for Temporal Reasoning

Many temporal applications like planning and scheduling can be viewed as special cases of the numeric and symbolic temporal constraint satisfaction problem. Thus we have developed a temporal model, TemPro, based on the interval Algebra, to express such applications in term of qualitative and quantitative temporal constraints. TemPro extends the interval algebra relations of Allen to handle numeric information. To solve a constraint satisfaction problem, different approaches have been developed. These approaches generally use constraint propagation to simplify the original problem and backtracking to directly search for possible solutions. The constraint propagation can also be used during the backtracking to improve the performance of the search. The objective of this paper is to assess different policies for finding if a TemPro network is consistent. The main question we want to answer here is how much constraint propagation is useful for finding a single solution for a TemPro constraint graph. For this purpose, we have experimented by randomly generating large consistent networks for which either arc and/or path consistency algorithms (AC-3, AC-7 and PC-2) were applied. The main result of this study is an optimal policy combining these algorithms either at the symbolic (Allen relation propagation) or at the numerical level.     

Discrete optimisation based on the combined use of reinforcement and constraint satisfaction schemes

A new approach is presented for finding near-optimal solutions to discrete optimisation problems that is based on the cooperation of two modules: an optimisation module and a constraint satisfaction module. The optimisation module must be able to search the problem state space through an iterative process of sampling and evaluating the generated samples. To evaluate a generated point, first a constraint satisfaction module is employed to map that point to another one satisfying the problem constraints, and then the cost of the new point is used as the evaluation of the original one. The scheme that we have adopted for testing the effectiveness of the method uses a reinforcement learning algorithm in the optimisation module and a general deterministic constraint satisfaction algorithm in the constraint satisfaction module. Experiments using this scheme for the solution of two optimisation problems indicate that the proposed approach is very effective in providing feasible solutions of acceptable quality.     

Resolving inconsistencies and redundancies in declarative process models

Declarative process models define the behaviour of business processes as a set of constraints. Declarative process discovery aims at inferring such constraints from event logs. Existing discovery techniques verify the satisfaction of candidate constraints over the log, but completely neglect their interactions. As a result, the inferred constraints can be mutually contradicting and their interplay may lead to an inconsistent process model that does not accept any trace. In such a case, the output turns out to be unusable for enactment, simulation or verification purposes. In addition, the discovered model contains, in general, redundancies that are due to complex interactions of several constraints and that cannot be cured using existing pruning approaches. We address these problems by proposing a technique that automatically resolves conflicts within the discovered models and is more powerful than existing pruning techniques to eliminate redundancies. First, we formally define the problems of constraint redundancy and conflict resolution. Second, we introduce techniques based on the notion of automata-product monoid, which guarantees the consistency of the discovered models and, at the same time, keeps the most interesting constraints in the pruned set. The level of interestingness is dictated by user-specified prioritisation criteria. We evaluate the devised techniques on a set of real-world event logs.     

Reasoning with Numeric and Symbolic Time Information

Representing and reasoning about time is fundamental in many applications of Artificial Intelligence as well as of other disciplines in computer science, such as scheduling, planning, computational linguistics, database design and molecular biology. The development of a domain-independent temporal reasoning system is then practically important. An important issue when designing such systems is the efficient handling of qualitative and metric time information. We have developed a temporal model, TemPro, based on the Allen interval algebra, to express and manage such information in terms of qualitative and quantitative temporal constraints. TemPro translates an application involving temporal information into a Constraint Satisfaction Problem (CSP). Constraint satisfaction techniques are then used to manage the different time information by solving the CSP. In order for the system to deal with real time applications or those applications where it is impossible or impractical to solve these problems completely, we have studied different methods capable of trading search time for solution quality when solving the temporal CSP. These methods are exact and approximation algorithms based respectively on constraint satisfaction techniques and local search. Experimental tests were performed on randomly generated temporal constraint problems as well as on scheduling problems in order to compare and evaluate the performance of the different methods we propose. The results demonstrate the efficiency of the MCRW approximation method to deal with under constrained and middle constrained problems while Tabu Search and SDRW are the methods of choice for over constrained problems.     

A CSP model for simple non-reversible and parallel repair plans

This work presents a constraint satisfaction problem (CSP) model for the planning and scheduling of disassembly and assembly tasks when repairing or substituting faulty parts. The problem involves not only the ordering of assembly and disassembly tasks, but also the selection of them from a set of alternatives. The goal of the plan is the minimization of the total repairing time, and the model considers, apart from the durations and resources used for the assembly and disassembly tasks, the necessary delays due to the change of configuration in the machines, and to the transportation of intermediate subassemblies between different machines. The problem considers that sub-assemblies that do not contain the faulty part are nor further disassembled, but allows non-reversible and parallel repair plans. The set of all feasible repair plans are represented by an extended And/Or graph. This extended representation embodies all of the constraints of the problem, such as temporal and resource constraints and those related to the selection of tasks for obtaining a correct plan.     

Interactive scheduling as a constraint satisfiability problem

A constraint satisfiability problem consists of a set of variables, their associated domains (i.e., the set of values the variable can take) and a set of constraints on these variables. A solution to the CSP is an instantiation (or labeling) of all the variables which does not violate any of the constraints. Since constraint satisfiability problems are, in general, NP-complete, it is of interest to compare the effectiveness and efficiency of heuristic algorithms as applied, in particular, to our application. Our research effort attempts to determine which algorithms perform best in solving the student scheduling problem (SSP) and under what conditions. We also investigate the probabilistic techniques of Nudel for finding a near-optimal instantiation order for search algorithms, and develop our own modifications which can yield a significant improvement in efficiency for the SSP. Experimental results have been collected and are reported here. Our system was developed for and used at Bar-Ilan University during the registration period, being available for students to construct their timetables.     

Modular design of a hybrid genetic algorithm for a flexible job–shop scheduling problem

The aim of the job–shop scheduling problem is to optimize the task planning in an industrial plant satisfying time and technological constraints. The existing algorithmic and mathematical methods for solving this problem usually have high computational complexities making them intractable. Flexible job–shop scheduling becomes even more complex, since it allows one to assign each operation to a resource from a set of suitable ones. Alternative heuristic methods are only able to satisfy part of the constraints applicable to the problem. Moreover, these solutions usually offer little flexibility to adapt them to new requirements. This paper describes research within heuristic methods that combines genetic algorithms with repair heuristics. Firstly, it uses a genetic algorithm to provide a non-optimal solution for the problem, which does not satisfy all its constraints. Then, it applies repair heuristics to refine this solution. There are different types of heuristics, which correspond to the different types of constraints. A heuristic is intended to evaluate and slightly modify a solution that violates a constraint in a way that avoids or mitigates such violation. This approach improves the adaptability of the solution to a problem, as some changes can be addressed just modifying the considered chromosome or heuristics. The proposed solution has been tested in order to analyse its level of constraint satisfaction and its makespan, which are two of the main parameters considered in these types of problems. The paper discusses this experimentation showing the improvements over existing methods.     

A unified framework for consistency check

Constraint Satisfaction Problem (CSP) involves finding values for variables to satisfy a set of constraints. Consistency check is the key technique in solving this class of problems. Past research has developed many algorithms for such a purpose, e.g., node consistency, are consistency, generalized node and arc consistency, specific methods for checking specific constraints, etc. In this article, an attempt is made to unify these algorithms into a common framework. This framework consists of two parts. the first part is a generic consistency check algorithm, which allows and encourages each individual constraint to be checked by its specific consistency methods. Such an approach provides a direct way of practical implementation of the CSP model for real problem-solving. the second part is a general schema for describing the handling of each type of constraint. the schema characterizes various issues of constraint handling in constraint satisfaction, and provides a common language for expressing, discussing, and exchanging constraint handling techniques. © 1995 John Wiley & Sons, Inc.     

Stabilization of nonlinear systems with state and control constraints using Lyapunov-based predictive control

This work considers the problem of stabilization of nonlinear systems subject to state and control constraints, for cases where the state constraints need to be enforced at all times (hard constraints) and where they can be relaxed for some time (soft constraints). We propose a Lyapunov-based predictive control design that guarantees stabilization and state and input constraint satisfaction for all times from an explicitly characterized set of initial conditions. An auxiliary Lyapunov-based analytical bounded control design is used to characterize the stability region of the predictive controller and also provide a feasible initial guess to the optimization problem in the predictive controller formulation. For the case when the state constraints are soft, we propose a switched predictive control strategy that reduces the time during which state constraints are violated, driving the states into the state and input constraints feasibility region of the Lyapunov-based predictive controller. We demonstrate the application of the Lyapunov-based predictive controller designs through a chemical process example.     

A constraint satisfaction neural network and heuristic combined approach for concurrent activities scheduling

Scheduling activities in concurrent product development process is of great sig-nificance to shorten developements lead time and minimize the cost.Moreover,it can eliminate the unnecessary redesign periods and guarantee that serial activities can be executed as concurrently as possible,This paper presents a constraint satisfaction neural network and heuristic combined approach for concurrent activities scheduling.In the combined approack,the neural network is used to obtain a feasible starting time of all the activities based on sequence constraints ,the heuristic algorithm is used to obtain a feasible solution of the scheduling problem based on resource constrainsts.The feasible scheduling solution is obtained by a gradient optimization function .Sim-ulations have shown that the proposed combined approach is efficient and fasible with respect to concurrent activities scheduling.     

A Constraint Satisfaction Neural Network and Heuristic Combined Approach for Concurrent Activities Scheduling

Scheduling activities in concurrent product development process is of great significance to shorten development lead time and minimize the cost. Moreover, it can eliminate the unnecessary redesign periods and guarantee that serial activities can be executed as concurrently as possible. This paper presents a constraint satisfaction neural network and heuristic combined approach for concurrent activities scheduling. In the combined approach, the neural network is used to obtain a feasible starting time of all the activities based on sequence constraints, the heuristic algorithm is used to obtain a feasible solution of the scheduling problem based on resource constraints. The feasible scheduling solution is obtained by a gradient optimization function. Simulations have shown that the proposed combined approach is efficient and feasible with respect to concurrent activities scheduling.     

约束不均衡条件下车辆双层线路规划流动稳定性问题研究

双层线路在高峰期时,车辆规划计算最优解过程中为每个约束条件都分配一个最优解,会极大地浪费计算资源。车辆物流线路规划过程中,约束条件不均衡的天然特性,会导致规划过程车辆的流动稳定性受到影响。针对约束条件不均衡,对车辆双层线路规划流动稳定性影响的问题展开研究。构建了车辆物流线路双层规划Stackelberg模型,上层部分主要用于约束车辆物流线路的容量以及结构,排除不可用路线;下层部分主要对车辆物流线路实施均衡化配流,防止过多的车辆拥挤在同一路线中。利用模型将调度业务整合到高容量的路线中调度。在模型中加入调度资源缓存技术,保证调度过程的稳定性。实验结果表明：与使用单一模型求解相比,使用该模型进行调度业务疏导,可以在很大程度上获得更稳定的性能,解决了车辆物流线路规划流动稳定性问题。