Technology and system of constraint programming for industry production scheduling Part I: A brief survey and potential directions

Yarong CHEN, Zailin GUAN, Yunfang PENG, Xinyu SHAO, Muhammad HASSEB

PDF(237 KB)
PDF(237 KB)
Front. Mech. Eng. ›› DOI: 10.1007/s11465-010-0106-x
RESEARCH ARTICLE

Technology and system of constraint programming for industry production scheduling Part I: A brief survey and potential directions

Author information +
History +

Abstract

The use of techniques and system of constraint programming enables the implementation of precise, flexible, efficient, and extensible scheduling systems. It has been identified as a strategic direction and dominant form for the application into planning and scheduling of industrial production. This paper systematically introduces the constraint modeling and solving technology for production scheduling problems, including various real-world industrial applications based on the Chip system of Cosytec Company. We trend of some concrete technology, such as modeling, search, constraint propagation, consistency, and optimization of constraint programming for scheduling problems. As a result of the application analysis, a generic application framework for real-life scheduling based on commercial constraint propagation (CP) systems is proposed.

Keywords

constraint programming / production scheduling / constraint propagation / search / consistency / optimization

Cite this article

Download citation ▾
Yarong CHEN, Zailin GUAN, Yunfang PENG, Xinyu SHAO, Muhammad HASSEB. Technology and system of constraint programming for industry production scheduling Part I: A brief survey and potential directions. Front Mech Eng Chin, https://doi.org/10.1007/s11465-010-0106-x

References

[1]
Barták R. Constraint programming: in pursuit of the Holy Grail. In: Proceedings of the Week of Doctoral Students, Part IV, Prague, Czech Republic, 1999: 555–564
[2]
Kumar V. Algorithms for constraint-satisfaction problems: a survey. Artificial Intelligence, 1992, 13(2): 32–44
[3]
Le Pape C. Constraint-Based Programming for Scheduling: An historical Perspective. Working Paper, Operation Research Society Seminar on Constraint Handling Techniques, London, United Kingdom, 1994
[4]
Freuder E C. In pursuit of the Holy Grail. Constraints, 1997, 2(1): 57–61
CrossRef Google scholar
[5]
Nuitjen W P M, Aarts E H L. A Computational study of constraint satisfaction for multiple capacitated job-shop scheduling. European Journal of Operational Research, 1996, 90(2): 269–284
CrossRef Google scholar
[6]
Guéret C, Jussien N, Prins C. Using intelligent backtracking to improve branch-and-bound methods: An application to open-shop problems. European Journal of Operational Research, 2000, 127(2): 344–354
CrossRef Google scholar
[7]
Zhang X H, Bard J F. A multi-period machine assignment problem. European Journal of Operational Research, 2006, 170(2): 398–415
CrossRef Google scholar
[8]
Le Pape C. Constraint-based scheduling: a tutorial. http://www.math.unipd.it/%7Efrossi/cp-school/lepape.pdf
[9]
Bessière C. Constraint Propagation (Ch 3). Rossi F, Van Beek P, Walsh T. Handbook of Constraint Programming. Amsterdam, Elsevier Science Ltd, Boston, 2006
[10]
Le Pape C. Implementation of resource constraints in ILOG schedule: A library for the development of constraint-based scheduling systems. Intelligent System Engineering, 1994, 3(2): 55–66
CrossRef Google scholar
[11]
Baptiste P, Le Pape C. Disjunctive constraints for manufacturing scheduling: principles and extensions. International Journal of Computer Integrated Manufacturing, 1996, 9(4): 306–310
CrossRef Google scholar
[12]
Dash Optimization Ltd. Xpress-Kalis Reference Manual, 2007
[13]
ILOG Inc. ILOG Scheduler 6.2 Reference Manual, 2006
[14]
Dubois D, Fargier H, Prade H. Fuzzy constraints in job-shop scheduling. Journal of Intelligent Manufacturing, 1995, 6(4): 215–234
CrossRef Google scholar
[15]
Barták R. Modelling soft constraints: a survey. Neural Network World, 2002, 12(5): 1–10
[16]
Sadeh N, Sycara K, Xiong Y L. Backtracking techniques for the job shop scheduling constraint satisfaction problem. Artificial Intelligence, 1995, 76(1-2): 455–480
CrossRef Google scholar
[17]
Stergiou K, Koubarakis M. Backtracking algorithms for disjunctions of temporal constraints. Artificial Intelligence, 2000, 120(1): 81–117
CrossRef Google scholar
[18]
Wu H, Beek P. On universal restart strategies for backtracking search. In: Proceedings of the Thirteenth International Conference on Principles and Practice of Constraint Programming, 2007: 681–695
[19]
Dcchter R, Meiri I. Experimental evaluation of preprocessing algorithms for constraint satisfaction problems. Artificial Intelligence, 1994, 68(2): 211–241
CrossRef Google scholar
[20]
Minton S, Johnston M D, Philips A B, Laird P. Minimizing conflicts: a heuristic repair method for constraint satisfaction and scheduling problems. Artificial Intelligence, 1992, 58(1-3): 161–205
CrossRef Google scholar
[21]
Sadeh N, Fox M S. Variable and value ordering heuristics for the job shop scheduling constraint satisfaction problem. Artificial Intelligence, 1996, 86(1): l–41
CrossRef Google scholar
[22]
Cheng C C, Smith S F. Applying constraint satisfaction techniques to job shop scheduling. Annual of Operation Resource, 1997, 70: 327–378
CrossRef Google scholar
[23]
Nuijten W P M. Time and resource constrained scheduling: A constraint satisfaction approach, Ph.D. Thesis at Eindhoven University of Technology, 1994
[24]
Beck J C, Fox M S. Dynamic problem structure analysis as a basis for constraint-directed scheduling heuristics. Artificial Intelligence, 2000, 117(1): 31–81
CrossRef Google scholar
[25]
Tsang E. Foundations of Constraint Satisfaction. London: Academic Press , 1993
[26]
Beck J C. Solution-guided multi-point constructive search for job shop scheduling. Journal of Artificial Intelligence Research, 2007, 29(3): 49–77
[27]
Watson J P, Beck J C. A hybrid constraint programming/local search approach to the job-shop scheduling problem. Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 2008, 5015: 263–277
CrossRef Google scholar
[28]
Baptiste P, Le Pape C. Edge-Finding Constraint Propagation Algorithms for Disjunctive and Cumulative Scheduling. In: Proceedings of the Fifteenth Workshop of the U.K. Planning Special Interest Group, Liverpool, United Kingdom, 1996. Available from http://www.hds.utc.fr/ baptiste/
[29]
Baptiste P, Le Pape C. A Theoretical and experimental comparison of constraint propagation techniques for disjunctive scheduling. International Joint Conference on Artificial Intelligence, Montreal, Quebec, 1995
[30]
Laborie P. Algorithms for propagating resource constraints in AI planning and scheduling: Existing approaches and new results. Artificial Intelligence, 2003, 143(2): 151–188
CrossRef Google scholar
[31]
Dorndorf U, Pesch E, Phan-Huy T. Solving the open shop scheduling problem. Journal of Schdeuling, 2001, (4): 157–174
[32]
Jussien N, Lhomme O. Local search with constraint propagation and conflict-based heuristics. Artificial Intelligence, 2002, 139(1): 21–45
CrossRef Google scholar
[33]
Barták R. Practical Constraints: A Tutorial on Modeling with Constraints. 5th Workshop on Constraint Programming for Decision, Gliwice, Poland, 2003: 7–17
[34]
Law Y C, Lee J H M. Automatic generation of redundant models for permutation constraint satisfaction problems. Journal of Consrtraints, 2007, 12(4): 469–505
CrossRef Google scholar
[35]
Barták R. Theory and practice of constraint propagation. In: Proceedings of the third Workshop on Constraint Programming in Decision and Control, Silesian University, Poland, 2001: 7–14
[36]
Bessière C, Régin J C, Yap R H C, Zhang Y. An optimal coarse-grained arc consistency algorithm. Artificial Intelligence, 2005, 165(2): 165–185
CrossRef Google scholar
[37]
Brailsford S C, Potts C N, Smith B M. Constraint satisfaction problems: Algorithms and applications. European Journal of Operational Research, 1999, 119(3): 557–581
CrossRef Google scholar
[38]
Bessière C, Debruyne R. Theoretical analysis of singleton arc consistency and its extensions. Artificial Intelligence, 2008, 172(1): 29–41
CrossRef Google scholar
[39]
Baptiste P, Le Pape C, Nuijten W P M. Incorporating efficient operations research algorithms in constraint-based scheduling. In: Proceedings of the First International Joint Workshop on Artificial Intelligence and Operations Research, Timberline Lodge, Oregon, 1995
[40]
Hooker J N. Logic, optimization and constraint programming. INFORMS Journal on Computing, 2002, 14(4): 295–321
CrossRef Google scholar
[41]
Jain V, Grossmann I E. Algorithms for hybrid MILP/CP models for a class of optimization problems. INFORMS Journal on Computing, 2001, 13(4): 258–276
CrossRef Google scholar
[42]
Cambazard H, Jussien N. Integrating Benders decomposition within constraint programming. In: Proceedings of CP, Sitges, Spain, 2005, 752–756
[43]
Milano M, Wallace M. Integrating operations research in constraint programming. Annals of Operations Research, 2005, 4(3): 175–219
[44]
Timpe C. Solving planning and scheduling problems with combined integer and constraint programming. Operation Research Spectrum, 2002, 24(4): 431–448
[45]
Jahangirian M, Conroy G V. Intelligent dynamic scheduling system: the application of genetic algorithms. Integrated Manufacturing Systems, 2000, 11(4): 247–257
CrossRef Google scholar
[46]
Loudni S, Boizumault P. Combining VNS with constraint programming for solving anytime optimization problems. European Journal of Operational Research, 2008, 191(3): 705–735
CrossRef Google scholar
[47]
Zupanic D. Optimal solution for a textile production unit. In: Proceedings of the Second International Conference, <month>April</month>1996
[48]
Freuder G, Wallace M. Constraint technology and the commercial world. IEEE Intelligent Systems, 2000, 15(1): 20–23
CrossRef Google scholar
[49]
Simonis H. Building industrial applications with constraint programming. Principles and Practice of Constraint Programming, 2007, 4741: 271–309
[50]
Simonis H, Charlier P, Kay P. Constraint handling in an integrated transportation problem. IEEE Intelligent Systems, 2000, 15(1): 26–32
CrossRef Google scholar

Acknowledgments

This research work was jointly supported by the National Natural Science Foundation of China (Grant Nos. 70772056 and 50825503), the State Hi-Tech R&D Program of China (No. 2007AA04Z110), and the Science and Technology Plan Project of Wenzhou (G20090038)

RIGHTS & PERMISSIONS

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg
AI Summary AI Mindmap
PDF(237 KB)

Accesses

Citations

Detail

Sections
Recommended

/