Abstract
We introduce constraint-based scheduling and discuss its main principles. An approximation algorithm based on tree search is developed for the job shop scheduling problem using ILOG SCHEDULER. A new way of calculating lower bounds on the makespan of the job shop scheduling problem is presented and we show how such results can be used within a constraint-based approach. An empirical performance analysis shows that the algorithm we developed performs well. Finally, taking the job shop scheduling problem as a start point, we discuss how constraint-based scheduling can be used to solve more general scheduling problems.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Aarts, E.H.L., P.J.M. van Laarhoven, J.K. Lenstra, and N.J.L. Ulder. (1994). "A Computational Study of Local Search Algorithms for Job Shop Scheduling," ORSA Journal on Computing 6, 113–125.
Adams, J., E. Balas, and D. Zawack. (1988). "The Shifting Bottleneck Procedure for Job Shop Scheduling," Management Science 34, 391–401.
Aggoun, A. and N. Beldiceanu. (1993). "Extending Chip in Order to Solve Complex Scheduling and Placement Problems," Mathematical and Computer Modelling 17, 57–73.
Applegate, D. andW. Cook. (1991). "AComputational Study of the Job-Shop Scheduling Problem," ORSA Journal on Computing 3, 149–156.
Baker, K.R. (1974). Introduction to Sequencing and Scheduling. Wiley & Sons.
Balas, E. and A. Vazacopoulos. (1995). "}Guided Local Search with Shifting Bottleneck for Job-Shop Scheduling," Management Science Research Report MSRR-609(R), Carnegie Mellon University, Pittsburgh.
Baptiste, P. and C. Le Pape. (1996). "Edge-Finding Constraint Propagation Algorithms for Disjunctive and Cummulative Scheduling," Proc. 15th Workshop of the U.K. Planning Special Interest Group.
Baptiste, P., C. Le Pape, and W. Nuijten. (1995). "Constraint-Based Optimization and Approximation for Job Shop Scheduling," Proc. IJCAI'95 Workshop on Intelligent Manufacturing Systems.
Barnes, J.W. and J.B. Chambers. (1994). "Solving the Job Shop Scheduling Problem Using Tabu Search," IEEE Transactions 27/2, 257–263.
Blazewicz, J., W. Domschke, and E. Pesch. (1996). "The Job Shop Scheduling Problem: Conventional and New Solution Techniques," European Journal of Operational Research 91, 1–33.
Brucker, P., B. Jurisch, and B. Sievers. (1994). "A Branch and Bound Algorithm for the Job-Shop Scheduling Problem," Discrete Applied Mathematics 49, 107–127.
Carlier, J. and E. Pinson. (1989). "An Algorithm for Solving the Job-Shop Problem," Management Science 35, 164–176.
Carlier, J. and E. Pinson. (1994). "Adjustment of Heads and Tails for the Job-Shop Problem," European Journal of Operational Research 78, 146–161.
Caseau, Y. and F. Laburthe. (1994). "Improved CLP Scheduling with Task Intervals," Proc. 11th International Conference on Logic Programming.
Caseau,Y. and F. Laburthe. (1995). "Disjunctive Scheduling with Task Intervals," Technical Report, Ecole Normale Superieure.
Dechter, R. (1992). "Constraint Networks." In S.C. Shapiro (ed.), Encyclopedia of Artificial Intelligence. John Wiley & Sons, second edition, vol. 1, pp. 276–285.
Dell'Amico, M. and M. Trubian. (1993). "Applying Tabu-Search to the Job-Shop Scheduling Problem," Annals of Operations Research 41, 231–252.
Dorndorf, U. and E. Pesch. (1995). "Evolution Based Learning in a Job Shop Scheduling Environment," Computers and Operations Research 22, 25–40.
Ford, Jr., L.R. (1956). "Network Flow Theory," Technical report, Rand Corporatio
Garey, M.R. and D.S. Johnson. (1979). Computers and Intractability; A Guide to the Theory of NP-Completeness. New York: W.H. Freeman and Company.
Garey, M.R., D.S. Johnson, and R. Sethi. (1976). "The Complexity of Flowshop and Job-Shop Scheduling," Mathematics of Operations Research 1, 117–129.
Gondran, M. and M. Minoux. (1984). Graphs and Algorithms. John Wiley and Sons.
Haupt, R. (1989). "A Survey of Priority Rule-Based Scheduling," OR Spektrum 11, 3–16.
Hentenryck, P. van. (1989). Constraint Satisfaction in Logic Programming. MIT Press.
Kumar, V. (1992). "Algorithms for Constraint-Satisfaction Problems: A Survey," AI Magazine 13, 32–44.
Laarhoven, P.J.M. van, E.H.L. Aarts, and J.K. Lenstra}. (1992). "Job Shop Scheduling by Simulated Annealing}," Operations Research} 40}, 113–
Le Pape, C. (1994). "Implementation of Resource Constraints in ILOG SCHEDULE: A Library for the Development of Constraint-Based Scheduling Systems," Intelligent Systems Engineering 3, 55–66.
Le Pape, C. and P. Baptiste. (1996). "Constraint Propagation Techniques for Disjunctive Scheduling: The Preemptive Case," Proc. 12th European Conference on Artificial Intelligence.
Le Pape, C., P. Couronné, D. Vergamini, and V. Gosselin. (1995). "Time-Versus-Capacity Compromises in Project Scheduling," AISB Quarterly 91, 19–31.
Martin, P.D. (1996). "A Time-Oriented Approach to Computing Optimal Schedules for the Job-Shop Scheduling Problem," Ph.D. Thesis, School of Operations Research and Industrial Engineering, Cornell University.
Matsuo, H., C.J. Suh, and R.S. Sullivan. (1988). "A Controlled Search Simulated Annealing Method for the General Job Shop Scheduling Problem," Working Paper 03-04-88, Graduate School of Business, University of Texas at Austin, Austin, USA.
Nowicki, E. and C. Smutnicki. (1993). "A Fast Taboo Search Algorithm for the Job Shop Problem," Preprinty nr 8/93. Instytut Cybernetyki Technicznej, Politechnicki Wroclawskiej, Poland.
Nowicki, E. and C. Smutnicki. (1996). "A Fast Taboo Search Algorithm for the Job Shop Problem," Management Science 42, 797–813.
Nuijten, W.P.M. (1994). "Time and Resource Constrained Scheduling: A Constraint Satisfaction Approach," Ph.D. Thesis. Eindhoven University of Technology.
Nuijten, W.P.M. and E.H.L. Aarts. (1996). "A Computational Study of Constraint Satisfaction for Multiple Capacitated Job Shop Scheduling," European Journal of Operational Research 90, 269–284.
Panwalkar, S.S. and W. Iskander. (1977). "A Survey of Scheduling Rules," Operations Research 25, 45–61.
Puget, J.-F. (1994). "A C++ Implementation of CLP," Technical Report 94-01. ILOG S.A., Gentilly, France.
Smith, S.F. and C.-C. Cheng. (1993). "Slack-Based Heuristics for Constraint Satisfaction," Proc. 11th National Conference on Artificial Intelligence.
Taillard, E. (1994). "Parallel Taboo Search Techniques for the Job Shop Scheduling Problem," ORSA Journal on Computing 6, 108–117.
Vaessens, R.J.M., E.H.L. Aarts, and J.K. Lenstra. (1994). "Job Shop Scheduling by Local Search," COSOR Memorandum 94-05, Eindhoven University of Technology.
Zweben, M. and M. Fox (eds.) (1994). Intelligent Scheduling. New York: Morgan Kauffman.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Nuijten, W., Le Pape, C. Constraint-Based Job Shop Scheduling with IILOG SCHEDULER . Journal of Heuristics 3, 271–286 (1998). https://doi.org/10.1023/A:1009687210594
Issue Date:
DOI: https://doi.org/10.1023/A:1009687210594