Constraint models for complex state transitions
Abstract
Constraint-based scheduling is an approach for solving real-life scheduling problems by combining the generality of AI techniques with the efficiency of OR techniques. Basically, it describes a scheduling problem as a constraint satisfaction problem and then uses constraint satisfaction techniques to find a solution. In this paper we study three constraint models describing complex state transitions that are going beyond the existing models of resources (machines) used in scheduling. These models can naturally handle any setup/changeover/transition scheme as well as special counter constraints imposed on the sequence of activities. The proposed models have been implemented and tested in the commercial scheduling engine of Visopt ShopFloor system.
Keywords
constraint satisfaction, scheduling, machine setups,References
[1] P. Baptiste, C. Le Pape, W. Nuijten. Constraint-Based Scheduling: Applying Constraint Programming to SchedulingProblems. Kluwer Academic Publisher, 2001.
[2] R. Bartak. Conceptual models for combined planning and scheduling. Electronic Notes in Discrete Mathematics,
Volume 4. Elsevier, 1999.
[3] R. Bartak. Dynamic constraint models for planning and scheduling problems. New Trends in Constraints. LNAI
1865, 237- 255. Springer-Verlag, 2000.
[4] R. Bartak. A general relation constraint: an implementation. Proceedings of CP2000 Post- Workshop on Techniques
for Implementing Constraint Programming Systems, 30-40, 2000.
[5] R. Bartak. Filtering algorithms for tabular constraints. Proceedings of CP2001 Workshop CICLOPS, 168- 182,
2001.
