Heurystyczne przeszukiwanie drzewa rozwiązań dla problemu szeregowania na maszynach równoległych

• Autorzy: Kucharska E. , Dutkiewicz L.

Warianty tytułu

EN

Heuristic search of solution tree for scheduling problem with parallel machines

• Języki publikacji: PL

Abstrakty

PL

Celem artykułu jest przedstawienie algorytmu wykorzystującego heurystyczne przeszukiwanie drzewa rozwiązań. Został on opracowany do rozwiązywania problemów szeregowania zadań na wielu maszynach. Algorytm ten wykorzystuje model przestrzeni stanów i oparty jest na modelu algebraiczno-logicznym. Polega na generowaniu trajektorii, a następnie poprawianiu końcowych odcinków znalezionej trajektorii. Do wyboru decyzji w kolejnych stanach trajektorii wykorzystuje optymalizację lokalną. W artykule opisany został specyficzny problem szeregowania zadań z przezbrojeniami na maszynach równoległych, do którego proponowany algorytm został zastosowany. Opisana została postać kryterium lokalnego dla tego problemu i sposób wyboru stanu, od którego będzie poprawiana trajektoria. Przedstawione i omówione zostały wyniki eksperymentów.

EN

The aim of the paper is to present an algorithm, in which heuristics search of solution tree is applied. This algorithm is designed for task scheduling problems on multiple machines. It uses state space representation and is based on an algebraic-logical model. The proposed algorithm consists in constructing a trajectory and then improving terminal parts of the constructed trajectory. Decision choosing in the algorithm is based on local optimization. In the article a specific scheduling problem with parallel machines is described. For this problem there is given a structure of local criterion and a method of choosing a state from which the trajectory will be improved. Results of experiment are also presented.

Słowa kluczowe

PL

model algebraiczno-logiczny; przeszukiwanie heurystyczne; graf stanów

EN

algebraic-logical model; heuristic search; state graph

• Wydawca: Wydawnictwa AGH
• Czasopismo: Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
• Rocznik: 2008
• Tom: T. 12, z. 3
• Strony: 945--956
• Opis fizyczny: . Bibliogr. 7 poz., tab.

Twórcy

autor

Kucharska E.

• Katedra Automatyki, Akademia Górniczo-Hutnicza w Krakowie

autor

Dutkiewicz L.

• Katedra Automatyki, Akademia Górniczo-Hutnicza w Krakowie

Bibliografia

• [1] Bubnicki Z., Wstęp do systemów ekspertowych. Warszawa, PWN 1990.
• [2] Dudek-Dyduch E., Formalizacja i analiza problematyki dyskretnych procesów produkcyjnych. Zeszyty Naukowe AGH Automatyka, z. 54, 1990 (praca habilitacyjna).
• [3] Dudek-Dyduch E., Learning based algorithm in scheduling. Cluver Academic Publishers, Journal of Intelligent Manufacturing (JIM), vol. 11, no 2, 2000, 135-143.
• [4] Dudek-Dyduch E., Dutkiewicz L., Kucharska E., Model algebraiczno-logiczny szeregowania zadań z uwzględnieniem transportu maszyn. Automatyka (półrocznik AGH), t. 8, z. 3, 2004, 553-562.
• [5] Dudek-Dyduch E., Dutkiewicz L., Kucharska E., Algorytmy z szacowaniem kosztów w kryterium lokalnym dla problemu szeregowania zadań. Automatyka (półrocznik AGH), t. 11 z. 3, 2007, 383-395.
• [6] Janiak A., Wybrane problemy i algorytmy szeregowania zadań i rozdziału zasobów. Warszawa, Akademicka Oficyna Wydawnicza PLJ 1999.
• [7] Kucharska E., Wykorzystanie modelu algebraiczno-logicznego do optymalizacji problemów szeregowania z czasem przezbrojeń zależnym od stanu. Rozprawa doktorska 2006.