Study On The Constraint Satisfaction Technique And Its Application For Production Scheduling

Production management is an important means to raise production efficiency and economy benefit for the modern production enterprises. The production scheduling is the key technique to the whole production management system. Job shop scheduling problem is a kind of most complex representative scheduling problem in production scheduling domain. It is remarkable that, not only because its background can frencently occur in production, medical treatment, traffic, transport, communication and other application domain, but also because its model can be regard as a generalization for single machine, parallel machine and flow shop scheduling, etc, many researchers in both academical and industry community pay their attention to the modeling and algorithms for job shop scheduling problem. However, it is well known that it is difficult to resolve.Whereas general job shop scheduling problem is belonging to NP-hard problem, it is very difficult to discuss the optimization solution indeed. With additional real-time and dynamic requirenment, the most of problems become NP-complete ones, even the feasible solution is stubborn to obtain. So it is practical research on contructing feasible and approximate algorithm for the problem.Based on constraint satisfaction idea and theory, this dissertation makes basic research on constraint satisfaction technique for general job shop scheduling problem, complex job shop scheduling problem, real-time job shop scheduling problem and dynamic reaction job shop scheduling problem. In each of the two kinds of method, viz. incremental construction method and iterative repair method, the research includes four aspects:constraint propagation, search strategy, embedded heuristic rule and learning mechanism. For the different problems, the constraint satisfaction optimization models and constraint network connectionist architecture models are established. Based constraint satisfaction technique, the algorithms for these models are proposed and designed. The major content of the dissertation is summarized as follows:1) Based on incremental construction method, by analyzing advantages and disadvantages of traditional operational research and constraint satisfaction method respectively, a hybrid algorithm of constraint propagation technique and branch-and-bound method is proposed in which a branch-and-bound search tree with time windows is constructed and the temporary constraint propagation is executed at each tree node. The proposed hybrid stategy is then applied to solve the job shop scheduling problem with the objective of minimizing the maximal completion time.2) Based on incremental construction method, a constraint satisfaction optimization model is established, and an arc-consistence constraint propagation optimization algorithm is developed for this model. In order to direct the filtration in each node and speed up search for the solutions, the dynamic enhanced constraint propagation techniques are designed and embedded in each node in the process of search. The propsed model and algorithm is then applied to solve job shop scheduling problem with the same release time and due date and the objective of minimizing the maximal completion time.3) Based on iterative repair method, a GENET network connectionist architecture constraint satisfaction optimization model is established for the large scale optimization problems. For this model, an algorithm based on progressive stochastic search is proposed by designing and constructing a constraint propagation framework with posting new constraints in the network. The propsed model and algorithm is then applied to solve job shop scheduling problem. The constraint network connectionist architecture with repair optimization strategy is constructed by mapping between problem and network.4) Based on iterative repair method, by considering the object avaiblity, a kind of GENET network connectionist architecture constraint satisfaction optimization model with restrictive window constraints is established. An algorithm with the progressive stochastic search scheme and embedded heuristics is proposed for this network. The propsed model and algorithm is then applied to solve job shop scheduling problem with different release dates and due dates. In the process of searching, two heuristic methods are embedded to realize the objective of minimizing the weighted number of tardy jobs.5) Based on iterative repair method, by concidering resource avaiblity, a kind of GENET network connectionist architecture constraint satisfaction optimization model with various discontinuous window constraints is established. Based on this network model, an algorithm with progressive stochastic search scheme and embedded heuristic is proposed. The propsed model and algorithm is then applied to solve job shop scheduling problem with ready time and due date constraints on jobs, shutdown constraints on the machines, and the scheduling objective of minimize the percentage of tardy jobs. Assume that the machine unavailable time is known in advance, three cases with single shutdown and multiple shutdowns are considered.6) Based on iterative repair method, a kind of GENET network connectionist architecture constraint satisfaction optimization model with forced restrictive windows (hard constraints) is established. Based on this network model, iterative repair search strategy and embedded heuristic learning rule for multi-objectives problem is proposed. The propsed model and algorithm is then applied to solve job shop on-line real-time scheduling problem with bicriterion of deadlines and optimization. A heuristic policy which is modified from the earliest deadline first policy and an optimal mechanism are embedded into the proposed method to satisfy both deadline constraints and optimization objective.7) Based on iterative repair method, a kind of GENET network connectionist architecture constraint satisfaction optimization model with the ability to adjust and repair the dynamic disruptions is established. Based on this network model, iterative repair search strategy is proposed to make it possible for original constraint network connectionist architecture to keep with the external the dynamic disruptions. The propsed model and algorithm is then applied to solve job shop scheduling problem job shop scheduling problem with double disruptions of machine breakdown and urgent job. Under the conditions of satisfying the feasibility of new schedule, the objective of minimizing the difference between the new and the original schedule is realized. 8) The non-binary constraint satisfaction problem exists abroad in the real world, and E-GENET is still short of support from theory and practice. After giving the new mathematics definition of the non-binary constraint satisfaction problem and E-GENET network model energy function completely and accurately, the non-binary constraint satisfaction problem is translated into the integer constrained minimization problems. And a class of discrete Lagrangian-based search scheme and algorithm with non-binary variable constraints is proposed. The connective relationship between E-GENET and discrete Lagrangian multiplier method is established. Then E-GENET can be extended and reconstructed. The theory of resolving the multi-overconstraint problem is studied and. proofed. The propsed method is then applied to solve classical job shop scheduling problem.9) Based on the above researches, in order to verify the performance of the propsed models and algorithms and try to explore the feasibility on industry application, a sorftwore platform on the job shop constraint satisfaction scheduling problems is developed under the VC++6.0 environment. The propsed models and algorithms has been testing on the plateform. The computational experiments are carried out and demonstrate that the proposed approach is effective...