×

Solving variants of the job shop scheduling problem through conflict-directed search. (English) Zbl 1329.90061

Summary: We introduce a simple technique for disjunctive machine scheduling problems and show that this method can match or even outperform state-of-the-art algorithms on a number of problem types. Our approach combines a number of generic search techniques such as restarts, adaptive heuristics, and solution-guided branching on a simple model based on a decomposition of disjunctive constraints and on the reification of these disjuncts.{ } This paper describes the method and its application to variants of the job shop scheduling problem (JSP). We show that our method can easily be adapted to handle additional side constraints and different objective functions, often outperforming the state-of-the-art and closing a number of open problems. Moreover, we perform in-depth analysis of the various factors that make this approach efficient. We show that, while most of the factors give moderate benefits, the variable and value ordering components are key.

MSC:

90B35 Deterministic scheduling theory in operations research
90C27 Combinatorial optimization
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adams J, Balas E, Zawack D (1988) The shifting bottleneck procedure for job shop scheduling. Management Sci. 34:391-401. Abstract, · Zbl 0637.90051
[2] Applegate D, Cook W (1991) A computational study of the job-shop scheduling problem. INFORMS J. Comput. 3:149-156. Abstract, · Zbl 0755.90039
[3] Artigues C, Feillet D (2008) A branch and bound method for the job-shop problem with sequence-dependent setup times. Ann. Oper. Res. 159:135-159. CrossRef · Zbl 1152.90424
[4] Artigues C, Huguet M-J, Lopez P (2011) Generalized disjunctive constraint propagation for solving the job shop problem with time lags. Engrg. Appl. Artificial Intelligence 24:220-231. CrossRef
[5] Baptiste P, Le Pape C (1995) A theoretical and experimental comparison of constraint propagation techniques for disjunctive scheduling. Proc. 14th Internat. Joint Conf. Artificial Intelligence–IJCAI’95, Quebec, 600-606.
[6] Baptiste P, Le Pape C (1996) Edge-finding constraint propagation algorithms for disjunctive and cumulative scheduling. Proc. 15th Workshop U.K. Planning Special Interest Group, Liverpool, UK.
[7] Baptiste P, Le Pape C, Nuijten W (2001) Constraint-Based Scheduling: Applying Constraint Programming Techniques to Scheduling Problems (Kluwer Academic Publishers, Dordrecht, the Netherlands). CrossRef · Zbl 1094.90002
[8] Beck JC (2007) Solution-guided multi-point constructive search for job shop scheduling. J. Artificial Intelligence Res. 29:49-77. · Zbl 1182.68058
[9] Beck JC, Refalo P (2003) A hybrid approach to scheduling with earliness and tardiness costs. Ann. Oper. Res. 118:49-71. CrossRef · Zbl 1026.90039
[10] Beck JC, Davenport AJ, Sitarski EM, Fox MS (1997) Texture-based heuristics for scheduling revisited. Proc. 14th National Conf. Artificial Intelligence (AAAI’97), Providence, RI, 241-248.
[11] Boussemart F, Hemery F, Lecoutre C, Sais L (2004) Boosting systematic search by weighting constraints. Proc. 16th Eur. Conf. Artificial Intelligence (ECAI’04), Valencia, Spain, 146-150.
[12] Brucker P, Thiele O (1996) A branch and bound method for the general-shop problem with sequence-dependent setup times. Oper. Res. Spektrum 18:145-161. CrossRef · Zbl 0852.90087
[13] Brucker P, Hurink J, Jurisch B, Wöstmann B (1997) A branch and bound algorithm for the open-shop problem. Discrete Appl. Math. 76:43-59. CrossRef · Zbl 0882.90066
[14] Bürgy R, Gröflin H (2012) Optimal job insertion in the no-wait job shop. J. Combin. Optim. 26:345-371. CrossRef · Zbl 1297.90189
[15] Carlier J (1978) Ordonnancements à contraintes disjonctives. R.A.I.R.O Recherche Opérationelle/Oper. Res. 12:333-350. · Zbl 0401.90052
[16] Carlier J, Pinson E (1989) An algorithm for solving the job-shop problem. Management Sci. 35:164-176. Abstract, · Zbl 0677.90036
[17] Carlier J, Pinson E (1994) Adjustment of heads and tails for the job-shop problem. Eur. J. Oper. Res. 78:146-191. CrossRef · Zbl 0812.90063
[18] Caumond A, Lacomme P, Tchernev N (2008) A memetic algorithm for the job-shop with time-lags. Comput. Oper. Res. 35:2331-2356. CrossRef · Zbl 1177.90147
[19] Danna E, Perron L (2003) Structured vs. unstructured large neighborhood search: A case study on job-shop scheduling problems with earliness and tardiness costs. Proc. Principles Practice Constraint Programming (CP’03), Kinsale, Ireland, 817-821. CrossRef
[20] Dechter R, Meiri I, Pearl J (1991) Temporal constraint networks. Artificial Intelligence 49:61-95. CrossRef · Zbl 0737.68070
[21] Fisher H, Thompson GL (1963) Probabilistic learning combinations of local job-shop scheduling rules. Muth JF, Thompson GL, eds. Industrial Scheduling (Prentice Hall, Englewood Cliffs, NJ), 225-251.
[22] Fox MS, Sadeh NM, Baykan CA (1989) Constrained heuristic search. Proc. 11th Internat. Joint Conf. Artificial Intelligence (IJCAI’89), Detroit, 309-315.
[23] Geelen PA (1992) Dual viewpoint heuristics for binary constraint satisfaction problems. Proc. 10th Eur. Conf. Artificial Intelligence (ECAI’92), Vienna, 31-35.
[24] Gini C (1912) Variabilita e mutabilita contributo allo studio della distribuzioni. Studie Economico-Guiridici della R. Universita di Cagliari 3:1-158.
[25] González MA, Vela CR, Varela R (2008) A new hybrid genetic algorithm for the job shop scheduling problem with setup times. Proc. 18th Internat. Conf. Automated Planning Scheduling (ICAPS’08), Sydney, Australia, 116-123.
[26] Grimes D (2012) Identifying sources of global contention in constraint satisfaction search. Ph.D. thesis, National University of Ireland, Cork, http://cora.ucc.ie/handle/10468/646.
[27] Grimes D, Hebrard E (2010) Job shop scheduling with setup times and maximal time-lags: A simple constraint programming approach. Lodi A, Milano M, Toth P, eds. CPAIOR, Lecture Notes in Computer Science, Vol. 6140 (Springer, Berlin), 147-161. CrossRef · Zbl 1285.68157
[28] Grimes D, Hebrard E (2011) Models and strategies for variants of the job shop scheduling problem. Proc. Principles Practice Constraint Programming (CP’11), Lecture Notes in Computer Science, Vol. 6876 (Springer, Berlin), 356-372. CrossRef
[29] Grimes D, Hebrard E, Malapert A (2009) Closing the open shop: Contradicting conventional wisdom. Proc. Principles Practice Constraint Programming (CP’09), Lecture Notes in Computer Science, Vol. 5732 (Springer, Berlin), 400-408. CrossRef
[30] Guéret C, Prins C (1999) A new lower bound for the open-shop problem. Ann. Oper. Res. 92:165-183. CrossRef · Zbl 0958.90033
[31] Hebrard E (2008) Mistral, a constraint satisfaction library. The Third Internat. CSP Solver Competition31-40.
[32] Heckman I (2007) Empirical analysis of solution guided multi-point constructive search. Master’s thesis, University of Toronto.
[33] Johnson SM (1954) Optimal two- and three-stage production schedules with setup times included. Naval Res. Logist. Quart. 1:61-68. CrossRef · Zbl 1349.90359
[34] Laborie P (2003) Algorithms for propagating resource constraints in AI planning and scheduling: Existing approaches and new results. Artificial Intelligence 143:151-188. CrossRef · Zbl 1079.68622
[35] Laborie P (2005) Complete MCS-based search: Application to resource constrained project scheduling. Proc. 19th Internat. Joint Conf. Artificial Intelligence (IJCAI’05), Edinburgh, Scotland, 181-186.
[36] Laborie P (2009) IBM ILOG CP optimizer for detailed scheduling illustrated on three problems. Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, LNCS 5547 (Springer, Berlin), 148-162. CrossRef
[37] Lawrence S (1984) Resource constrained project scheduling: An experimental investigation of heuristic scheduling techniques (supplement). Working paper, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, PA.
[38] Lecoutre C, Sais L, Tabary S, Vidal V (2007) Nogood recording from restarts. Proc. 20th Internat. Joint Conf. Artificial Intelligence (IJCAI’07), Hyderabad, India, 131-136.
[39] Le Pape C (1994) Implementation of resource constraints in ILOG SCHEDULE: A library for the development of constraint-based scheduling systems. Intelligent Systems Engrg. 3:55-66. CrossRef
[40] Luby M, Sinclair A, Zuckerman D (1993) Optimal speedup of Las Vegas algorithms. Israel Sympos. Theory Comput. Systems, Jerusalem, Israel, 128-133. CrossRef · Zbl 0797.68139
[41] Malapert A, Cambazard H, Guéret C, Jussien N, Langevin A, Rousseau L-M (2012) An optimal constraint programming approach to the open-shop problem. INFORMS, J. Comput. 24:228-244. Abstract, · Zbl 1460.90089
[42] Martin P, Shmoys DB (1996) A new approach to computing optimal schedules for the job-shop scheduling problem. 5th Internat. Conf. Integer Programming Combin. Optim. (IPCO’96), Lecture Notes in Computer Science, Vol. 1084 (Springer, Berlin), 389-403. CrossRef
[43] Mascis A, Pacciarelli D (2002) Job-shop scheduling with blocking and no-wait constraints. Eur. J. Oper. Res. 143:498-517. CrossRef · Zbl 1082.90528
[44] Morton TE, Pentico DW (1993) Heuristic Scheduling Systems (John Wiley and Sons, New York).
[45] Nowicki E, Smutnicki C (1996) A fast taboo search algorithm for the job shop problem. Management Sci. 42:797-813. Abstract, · Zbl 0880.90079
[46] Nowicki E, Smutnicki C (2005) An advanced Tabu search algorithm for the job shop problem. J. Scheduling 8:145-159. CrossRef · Zbl 1154.90479
[47] Nuijten W (1994) Time and resource constraint scheduling: A constraint satisfaction approach. Ph.D. thesis, Eindhoven University of Technology, Eindhoven, the Netherlands. · Zbl 0837.90068
[48] Ovacik IM, Uzsoy R (1997) Decomposition methods for scheduling semiconductor testing facilities. Internat. J. Flexible Manufacturing Systems 8:357-387.
[49] Peng B, Lu Z, Cheng TCE (2015) A tabu search/path relinking algorithm to solve the job shop scheduling problem. Comput. Oper. Res. 53:154-164. CrossRef · Zbl 1348.90298
[50] Raaymakers WHM, Hoogeveen JA (2000) Scheduling multipurpose batch process industries with no-wait restrictions by simulated annealing. Eur. J. Oper. Res. 126:131-151. CrossRef · Zbl 0970.90034
[51] Rajendran C (1994) A no-wait flowshop scheduling heuristic to minimize makespan. J. Oper. Res. Soc. 45:472-478. CrossRef · Zbl 0799.90060
[52] Refalo P (2004) Impact-based search strategies for constraint programming. Proc. Principles and Practice of Constraint Programming (CP’04), Lecture Notes in Computer Science, Vol. 3258 (Springer, Berlin), 557-571. CrossRef · Zbl 1152.68577
[53] Roy B, Sussman MA (1964) Les problèmes d’ordonnancement avec contraintes disjonctives. Technical Report Note DS 9 bis, SEMA, Paris.
[54] Sadeh NM (1991) Look-ahead techniques for micro-opportunistic job-shop scheduling. Ph.D. thesis, Carnegie Mellon University, Pittsburgh, PA.
[55] Sadeh NM, Fox MS (1996) Variable and value ordering heuristics for the job shop scheduling constraint satisfaction problem. Artificial Intelligence 86:1-41. CrossRef
[56] Sha DY, Hsu C-Y (2008) A new particle swarm optimization for the open shop scheduling problem. Comput. Oper. Res. 35:3243-3261. CrossRef · Zbl 1133.90017
[57] Shaw P (1998) Using constraint programming and local search methods to solve vehicle routing problems. Proc. Principles Practice Constraint Programming (CP’98), Lecture Notes in Computer Science, Vol. 1520 (Springer, Berlin), 417-431. CrossRef
[58] Storer RH, Wu SD, Vaccari R (1992) New search spaces for sequencing problems with application to job shop scheduling. Management Sci. 38:1495-1509. Abstract, · Zbl 0759.90048
[59] Taillard E (1993) Benchmarks for basic scheduling problems. Eur. J. Oper. Res. 64:278-285. CrossRef · Zbl 0769.90052
[60] Torres P, Lopez P (2000) On not-first/not-last conditions in disjunctive scheduling. Eur. J. Oper. Res. 127:332-343. CrossRef · Zbl 0990.90049
[61] van den Broek JJJ (2009) MIP-based approaches for complex planning problems. Ph.D. thesis, Eindhoven University of Technology, Eindhoven, the Netherlands.
[62] Vilím P (2012) Global constraints in scheduling. Ph.D. thesis, Charles University in Prague, Faculty of Mathematics and Physics, Department of Theoretical Computer Science and Logic, Universita Karlova, Praha, Czech Republic, http://vilim.eu/petr/disertace.pdf.
[63] Walsh T (1999) Search in a small world. Proc. 16th Internat. Joint Conf. Artificial Intelligence (IJCAI’99), Stockholm, 1172-1177.
[64] Watson J-P, Beck JC (2008) A hybrid constraint programming/local search approach to the job-shop scheduling problem. Integration AI OR Techniques Constraint Programming Combin. Optim. Problems (CPAIOR’08), Lecture Notes in Computer Science, Vol. 5015 (Springer, Berlin), 263-277. CrossRef · Zbl 1142.68527
[65] Watson J-P, Barbulescu L, Howe AE, Whitley LD (1999) Algorithm performance and problem structure for flow-shop scheduling. Proc. 16th National Conf. Artificial Intelligence (AAAI’99), Orlando, FL, 688-695.
[66] Wismer DA (1972) Solution of the flowshop-scheduling problem with no intermediate queues. Oper. Res. 20:689-697. Abstract, · Zbl 0241.90031
[67] Yamada T, Nakano R (1992) A genetic algorithm applicable to large-scale job-shop problems. Davidor Y, Schwefel H-P, Manner R, eds. Parallel Problem Solving Nature 2 (PPSN-II) (Springer-Verlag, Berlin), 283-292.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.