An Optimal Constraint Programming Approach to the Open-Shop Problem

References

• Baptiste P., Le Pape C. Edge-finding constraint propagation algorithms for disjunctive and cumulative scheduling. Proc. 15th Workshop UK Planning Special Interest Group (1996) LiverpoolGoogle Scholar
• Beck J. C., Davenport A. J., Sitarski E. M., Fox M. S. Texture-based heuristics for scheduling revisited. Proc. 14th Natl. Conf. Artificial Intelligence/9th Conf. Innovative Appl. Artificial Intelligence (1997) (AAAI Press, Menlo Park, CA) 241–248Google Scholar
• Blum C. Beam-ACO—Hybridizing ant colony optimization with beam search: An application to open shop scheduling. Comput. Oper. Res. (2005) 32(6):1565–1591Crossref, Google Scholar
• Bräsel H., Tautenhahn T., Werner F. Constructive heuristic algorithms for the open shop problem. Computing (1993) 51(2):95–110Crossref, Google Scholar
• Brucker P., Hilbig T., Hurink J. A branch and bound algorithm for scheduling problems with positive and negative time-lags. (1996) . Technical report, Osnabrück University, Osnabrück, GermanyGoogle Scholar
• Brucker P., Hurink J., Jurisch B., Wöstmann B. A branch and bound algorithm for the open-shop problem. GO-II Meeting: Proc. Second Internat. Colloquium Graphs Optim. (1997) (Amsterdam)43–59Crossref, Google Scholar
• Brucker P., Drexl A., Mohring R., Neumann K., Pesch E. Resource-constrained project scheduling: Notation, classification, models, and methods. Eur. J. Oper. Res. (1999) 112(1):3–41Crossref, Google Scholar
• Carlier J., Pinson E. Adjustment of heads and tails for the job-shop problem. Eur. J. Oper. Res. (1994) 78(2):146–161Crossref, Google Scholar
• Caseau Y., Laburthe F. Disjunctive scheduling with task intervals. (1995) . Technical report, Laboratoire d'Informatique de I'Ecole Normale Superieure, ParisGoogle Scholar
• Cesta A., Oddi A. Gaining efficiency and flexibility in the simple temporal problem. TIME '96: Proc. 3rd Workshop Temporal Representation Reasoning (TIME'96) (1996) (IEEE Computer Society, Washington, DC) 45Crossref, Google Scholar
• Chatzikokolakis K., Boukeas G., Stamatopoulos P., Vouros G. A., Panayiotopoulos T. Construction and repair: A hybrid approach to search in CSPS. SETN 2004, Vol. 3025 (2004) (Springer, Berlin) 342–351Lecture Notes in Artificial IntelligenceGoogle Scholar
• Dechter R.Constraint Processing (2003) (Morgan Kaufmann, San Francisco) Crossref, Google Scholar
• Dorndorf U., Pesch E., Phan-Huy T. Solving the open shop scheduling problem. J. Scheduling (2001) 4(3):157–174Crossref, Google Scholar
• Frigioni D., Miller T., Nanni U., Zaroliagis C. D. An experimental study of dynamic algorithms for transitive closure. ACM J. Experiment. Algorithms (2001) 6Article 9Google Scholar
• Gondran M., Minoux M.Graphs and Algorithms (1984) (John Wiley & Sons, New York) Google Scholar
• Gonzalez T., Sahni S. Open shop scheduling to minimize finish time. J. Assoc. Comput. Machinery (1976) 23(4):665–679Crossref, Google Scholar
• Guéret C. Problèmes d'ordonnancement sans contraintes de précédence. (1997) . Thesis, Université de Technologie de Compiègne, Compiègne, FranceGoogle Scholar
• Guéret C., Prins C. Forbidden intervals for open-shop problems. (1998) . Technical report, École des Mines de Nantes, Nantes, FranceGoogle Scholar
• Guéret C., Prins C. A new lower bound for the open-shop problem. Ann. Oper. Res. (1999) 92:165–183Crossref, Google Scholar
• Guéret C., Jussien N., Prins C. Using intelligent backtracking to improve branch-and-bound methods: An application to open-shop problems. Eur. J. Oper. Res. (2000) 127(2):344–354Crossref, Google Scholar
• Kellerer H., Pferschy U., Pisinger D.Knapsack Problems (2004) (Springer, Berlin) Crossref, Google Scholar
• Kolisch R. Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation. Eur. J. Oper. Res. (1996) 90(2):320–333Crossref, Google Scholar
• Laborie P., Kaelbling L. P., Saffiotti A. Complete MCS-based search: Application to resource constrained project scheduling. Proc. 19th Internat. Joint Conf. Artificial Intelligence (2005) (Professional Book Center, Denver) 181–186Google Scholar
• Le Pape C., Couronné P., Vergamini D., Gosselin V. Time-versus-capacity compromises in project scheduling. Proc. 13th Workshop UK Planning Special Interest Group (1994) Strathclyde, UKGoogle Scholar
• Lecoutre C., Sais L., Tabary S., Vidal V., Veloso M. M. Nogood recording from restarts. Proc. 20th Internat. Joint Conf. Artificial Intelligence (2007) (Morgan Kaufmann, San Francisco) 131–136Google Scholar
• Luby M., Sinclair A., Zuckerman D. Optimal speedup of Las Vegas algorithms. Inform. Processing Lett. (1993) 47(4):173–180Crossref, Google Scholar
• Pearce D. J., Kelly P. H. J. A dynamic topological sort algorithm for directed acyclic graphs. ACM J. Experiment. Algorithms (2006) 11:1–7Google Scholar
• Prins C. Competitive genetic algorithms for the open-shop scheduling problem. Math. Methods Oper. Res. (2000) 52(3):389–411Crossref, Google Scholar
• Sha D. Y., Hsu C.-Y. A new particle swarm optimization for the open shop scheduling problem. Comput. Oper. Res. (2008) 35(10):3243–3261Crossref, Google Scholar
• Taillard E. Benchmarks for basic scheduling problems. Eur. J. Oper. Res. (1993) 64(2):278–285Crossref, Google Scholar
• Tamura N., Taga A., Kitagawa S., Banbara M. Compiling finite linear CSP into SAT. Principles and Practice of Constraint Programming—CP 2006, Vol. 4204 (2006) (Springer, Berlin) 590–603Lecture Notes in Computer ScienceCrossref, Google Scholar
• Vilím P. O(n log n) filtering algorithms for unary resource constraint. CPAIOR 2004, Vol. 3011 (2004) (Springer, Berlin) 335–347Lecture Notes in Computer ScienceCrossref, Google Scholar
• Walsh T. Search in a small world. IJCAI '99: Proc. 16th Internat. Joint Conf. Artificial Intelligence (1999) (Morgan Kaufmann, San Francisco) 1172–1177Google Scholar
• Wu H., van Beek P. On universal restart strategies for backtracking search. Principles and Practice of Constraint Programming CP 2007, Vol. 4741 (2007) (Springer, Berlin) 681–695Lecture Notes in Computer ScienceCrossref, Google Scholar