Combining Constraint Programming and Local Search for Job-Shop Scheduling

References

• Balas E., Vazacopoulos A. Guided local search with shifting bottleneck for job shop scheduling. Management Sci. (1998) 44(2):262–275Link, Google Scholar
• Baptiste P., Le Pape C., Nuijten W.Constraint-Based Scheduling (2001) (Kluwer Academic Publishers, Norwell, MA) Crossref, Google Scholar
• Beck J. C. Solution-guided multi-point constructive search for job shop scheduling. J. Artificial Intelligence Res. (2007) 29(1):49–77Crossref, Google Scholar
• Beck J. C., Fox M. S. Dynamic problem structure analysis as a basis for constraint-directed scheduling heuristics. Artificial Intelligence (2000) 117(1):31–81Crossref, Google Scholar
• Błażewicz J., Domschke W., Pesch E. The job shop scheduling problem: Conventional and new solution techniques. Eur. J. Oper. Res. (1996) 93(1):1–33Crossref, Google Scholar
• Boyan J., Moore A. W. Learning evaluation functions to improve optimization by local search. J. Machine Learn. Res. (2000) 1(September):77–112Google Scholar
• Carchrae T., Beck J. C. Applying machine learning to low-knowledge control of optimization algorithms. Comput. Intelligence (2005) 21(4):372–387Crossref, Google Scholar
• Cohen P. R.Empirical Methods for Artificial Intelligence (1995) (MIT Press, Cambridge, MA) Google Scholar
• Garey M. R., Johnson D. S., Sethi R. The complexity of flowshop and jobshop scheduling. Math. Oper. Res. (1976) 1(2):117–129Link, Google Scholar
• Glover F., Laguna M., Martí R., Glover F., Kochenberger G. A. Scatter search and path relinking: Advances and applications. Handbook of Metaheuristics (2003) 57(Kluwer Academic Publishers, Dordrecht, The Netherlands) 1–35Crossref, Google Scholar
• Gomes C. P., Fernández C., Selman B., Bessière C. Statistical regimes across constrainedness regions. Constraints (2005) 10(4):317–337Crossref, Google Scholar
• Hooker J. N. Testing heuristics: We have it all wrong. J. Heuristics (1996) 1:33–42Crossref, Google Scholar
• Horvitz E., Ruan Y., Gomes C. P., Kautz H. A., Selman B., Chickering D. M. A Bayesian approach to tackling hard computational problems. Proc. 17th Conf. Uncertainty Artificial Intelligence (UAI-2001) (2001) (Morgan Kaufmann, San Francisco) 235–244Google Scholar
• Laborie P. Algorithms for propagating resource constraints in AI planning and scheduling: Existing approaches and new results. Artificial Intelligence (2003) 143(2):151–188Crossref, Google Scholar
• Lagoudakis M. G., Littman M. L. Algorithm selection using reinforcement learning. Proc. 17th Internat. Conf. Machine Learning (2000) (Morgan Kaufmann, San Francisco) 511–518Google Scholar
• Le Pape C. Implementation of resource constraints in ILOG SCHEDULE: A library for the development of constraint-based scheduling systems. Intelligent Systems Engrg. (1994) 3(2):55–66Crossref, Google Scholar
• Leyton-Brown K., Nudelman E., Shoham Y., Van Hentenryck P. Learning the empirical hardness of optimization problems: The case of combinatorial auctions. Proc. 8th Internat. Conf. Principles Practice Constraint Programming (CP 2002) (2002) 2470(Springer, Berlin) 91–100Lecture Notes in Computer ScienceCrossref, Google Scholar
• Luby M., Sinclair A., Zuckerman D. Optimal speedup of Las Vegas algorithms. Inform. Processing Lett. (1993) 47(4):173–180Crossref, Google Scholar
• Minton S. Automatically configuring constraint satisfaction programs: A case study. Constraints (1996) 1(1–2):7–43Crossref, Google Scholar
• Nowicki E., Smutnicki C. A fast taboo search algorithm for the job shop problem. Management Sci. (1996) 42(6):797–813Link, Google Scholar
• Nowicki E., Smutnicki C. An advanced tabu algorithm for the job shop problem. J. Scheduling (2005) 8(2):145–159Crossref, Google Scholar
• Nuijten W. P. M. Time and resource constrained scheduling: A constraint satisfaction approach. (1994) . Ph.D. thesis, Department of Mathematics and Computing Science, Eindhoven University of Technology, Eindhoven, The NetherlandsGoogle Scholar
• R Development Core TeamR: A Language and Environment for Statistical Computing (2009) (R Foundation for Statistical Computing, Vienna) . http://www.R-project.orgGoogle Scholar
• Rice J. R. The algorithm selection problem. Adv. Comput. (1976) 15:65–118Crossref, Google Scholar
• Scheduler ILOG Scheduler 6.5 user's manual and reference manual. (2007) . IBM ILOG, Armonk, NYGoogle Scholar
• Smith S. F., Cheng C.-C. Slack-based heuristics for constraint satisfaction scheduling. Proc. 11th National Conf. Artificial Intelligence (AAAI-93) (1993) (AAAI, Washington, DC) 139–144Google Scholar
• Sutton R. S., Barto A. G.Reinforcement Learning: An Introduction (1998) (MIT Press, Cambridge, MA) Google Scholar
• Taillard É. D. Parallel taboo search technique for the jobshop scheduling problem. (1989) . Technical Report ORWP 89/11, DMA, Ecole Polytechnique Fédérale de Lausanne, Lausanne, SwitzerlandGoogle Scholar
• Taillard É. D. Éric Taillard's page. (2008) . http://mistic.heig-vd.ch/taillard/problemes.dir/ordonnancement.dir/ordonnancement.htmlGoogle Scholar
• Taillard E. D. Benchmarks for basic scheduling problems. Eur. J. Oper. Res. (1993) 64(2):278–285Crossref, Google Scholar
• Watson J.-P. Empirical modeling and analysis of local search algorithms for the job-shop scheduling problem. (2003) . Ph.D. thesis, Department of Computer Science, Colorado State University, Fort CollinsGoogle Scholar
• Watson J.-P. On metaheuristic “failure modes”: A case study in tabu search for job-shop scheduling. Proc. 6th Metaheuristics Internat. Conf. (2005) ViennaGoogle Scholar
• Watson J.-P., Beck J. C., Perron L., Trick M. A. A hybrid constraint programming/local search approach to the job shop scheduling problem. Proc. 5th Internat. Conf. Integration AI OR Techniques Constraint Programming Combin. Optim. Problems (CPAIOR'08) (2008) 5015(Springer, Berlin) 263–277Lecture Notes in Computer ScienceCrossref, Google Scholar
• Watson J.-P., Howe A. E., Whitley L. D. Deconstructing Nowicki and Smutnicki's i-TSAB tabu search algorithm for the job-shop scheduling problem. Comput. Oper. Res. (2006) 33(9):2623–2644Crossref, Google Scholar
• Wu H., van Beek P., Bessiene C. On universal restart strategies for backtracking search. Proc. 13th Internat. Conf. Principles Practice Constraint Programming (2007) 4741(Springer, Berlin) 681–695Lecture Notes in Computer ScienceCrossref, Google Scholar
• Zhang C. Y., Li P., Rao Y., Guan Z. A very fast TS/SA algorithm for the job shop scheduling problem. Comput. Oper. Res. (2008) 35(1):282–294Crossref, Google Scholar