Constraint-based scheduling in Oz/Mozart

• Autorzy: Sitek P. , Wikarek J. , Banaszak Z.
• Języki publikacji: EN

Abstrakty

EN

In this paper we present how scheduling problems can be solved in the concurrent constraint programming (CCP) language Oz. Oz is the first high- level constraint language, which offers programmable search, modularity, expressiveness and an interface to invent new constraints using C++. As an example of scheduling problem the job-shop scheduling problem with manpower resources representation was considered. The objective discussed here is the minimization of the makespan. Allocating manpower to the jobs is more complicated than allocating machines, as different jobs and operations require different manpower. This problem is strongly NP-hard. We proposed the constraint programming (CP) based approach to decision support in this environment. The most important features of CP are declarative problem modeling, allowing a clear separation between the problem statement (variables and constraints) and the resolution of the problem.

Słowa kluczowe

EN

constraint programming; decision support; scheduling

• Wydawca: Polskie Towarzystwo Promocji Wiedzy ; Lublin University of Technology
• Czasopismo: Applied Computer Science
• Rocznik: 2006
• Tom: Vol. 2, no 1
• Strony: 83--99
• Opis fizyczny: Bibliogr. 10 poz., fig., tab.

Twórcy

autor

Sitek P.

• Technical University of Kielce, Department of Electric Engineering, Automation and Computer Science, Control and Management Systems Section, 1000-PP 7, Kielce

autor

Wikarek J.

• Technical University of Kielce, Department of Electric Engineering, Automation and Computer Science, Control and Management Systems Section, 1000-PP 7, Kielce

autor

Banaszak Z.

• Department of Computer Science and Management, Technical University of Koszalin, Sniadeckich 2, 75-453 Koszalin

Bibliografia

• [1] JÓZEFOWSKA J.: Discrete-continuous project scheduling, Project Driven Manufacturing, WNT, Warszawa 2003, pp. 7-22.
• [2] JÓZEFOWSKA J., RÓŻYCKI R., WĘGLARZ J.: Uncertainty in discrete-continuous project scheduling Project Driven Manufacturing, WNT, Warszawa 2003, pp. 23-33.
• [3] MIKA M., WALIGÓRA G., WĘGLARZ J.: Metaheuristic approach to the multi-mode resource-constrained project scheduling problem with discounted cash flows and progress payments, WNT, Warszawa 2003, pp 34-53.
• [4] FRENCH S.: Sequencing and Scheduling: An Introduction to the Mathematics of Job-shop. Chichester:Ellis Horwood, 1982.
• [5] PAPE C.Le.: Three Mechanisms for Managing Resource Constraints in a Library for Constraint-Based Scheduling Proceedings INRIA/IEEE Conference on Emerging Technologies and Factory Automation, 1995.
• [6] www.mozart-oz.org/
• [7] WÜRTZ J.: Constraint-Based Scheduling in Oz,. Operations Research Proceedings 1996, Berlin, Heidelberg, New York, Springer-Verlag, pp. 218-223.
• [8] SITEK P., BANASZAK Z., MUSZYŃSKI W.: Application of CLP to Prototyping Shop Orders in Small and Medium-Sized Enterprises MMAR 11th IEEE International Conference on Methods and Models in Automation and Robotics. Międzyzdroje 2005, pp 1091–1096.
• [9] MARTIN P., SHMOYS D. B.: A new approach to computing optimal schedules for the job shop scheduling problem. In International Conference on Integer Programming and Combinatorial Optimization, Vancouver, pp. 1996, 389-403.
• [10] BANASZAK Z., JÓZEFCZYK J.: Towards dedicated decision support tools: CLP-based approach. Applied Computer Science and Production Management. Vol.1, No 1, 2005, pp. 161-180.