Incremental propagation rules for a precedence graph with optional activities and time windows

Abstract

Constraint-based scheduling is a powerful tool for solving complex real-life scheduling problems thanks to a natural integration of special solving algorithms encoded in so-called global constraints. Global constraints describe subproblems of the scheduling problem, eg, allocation of activities to a disjunctive resource. Filtering algorithms behind these constraints are used to prune the search space by eliminating options that violate the constraint. The filtering algorithms are frequently expressed in the form of propagation rules that react to some change appearing during problem solving, eg, adding a new precedence relation, by proposing a derived restriction, eg, shrinking a time window. These changes can be invoked by other constraints or they can be a result of some search decision. This paper describes new incremental propagation rules integrating propagation of precedence relations and time windows for activities allocated to a disjunctive resource. Moreover, the rules also cover so-called optional activities that may or may not be present in the final schedule.

Keywords

constraint-based scheduling filtering algorithms optional activities temporal and resource constraints.

Get full access to this article

View all access options for this article.

References

Baptiste, P. and Le Pape, C. 1996: Edge-finding constraint propagation algorithms for disjunctive and cumulative scheduling. Proceedings of the Fifteenth Workshop of the U.K. Planning Special Interest Group (PLANSIG).

Baptiste, P. , Le Pape, C. and Nuijten, W. 2001: Constraint-based scheduling: applying constraint programming to scheduling problems. Kluwer Academic.

Barták, R. and Čepek, O. 2007: Temporal networks with alternatives: complexity and model . Proceedings of the Twentieth International Florida AI Research Society Conference (FLAIRS). AAAI Press, 641-46.

Beck, J. Ch. and Fox, M.S. 1999: Scheduling alternative activities. Proceedings of AAAI-99, 680-87.

Cesta, A. and Stella, C. 1997: A time and resource problem for planning architectures. Recent Advances in AI Planning, LNAI 1348. Springer-Verlag , 117-29.

Dechter, R. 2003: Constraint processing. Morgan Kaufmann .

Focacci, F. , Laborie, P. and Nuijten, W. 2000: Solving scheduling problems with setup times and alternative resources. Proceedings of AIPS 2000.

Garey, M.R. and Johnson, D.S. 1979: Computers and intractability: a guide to the theory of NP-completeness. W.H. Freeman.

Kuster, J. , Jannach, D. and Friedrich, G. 2007: Handling alternative activities in resource-constrained project scheduling problems. Proceedings of Twentieth International Joint Conference on Artificial Intelligence (IJCAI-07), 1960-65.

10.

Laborie, P. 2003: Algorithms for propagating resource constraints in AI planning and scheduling: existing approaches and new results. Artificial Intelligence 143, 151-88.

11.

Laborie, P. and Rogerie, J. 2008: Reasoning with conditional time-intervals. Proceedings of the Twenty-First International Florida AI Research Society Conference (FLAIRS) . AAAI Press, 555-60.

12.

Schulte, C. 2002: Programming constraint services, high-level programming of standard and new constraint services. Springer-Verlag .

13.

Torres, P. and Lopez, P. 1999: : On not-first/ not-last conditions in disjunctive scheduling . European Journal of Operational Research 127, 332-43.

14.

Vilím, P. 2002: Batch processing with sequence dependent setup times: new results. Proceedings of the 4th Workshop of Constraint Programming for Decision and Control, CPDC’02, Gliwice.

15.

Vilím, P. , Barták, R. and Čepek, O. 2005: Extension of O(n . log n) filtering algorithms for the unary resource constraint to optional activities. Constraints 10, 403-25.