Heuristic control of a constraint-based algorithm for the preemptive job-shop scheduling problem

被引：9

作者：

Le Pape C. ^{[1
]}

Baptiste P. ^{[1
]}

机构：

[1] Bouygues, Direction des Technologies Nouvelles, F-78061 Saint-Quentin-en-Yvelines, 1, av. E. Freyssinet

来源：

Journal of Heuristics | 1999年 / 5卷 / 3期

关键词：

preemptive scheduling; job-shop scheduling; constraint programming; constraint propagation; resource constraints; timetables; edge-finding; limited discrepancy search; depth-bounded discrepancy search;

D O I：

10.1023/A:1009613717770

中图分类号：

学科分类号：

摘要：

In the recent years, constraint programming has been applied to a wide variety of academic and industrial non-preemptive scheduling problems, i.e., problems in which activities cannot be interrupted. In comparison, preemptive scheduling problems have received almost no attention from both the Operations Research and the Artificial Intelligence community. Motivated by the needs of a specific application, we engaged in a study of the applicability of constraint programming techniques to preemptive scheduling problems. This paper presents the algorithms we developed and the results we obtained on the preemptive variant of the famous `job-shop scheduling problem.' Ten heuristic search strategies, combined with two different constraint propagation techniques, are presented, and compared using two well-known series of job-shop scheduling instances from the literature. The best combination, which relies on `limited discrepancy search' and on `edge-finding' techniques, is shown to provide excellent solutions to the preemptive job-shop scheduling problem. A mean relative distance to the optimal solution of 0.32% is achieved in five minutes, on instances with 10 jobs and 10 machines (100 activities).

引用

页码：305 / 325

页数：20

共 62 条

[1]

Adams J., Balas E., Zawack D., The Shifting Bottleneck Procedure for Job-Shop Scheduling, Management Science, 34, pp. 391-401, (1988)

[2]

Aggoun A., Beldiceanu N., Extending CHIP in Order to Solve Complex Scheduling and Placement Problems, Mathematical and Computer Modelling, 17, pp. 57-73, (1993)

[3]

Applegate D., Cook W., A Computational Study of the Job-Shop Scheduling Problem, ORSA Journal on Computing, 3, pp. 149-156, (1991)

[4]

Baptiste Ph., Le Pape C., A Theoretical and Experimental Comparison of Constraint Propagation Techniques for Disjunctive Scheduling, Proc. 14th International Joint Conference on Artificial Intelligence, pp. 600-606, (1995)

[5]

Baptiste Ph., Le Pape C., Nuijten W.P.M., Constraint-Based Optimization and Approximation for Job-Shop Scheduling, Proc. AAAI-SIGMAN Workshop on Intelligent Manufacturing Systems, pp. 5-16, (1995)

[6]

Baptiste Ph., Le Pape C., Constraint Propagation and Decomposition Techniques for Highly Disjunctive and Highly Cumulative Project Scheduling Problems, Proc. 3rd International Conference on Principles and Practice of Constraint Programming, pp. 375-389, (1997)

[7]

Beck H., Constraint Monitoring in TOSCA, Proc. AAAI Spring Symposium on Practical Approaches to Planning and Scheduling, (1992)

[8]

Beck J.C., Davenport A.J., Sitarski E.M., Fox M.S., Texture-Based Heuristics for Scheduling Revisited, Proc. 14th National Conference on Artificial Intelligence, (1997)

[9]

Brucker P., Jurisch B., Sievers B., A Branch and Bound Algorithm for the Job-Shop Scheduling Problem, Discrete Applied Mathematics, 49, pp. 107-127, (1994)

[10]

Brucker P., Thiele O., A Branch and Bound Method for the General-Shop Problem with Sequence-Dependent Setup Times, OR Spektrum, 18, pp. 145-161, (1996)

← 1 2 3 4 5 6 7 →