Algorytmy wyznaczania dróg transportu w problemie szeregowania zadań z zasobami zależnymi od stanu

Abstract

The aim of the paper is to present algorithms of transport paths for machines in specific task scheduling problem. This problem belongs to NP-hard class and its characteristic feature is that resources, which are required to accomplishing the tasks, are changeable and depend on the current state of the system. Proposed model allows machines wait for resources to be accessible. The shortest and the fastest transport path for machine are described and defined in the paper. Celem artykułu jest przedstawienie algorytmów wyznaczających drogi transportu maszyn w specyficznym problemie szeregowania zadań, należącym do klasy problemów NP-trudnych. Charakterystyczną cechą tego problemu jest fakt, że zasoby, niezbędne do realizacji zadań, są zmienne i ich dostępność zależy od aktualnego stanu systemu. W modelu tego zagadnienia uwzględniona jest możliwość oczekiwania maszyn na udostępnienie zasobu. W artykule opisano i zdefiniowano najkrótszą oraz najszybszą drogę transportową.