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

Abstract

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.

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.