Constraint models for complex state transitions

• Autorzy: Barták R.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

constraint satisfaction; scheduling; machine setups

PL

automatyzacja

• Wydawca: Instytut Podstawowych Problemów Techniki PAN
• Czasopismo: Computer Assisted Mechanics and Engineering Sciences
• Rocznik: 2007
• Tom: Vol. 14, No. 4
• Strony: 543--555
• Opis fizyczny: Bibliogr. 12 poz., rys.

Twórcy

autor

Barták R.

• Charles University, Faculty of Mathematics and Physics, Malostranské nám. 2/25, 118 00 Praha 1, Czech Republic

Bibliografia

• [1] P. Baptiste, C. Le Pape, W. Nuijten. Constraint-Based Scheduling: Applying Constraint Programming to Scheduling Problems. 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.
• [6] R. Bartak. Visopt ShopFloor: On the edge of planning and scheduling. Principles and Practice of Constraint Programming - CP2002. LNCS 2470, 587-602. Springer-Verlag, 2002.
• [7] R. Bartak. Modelling resource transitions in constraint-based scheduling. Proceedings of SOFSEM 2002: Theory and Practice of Informatics. LNCS 2540, 186-194. Springer-Verlag, 2002.
• [8] J. Ch. Beck, M.S. Fox. Scheduling alternative activities. Proceedings of AAAI-99, 680-687. AAAI Press, 1999.
• [9] P. Brucker. Scheduling Algorithms. Springer-Verlag, 2001.
• [10] V. Brusoni, L. Console, E. Lamma, P. Mello, M. Milano, P. Terenziani. Resource-based vs. task-based approaches for scheduling problems. Proceedings of the 9th ISMIS96. LNCS Series, Springer-Verlag, 1996.
• [11] M. Carlsson, G. Ottosson, B. Carlson. An open-ended finite domain constraint solver. Proceedings ProgrammingLanguages: Implementations, Logics, and Programs, 1997.
• [12] R. Dechter. Constraint Processing. Morgan Kaufmann, 2003.