Solving Variants of the Job Shop Scheduling Problem Through Conflict-Directed Search

References

• Adams J, Balas E, Zawack D (1988) The shifting bottleneck procedure for job shop scheduling. Management Sci. 34:391–401.Link, Google Scholar
• Applegate D, Cook W (1991) A computational study of the job-shop scheduling problem. INFORMS J. Comput. 3:149–156.Link, Google Scholar
• 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, Google Scholar
• 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, Google Scholar
• 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.Google Scholar
• 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.Google Scholar
• 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, Google Scholar
• Beck JC (2007) Solution-guided multi-point constructive search for job shop scheduling. J. Artificial Intelligence Res. 29:49–77.Crossref, Google Scholar
• Beck JC, Refalo P (2003) A hybrid approach to scheduling with earliness and tardiness costs. Ann. Oper. Res. 118:49–71.Crossref, Google Scholar
• 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.Google Scholar
• 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.Google Scholar
• 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, Google Scholar
• 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, Google Scholar
• Bürgy R, Gröflin H (2012) Optimal job insertion in the no-wait job shop. J. Combin. Optim. 26:345–371.Crossref, Google Scholar
• Carlier J (1978) Ordonnancements à contraintes disjonctives. R.A.I.R.O Recherche Opérationelle/Oper. Res. 12:333–350.Google Scholar
• Carlier J, Pinson E (1989) An algorithm for solving the job-shop problem. Management Sci. 35:164–176.Link, Google Scholar
• Carlier J, Pinson E (1994) Adjustment of heads and tails for the job-shop problem. Eur. J. Oper. Res. 78:146–191.Crossref, Google Scholar
• Caumond A, Lacomme P, Tchernev N (2008) A memetic algorithm for the job-shop with time-lags. Comput. Oper. Res. 35:2331–2356.Crossref, Google Scholar
• 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, Google Scholar
• Dechter R, Meiri I, Pearl J (1991) Temporal constraint networks. Artificial Intelligence 49:61–95.Crossref, Google Scholar
• 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.Google Scholar
• Fox MS, Sadeh NM, Baykan CA (1989) Constrained heuristic search. Proc. 11th Internat. Joint Conf. Artificial Intelligence (IJCAI’89), Detroit, 309–315.Google Scholar
• Geelen PA (1992) Dual viewpoint heuristics for binary constraint satisfaction problems. Proc. 10th Eur. Conf. Artificial Intelligence (ECAI’92), Vienna, 31–35.Google Scholar
• Gini C (1912) Variabilita e mutabilita contributo allo studio della distribuzioni. Studie Economico-Guiridici della R. Universita di Cagliari 3:1–158.Google Scholar
• 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.Google Scholar
• 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.Google Scholar
• 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, Google Scholar
• 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, Google Scholar
• 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, Google Scholar
• Guéret C, Prins C (1999) A new lower bound for the open-shop problem. Ann. Oper. Res. 92:165–183.Crossref, Google Scholar
• Hebrard E (2008) Mistral, a constraint satisfaction library. The Third Internat. CSP Solver Competition 31–40.Google Scholar
• Heckman I (2007) Empirical analysis of solution guided multi-point constructive search. Master’s thesis, University of Toronto.Google Scholar
• Johnson SM (1954) Optimal two- and three-stage production schedules with setup times included. Naval Res. Logist. Quart. 1:61–68.Crossref, Google Scholar
• Laborie P (2003) Algorithms for propagating resource constraints in AI planning and scheduling: Existing approaches and new results. Artificial Intelligence 143:151–188.Crossref, Google Scholar
• 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.Google Scholar
• 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, Google Scholar
• 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.Google Scholar
• 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.Google Scholar
• 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, Google Scholar
• Luby M, Sinclair A, Zuckerman D (1993) Optimal speedup of Las Vegas algorithms. Israel Sympos. Theory Comput. Systems, Jerusalem, Israel, 128–133.Crossref, Google Scholar
• 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.Link, Google Scholar
• 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, Google Scholar
• Mascis A, Pacciarelli D (2002) Job-shop scheduling with blocking and no-wait constraints. Eur. J. Oper. Res. 143:498–517.Crossref, Google Scholar
• Morton TE, Pentico DW (1993) Heuristic Scheduling Systems (John Wiley and Sons, New York).Google Scholar
• Nowicki E, Smutnicki C (1996) A fast taboo search algorithm for the job shop problem. Management Sci. 42:797–813.Link, Google Scholar
• Nowicki E, Smutnicki C (2005) An advanced Tabu search algorithm for the job shop problem. J. Scheduling 8:145–159.Crossref, Google Scholar
• Nuijten W (1994) Time and resource constraint scheduling: A constraint satisfaction approach. Ph.D. thesis, Eindhoven University of Technology, Eindhoven, the Netherlands.Google Scholar
• Ovacik IM, Uzsoy R (1997) Decomposition methods for scheduling semiconductor testing facilities. Internat. J. Flexible Manufacturing Systems 8:357–387.Google Scholar
• 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, Google Scholar
• 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, Google Scholar
• Rajendran C (1994) A no-wait flowshop scheduling heuristic to minimize makespan. J. Oper. Res. Soc. 45:472–478.Crossref, Google Scholar
• 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, Google Scholar
• Roy B, Sussman MA (1964) Les problèmes d’ordonnancement avec contraintes disjonctives. Technical Report Note DS 9 bis, SEMA, Paris.Google Scholar
• Sadeh NM (1991) Look-ahead techniques for micro-opportunistic job-shop scheduling. Ph.D. thesis, Carnegie Mellon University, Pittsburgh, PA.Google Scholar
• Sadeh NM, Fox MS (1996) Variable and value ordering heuristics for the job shop scheduling constraint satisfaction problem. Artificial Intelligence 86:1–41.Crossref, Google Scholar
• Sha DY, Hsu C-Y (2008) A new particle swarm optimization for the open shop scheduling problem. Comput. Oper. Res. 35:3243–3261.Crossref, Google Scholar
• 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, Google Scholar
• Storer RH, Wu SD, Vaccari R (1992) New search spaces for sequencing problems with application to job shop scheduling. Management Sci. 38:1495–1509.Link, Google Scholar
• Taillard E (1993) Benchmarks for basic scheduling problems. Eur. J. Oper. Res. 64:278–285.Crossref, Google Scholar
• Torres P, Lopez P (2000) On not-first/not-last conditions in disjunctive scheduling. Eur. J. Oper. Res. 127:332–343.Crossref, Google Scholar
• van den Broek JJJ (2009) MIP-based approaches for complex planning problems. Ph.D. thesis, Eindhoven University of Technology, Eindhoven, the Netherlands.Google Scholar
• 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.Google Scholar
• Walsh T (1999) Search in a small world. Proc. 16th Internat. Joint Conf. Artificial Intelligence (IJCAI’99), Stockholm, 1172–1177.Google Scholar
• 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, Google Scholar
• 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.Google Scholar
• Wismer DA (1972) Solution of the flowshop-scheduling problem with no intermediate queues. Oper. Res. 20:689–697.Link, Google Scholar
• 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.Google Scholar