Please wait a minute...
Shopping Cart Email List Chinese
Advanced Search Fig/Tab
Frontiers of Mechanical Engineering

ISSN 2095-0233

ISSN 2095-0241(Online)

CN 11-5984/TH

Postal Subscription Code 80-975

2018 Impact Factor: 0.989

Featured Articles  |  Most Downloaded  |  Most Reading
Online Submission Subscribe to Our RSS Content Feed
Front Mech Eng Chin    0, Vol. Issue () : 455-464    https://doi.org/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
Yarong CHEN1,2, Zailin GUAN3, Yunfang PENG3(), Xinyu SHAO3, Muhammad HASSEB4,5
1. State Key Lab of Digital Manufacturing Equipment & Technology, Huazhong University of Science and Technology, Wuhan 430074, China; 2. Mechanical & Electrical Engineering College, Wenzhou University, Wenzhou 325035, China; 3. State Key Lab of Digital Manufacturing Equipment & Technology, Huazhong University of Science and Technology, Wuhan 430074, China; 4. State Key Lab of Digital Manufacturing Equipment & Technology, Huazhong University of Science and Technology, Wuhan 430074, China; 5. Comsats Institute of Information Technology, Abbottabad 22010, Pakistan
 Download: PDF(237 KB)   HTML
 Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
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     
Corresponding Author(s): PENG Yunfang,Email:yunyun842@gmail.com   
Issue Date: 05 December 2010
 Cite this article:   
Yarong CHEN,Zailin GUAN,Yunfang PENG, et al. Technology and system of constraint programming for industry production scheduling — Part I: A brief survey and potential directions[J]. Front Mech Eng Chin, 0, (): 455-464.
 URL:  
https://academic.hep.com.cn/fme/EN/10.1007/s11465-010-0106-x
https://academic.hep.com.cn/fme/EN/Y0/V/I/455
type implicationtype
disjunctive schedulingcumulative scheduling
★each resource(machine) can execute at most one activity at a time★a resource can run several activities in parallel, provided that the resource capacity is not exceeded
nonpreemptive scheduling☆activities cannot be interrupted, and each activity Ai must be executed without interruption from its start time to its end timedecision variable: sti, cti, wit value domain: [esti, lsti), [ecti, lcti) sti + dti≤stk, when activity Ai precedence Ak
c(rj)=1 sti + dti≤stk ∨ stk + dtk≤sti, when Ai and Ak use the same resourcec(rj)≥1 ∑Acrij*wit≤c(rj)
preemptive scheduling☆activities can be interrupted at any time, e.g., to let some other activities executedecision variable: seti, wit value domain: [sti, cti), sti=mint∈seti(t), cti=maxt∈seti(t) wit=1?t∈seti, eles wit=0
c(rj)=1 sti + dti≤stk ∨ stk + dtk≤sti, when Ai and Ak use the same resourcec(rj)≥1 ∑Acrij*wit≤c(rj)
Tab.1  Common model description of scheduling problems
Fig.1  Relationship of CP technology for solving production scheduling problems
Fig.2  Comparison of propagation techniques
Fig.3  Relationship of basic consistency methods
constraint programmingoperation research (IP/MILP)
commonalityrely heavily on branch search accelerate the search by logic inference
differencesproblemFlexiblestructured
formulationdeclarativeprocedural
solvingreduction and propagationrelaxation
solutionfeasibleoptimal
searchexploit substructurehighly structured
Tab.2  Comparison of CP and OR (integer programming)
Fig.4  Framework for industrial production scheduling decision system based on CP
Fig.5  Summary of research on constraint-based production scheduling
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
doi: 10.1023/A:1009749006768
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
doi: 10.1016/0377-2217(95)00354-1
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
doi: 10.1016/S0377-2217(99)00488-9
7 Zhang X H, Bard J F. A multi-period machine assignment problem. European Journal of Operational Research , 2006, 170(2): 398–415
doi: 10.1016/j.ejor.2004.07.051
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
doi: 10.1049/ise.1994.0009
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
doi: 10.1080/095119296131616
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
doi: 10.1007/BF00128646
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
doi: 10.1016/0004-3702(95)00078-S
17 Stergiou K, Koubarakis M. Backtracking algorithms for disjunctions of temporal constraints. Artificial Intelligence , 2000, 120(1): 81–117
doi: 10.1016/S0004-3702(00)00019-9
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
doi: 10.1016/0004-3702(94)90068-X
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
doi: 10.1016/0004-3702(92)90007-K
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
doi: 10.1016/0004-3702(95)00098-4
22 Cheng C C, Smith S F. Applying constraint satisfaction techniques to job shop scheduling. Annual of Operation Resource , 1997, 70: 327–378
doi: 10.1023/A:1018934507395
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
doi: 10.1016/S0004-3702(99)00099-5
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
doi: 10.1007/978-3-540-68155-7_21
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
doi: 10.1016/S0004-3702(02)00362-4
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
doi: 10.1016/S0004-3702(02)00221-7
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
doi: 10.1007/s10601-007-9024-x
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
doi: 10.1016/j.artint.2005.02.004
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
doi: 10.1016/S0377-2217(98)00364-6
38 Bessière C, Debruyne R. Theoretical analysis of singleton arc consistency and its extensions. Artificial Intelligence , 2008, 172(1): 29–41
doi: 10.1016/j.artint.2007.09.001
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
doi: 10.1287/ijoc.14.4.295.2828
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
doi: 10.1287/ijoc.13.4.258.9733
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
doi: 10.1108/09576060010326375
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
doi: 10.1016/j.ejor.2006.12.062
47 Zupanic D. Optimal solution for a textile production unit. In: Proceedings of the Second International Conference , April1996
48 Freuder G, Wallace M. Constraint technology and the commercial world. IEEE Intelligent Systems , 2000, 15(1): 20–23
doi: 10.1109/MIS.2000.820324
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
doi: 10.1109/5254.820326
[1] Yanjun HAN, Haiyang ZHANG, Menghuan YU, Jinzhou YANG, Linmao QIAN. Simulation model optimization for bonnet polishing considering consistent contact area response[J]. Front. Mech. Eng., 2024, 19(4): 27-.
[2] Minjie SHAO, Tielin SHI, Qi XIA. An M-VCUT level set-based data-driven model of microstructures and optimization of two-scale structures[J]. Front. Mech. Eng., 2024, 19(4): 26-.
[3] Qi LI, Lei DING, Xin LUO. Dynamic motion of quadrupedal robots on challenging terrain: a kinodynamic optimization approach[J]. Front. Mech. Eng., 2024, 19(3): 20-.
[4] Shengjie XIAO, Yongqi SHI, Zemin WANG, Zhe NI, Yuhang ZHENG, Huichao DENG, Xilun DING. Lift system optimization for hover-capable flapping wing micro air vehicle[J]. Front. Mech. Eng., 2024, 19(3): 19-.
[5] Kun XU, Xinghan ZHUANG, Zhou SU, Qiuhong LIN, Shouzhi REN, Hang XIAO, Xilun DING. A novel stiffness optimization model of space telescopic boom based on locking mechanism[J]. Front. Mech. Eng., 2024, 19(3): 18-.
[6] Ye TIAN, Tielin SHI, Qi XIA. Buckling optimization of curvilinear fiber-reinforced composite structures using a parametric level set method[J]. Front. Mech. Eng., 2024, 19(1): 9-.
[7] Yingjun WANG, Zhenbiao GUO, Jianghong YANG, Xinqing LI. Multiresolution and multimaterial topology optimization of fail-safe structures under B-spline spaces[J]. Front. Mech. Eng., 2023, 18(4): 52-.
[8] Yi YAN, Xiaopeng ZHANG, Jiaqi HE, Dazhi WANG, Yangjun LUO. Achieving desired nodal lines in freely vibrating structures via material-field series-expansion topology optimization[J]. Front. Mech. Eng., 2023, 18(3): 42-.
[9] Yunpeng YIN, Yue ZHAO, Yuguang XIAO, Feng GAO. Footholds optimization for legged robots walking on complex terrain[J]. Front. Mech. Eng., 2023, 18(2): 26-.
[10] Haitao LUO, Qiming WEI, Yuxin LI, Junlin LI, Wei ZHANG, Weijia ZHOU. Numerical simulation and experimental research on the wheel brush sampling process of an asteroid sampler[J]. Front. Mech. Eng., 2023, 18(2): 16-.
[11] Aodi YANG, Shuting WANG, Nianmeng LUO, Tifan XIONG, Xianda XIE. Massively efficient filter for topology optimization based on the splitting of tensor product structure[J]. Front. Mech. Eng., 2022, 17(4): 54-.
[12] Jianzhao WU, Chaoyong ZHANG, Kunlei LIAN, Jiahao SUN, Shuaikun ZHANG. Processing parameter optimization of fiber laser beam welding using an ensemble of metamodels and MOABC[J]. Front. Mech. Eng., 2022, 17(4): 47-.
[13] Junhui ZHANG, Yining SHEN, Minyao GAN, Qi SU, Fei LYU, Bing XU, Yuan CHEN. Multi-objective optimization of surface texture for the slipper/swash plate interface in EHA pumps[J]. Front. Mech. Eng., 2022, 17(4): 48-.
[14] Rujun FAN, Yunhua LI, Liman YANG. Multiobjective trajectory optimization of intelligent electro-hydraulic shovel[J]. Front. Mech. Eng., 2022, 17(4): 50-.
[15] Zhaokun ZHANG, Zhufeng SHAO, Zheng YOU, Xiaoqiang TANG, Bin ZI, Guilin YANG, Clément GOSSELIN, Stéphane CARO. State-of-the-art on theories and applications of cable-driven parallel robots[J]. Front. Mech. Eng., 2022, 17(3): 37-.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed