Metoda zadań zastępczych do rozwiązywania NP-trudnych problemów szeregowania

• Autorzy: Dudek-Dyduch E. , Dutkiewicz L.

Warianty tytułu

EN

Substitution task method for NP-hard scheduling problems

• Konferencja: XV Krajowa Konferencja Automatyzacji Procesów Dyskretnych, Zakopane, 20-23 września 2006r.
• Języki publikacji: PL

Abstrakty

PL

W artykule przedstawiona jest heurystyczna metoda służąca do rozwiązywania skomplikowanych problemów szeregowania. Polega ona na tym, że w każdym stanie procesu decyzja podejmowana jest na podstawie specjalnie skonstruowanego zastępczego zadania optymalizacji. Metoda opisana jest na bazie modelu algebraiczno-logicznego. Opisany został też NP-trudny problem udostępniania pól eksploatacyjnych oraz algorytm jego rozwiązania oparty na proponowanej metodzie.

EN

The paper deals with a heuristic method for complex scheduling problems. According to this method a substitution optimization task is created in each state of the decision process. The method is described with the use of an algebraic-logical model. An NP-hard problem of preparing access to exploitation fields and algorithm for this problem based on the method is also described.

Słowa kluczowe

PL

problem NP-trudny; szeregowanie zadań; metoda zadań zastępczych; model algebraiczno-logiczny

EN

NP-hard; scheduling; substitution task method; algebraic-logical model

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Zeszyty Naukowe. Automatyka / Politechnika Śląska
• Rocznik: 2006
• Tom: z. 143
• Strony: 57--66
• Opis fizyczny: Bibliogr. 14 poz.

Twórcy

autor

Dudek-Dyduch E.

autor

Dutkiewicz L.

• Katedra Automatyki Akademii Górniczo-Hutniczej, 30-059 Kraków, Al. Mickiewicza 30, tel. [phone],

Bibliografia

• 1. Dudek-Dyduch E.: Formalizacja i analiza problematyki dyskretnych procesów produkcyjnych. Zeszyty Nauk. AGH, seria Automatyka, z. 54, Kraków 1990.
• 2. Dudek-Dyduch E.: Dolne ograniczenia algorytmów branch & bound w sterowaniu DPP. Zeszyty Naukowe Politechniki Śląskiej, seria Automatyka, z. 109, 1992, s. 47-56.
• 3. Dudek-Dyduch E.: Optimization of discrete manufacturing processes - branch and bound method. Operations Research' 92, Springer-Verlag, Heidelberg 1992, p. 15-22.
• 4. Dudek-Dyduch E.: Control of discrete event processes - branch and bound method. Prepr. of IFAC/Ifors/Imacs Symposium Large Scale Systems: Theory and Applications, Vol. 2, Chinese Association of Automation, 1992, p. 573- 578.
• 5. Dudek-Dyduch E., Fuchs-Seliger S.: Approximate algorithms for some tasks in management and economy. System, Modelling, Control, No. 7, Vol.1, 1993, p. 148-152.
• 6. Dudek-Dyduch E., Dyduch T.: Formal approach to optimization of discrete manufacturing processes. Proc. of the Twelfth IASTED Int. Conference Modelling, Identification and Control, Acta Press, Zurich 1993, p. 467-468.
• 7. Dudek-Dyduch E.: Learning based algorithm in sheduling. Journal of Intelligent Manufacturing (JIM), Vol. 11, No. 2, Kluwer Academic Publisher, 2000, p. 135-143.
• 8. Dudek-Dyduch E.: Systemy informacyjne zarządzania produkcją. Wydawnictwo Poldex, Kraków 2002.
• 9. Dudek-Dyduch E., Dutkiewicz L., Kucharska E.: Model algebraiczno-logiczny szeregowania zadań z uwzględnieniem transportu maszyn. Automatyka: półrocznik Akademii Górniczo-Hutniczej, t.8, z.3, Kraków 2004, s. 553-562.
• 10. Dudek-Dyduch E., Dutkiewicz L., Kucharska E.: Formalny model symulacji procesów decyzyjnych jako model algebraiczno-logiczny. XI Warsztaty Naukowe PTSK: „Symulacja w badaniach i rozwoju", Polskie Towarzystwo Symulacji Komputerowej, Warszawa 2005, s. 394-402.
• 11. Dudek-Dyduch E., Dyduch T.: Learning algorithms for scheduling using knowledge based model. Lecture Notes in Artificial Inteligence, Vol. 4029, Springer-Verlag 2006 (przyjęte do druku).
• 12. Dutkiewicz L.: Dwupoziomowe algorytmy optymalizacji procesów wytwarzania z zasobami zależnymi od stanu systemu. Praca doktorska, Promotor: prof, dr hab. inż. Ewa Dudek-Dyduch, Kraków 2005.
• 13. Dutkiewicz L., Kucharska E.: Model dla problemu szeregowania zadań z zasobami zależnymi od stanu systemu. Automatyka: półrocznik Akademii Górniczo-Hutniczej, t. 9, z. 1-2, Kraków 2005, s. 67-77.
• 14. Janiak A.: Wybrane problemy i algorytmy szeregowania zadań i rozdziału zasobów, Akademicka Oficyna Wydawnicza PLJ, Warszawa 1999.