Skip to main content
Log in

Probe Backtrack Search for Minimal Perturbation in Dynamic Scheduling

  • Published:
Constraints Aims and scope Submit manuscript

Abstract

This paperdescribes an algorithm designed to minimally reconfigure schedulesin response to a changing environment. External factors havecaused an existing schedule to become invalid, perhaps due tothe withdrawal of resources, or because of changes to the setof scheduled activities. The total shift in the start and endtimes of already scheduled activities should be kept to a minimum.This optimization requirement may be captured using a linearoptimization function over linear constraints. However, the disjunctivenature of the resource constraints impairs traditional mathematicalprogramming approaches. The unimodular probing algorithm interleavesconstraint programming and linear programming. The linear programmingsolver handles only a controlled subset of the problem constraints,to guarantee that the values returned are discrete. Using probebacktracking, a complete, repair-based method for search, thesevalues are simply integrated into constraint programming. Unimodularprobing is compared with alternatives on a set of dynamic schedulingbenchmarks, demonstrating its effectiveness.

In the final discussion, we conjecture that analogous probebacktracking strategies may obtain performance improvements overconventional backtrack algorithms for a broad range of constraintsatisfaction and optimization problems.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. A. Abderrahmane and N. Beldiceanu. (1992). Extending CHIP in order to solve complex scheduling and placement problems. Premières Journées Francophones sur la Programation en Logique.

  2. M. Bartusch, R. H. Möhring, and F. J. Radermacher. (1988). Scheduling project networks with resource constraints and time windows. Annals of Operations Research, 16: 201-240.

    Google Scholar 

  3. H. Beringer and B. de Backer. (1993). Satisfiability of boolean formulas over linear constraints. In IJCAI-93, pp. 296-301, Chambéry, France.

  4. E. G. Coffman Jr., M. R. Garey, and D. S. Johnson. (1984). Approximation algorithms for bin-packing-an updated survey. In G. Ausiello, M. Lucertini, and P. Serafini, editors, Algorithm Design for Computer System Design, pp. 49-106. Springer-Verlag.

  5. A. Davenport. (1998). Managing uncertainty in scheduling: a survey. Working Draft.

  6. R. Dechter and A. Dechter. (1988). Belief maintenance in dynamic constraint networks. In Proceedings of AAAI-88, pp. 37-42.

  7. R. Dechter and J. Pearl. (1988). Network-based heuristics for constraint satisfaction problems. Artificial Intelligence, 34.

  8. R. Dechter, I. Meiri, and J. Pearl. (1991). Temporal constraint networks. Artificial Intelligence, 49: 61-95.

    Google Scholar 

  9. A. El-Kholy and B. Richards. (1996). Temporal and resource reasoning in planning: The parc PLAN approach. In Proceedings of the 11th European Conference on Artificial Intelligence, ECAI-96, pp. 614-618, Budapest, Hungary.

  10. A. O. El-Kholy. (1996). Resource Feasibility in Planning. Ph.D. thesis, Imperial College, University of London.

  11. H. El Sakkout, T. Richards, and M.Wallace. (1997). Unimodular probing for minimal perturbance in dynamic resource feasibility problems. In Proceedings of the CP97 workshop on Dynamic Constraint Satisfaction.

  12. H. El Sakkout, T. Richards, and M. Wallace. (1998). Minimal perturbation in dynamic scheduling. In Proceedings of the 13th European Conference on Artificial Intelligence, ECAI-98, Brighton, UK, 1998.

  13. M. S. Fox. (1987). Constraint-directed search: a case study of job-shop scheduling. Morgan Kaufmann Publishers Inc.

  14. S. French. (1982). Sequencing and Scheduling: An introduction to the Mathematics of the Job-Shop. Ellis Horwood, England.

    Google Scholar 

  15. M. R. Garey and D. S. Johnson. (1979). Computers and Intractability: A Guide to the Theory of NPCompleteness. Bell Telephone Laboratories, Inc.

  16. R. S. Garfinkel and G. L. Nemhauser. (1972). Integer Programming. John Wiley & Sons.

  17. I. Heller and C.B.Tompkins. (1956). An extension of a theorem of Dantzig's. In Kuhn and Tucker, editors, Linear Inequalities and Related Systems, pp. 247-254. Princeton University Press.

  18. D.W. Hildum. (1994). Flexibility in a Knowledge-Based System for Solving Dynamic Resource-Constrained Scheduling Problems. Ph.D. thesis, Dept. of Computer Science, University of Massachusetts, Amherst. 19. J. N. Hooker and M. A. Osorio. (1996). Mixed logical/linear programming. Discrete Applied Mathematics (to appear). Electronic copy available from first author's home page: <http://www.gsia.cmu.edu/afs/andrew.cmu.edu/gsia/jh38/papers.html>.

    Google Scholar 

  19. N. Karmarkar. (1984). A new polynomial-time algrithm for linear programming. Combinatorica, 4(4): 373-395.

    Google Scholar 

  20. L. G. Khachian. (1979).Apolynomial algorithm in linear programming. Soviet Math. Dokl., 20(1): 191-194.

    Google Scholar 

  21. C. Le Pape, P. Couronné, D. Vergamini, and V. Gosselin. (1994). Time-versus-capacity compromises in project scheduling. In Proceedings of the 13th Workshop of the UK Planning and Scheduling SIG, Glasgow, Scotland.

  22. V. J. Leon, S. D. Wu, and R. H. Storer. (1994). Robustness measures and robust scheduling for job shop. IIE Transactions, 26(5): 32-43.

    Google Scholar 

  23. Olivier Lhomme. (1993). Consistency techniques for numeric csps. In Proceedings of the 13th International Joint Conference on Artificial Intelligence, IJCAI-93, pp. 232-238, Chambéry, France.

  24. V. Liatsos. (1998). Short term scheduling. Presentation at the DIMACS Workshop on Constraint Programming and Large-Scale Discrete Optimization, Rutgers University, NJ.

  25. S. Minton, M. D. Johnston, A. B. Philips, and P. Laird. (1992). Minimizing conflicts: a heuristic repair method for constraint satisfaction and scheduling problems. Artificial Intelligence, 58: 161-205.

    Google Scholar 

  26. W. Nuijten and E. Aarts. (1994). Constraint satisfaction for multiple capacitated job shop scheduling. In Proceedings of the 11th European Conference on Artificial Intelligence, ECAI-94. JohnWiley & Sons, Ltd.

  27. Wim Nuijten. (1994). Time and Resource Constrained Scheduling: A constraint satisfaction approach. PhD thesis, Eindhoven University of Technology.

  28. D. Pothos. (1997). A constraint-based approach to the british airways schedule re-timing problem. Technical Report 97/04-01, IC-Parc, Imperial College.

  29. P. W. Purdom, Jr. and G. N. Haven. (1997). Probe order backtracking. Siam Journal of Computing, 26: 456-483.

    Google Scholar 

  30. M. Queyranne and Y. Wang. (1991). Single-machine scheduling polyhedra with precedence constraints. Mathematics of Operations Research, pp. 1-20.

  31. N. Sadeh. (1994). Micro-opportunistic scheduling: The micro-boss factory scheduler. In M. Zweben and M. Fox, editors, Intelligent Scheduling, chapter 4, pp. 99-136. Morgan Kaufman.

  32. G. Verfaillie and T. Schiex. (1994). Solution reuse in dynamic constraint satisfaction problems. In AAAI-94, pp. 307-312, Seattle, WA.

  33. M. Yokoo. (1994). Weak-commitment search for solving constraint satisfaction problems. In AAAI-94, pp. 313-318, Seattle, WA.

Download references

Author information

Authors and Affiliations

Authors

Rights and permissions

Reprints and permissions

About this article

Cite this article

Sakkout, H.E., Wallace, M. Probe Backtrack Search for Minimal Perturbation in Dynamic Scheduling. Constraints 5, 359–388 (2000). https://doi.org/10.1023/A:1009856210543

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1009856210543

Navigation