Harmonogramowanie zadań i rozdziału zasobów jako problem spełnienia ograniczeń

• Autorzy: Sitek, P. , Wikarek, J. , Bocewicz, G.

Warianty tytułu

EN

CSP approach to scheduling problems

• Konferencja: Konferencja Naukowo-Techniczna Automatyzacja - Nowości i Perspektywy Automation 2007 (11; 14-16.03.2007; Warszawa, Poland)
• Języki publikacji: PL

Abstrakty

PL

W referacie przedstawiono możliwość formalizacji zagadnienia harmonogramowania zadań i rozdziału obciążeń w postaci problemu spełnienia ograniczeń - Constraint Satisfation Problem (CSP). Omówiono podstawowy algorytm CSP oraz techniki propagacji ograniczeń i backtrackingu. Z wykorzystaniem środowiska programowania w logice z ograniczeniami - Constraint Logic Programming (CLP), którego podstawowym zagadnieniem jest CSP, dokonano implementacji systemu wspomagania decyzji harmonogramowania produkcji. System opracowano przy wykorzystaniu pakietu ECLⁱPS^e. W artykule zamieszczono również przykład ilustracyjny wspomagania decyzji harmonogramowania produkcji typu gniazdowego (job-shop).

EN

Scheduling problems can be seen as a special type of Constraint Satisfaction Problem (CSP). This paper presents a formulating of scheduling problems as CSPs. To solve a CSP, different approaches have been developed. These approaches generally use constraint propagation to simplify the original problem and backtracking to directly search for possible solutions. To demonstrate flexibility of CSP approach, the implementation of decision support system for job-shop production based on Constraint Logic Programming (CLP) has been presented.

Słowa kluczowe

PL

harmonogramowanie zadań; rozdział zasobów; problem spełniania ograniczeń; CSP; programowanie w logice z ograniczeniami; CLP

EN

scheduling problem; Constraint Satisfaction Problem; CSP; Constraint Logic Programming; CLP

• Czasopismo: Pomiary Automatyka Robotyka
• Rocznik: 2007
• Tom: R. 11, nr 2
• Opis fizyczny: Bibliogr. 9 poz., rys., pełen tekst na CD

Twórcy

autor

Sitek, P.

• Samodzielny Zakład Systemów Sterowania i Zarządzania, Politechnika Świętokrzyska

autor

Wikarek, J.

• Samodzielny Zakład Systemów Sterowania i Zarządzania, Politechnika Świętokrzyska

autor

Bocewicz, G.

• Katedra Podstaw Informatyki i Zarządzania, Politechnika Koszalińska

Bibliografia

• [1] Janiak A.: Wybrane problemy i algorytmy szeregowania zadań i rozdziału zasobów. Akademicka Oficyna Wydawnicza PLJ, Warszawa 1999.
• [2] Liao S. Y., Wang H. Q., Liao L. J.: An extended formalism to constraint logic programming for decision analysis, Knowledge-based Systems 15, pp 189-202, 2002.
• [3] Ryu U. Young: Constraint logic programming framework for integrated decision supports, Decision Support Systems 22, pp 155-170, 1998.
• [4] M. Mouhoub, F. Charpilet, J. P. Haton: Experimental Analysis of Numeric and Symbolic Constraint Satisfaction Techniques for temporal Reasoning, Constraints, International Journal, 2, pp 151-164, 1998.
• [5] Tsang E. Foundation of Constraint Satisfations, Academic Press, London,1995.
• [6] A. Cesta, A. Oddi: A Constraint-Based Method for Project Scheduling with Time Windows, Journal of Heuristics, 8, pp 109-136, 2002.
• [7] Cheng-Chung Cheng, S. F. Smith: Applying constraint satisfaction techniques to job-shop scheduling, Annals of Operation Research 70, pp 327-357, 1997.
• [8] www.eclipse-clp.org
• [9] Błażewicz J., Cellary W., Słowiński R., Węglarz J. Badania operacyjne dla informatyków. WNT, Warszawa, (1983).