Permutacyjny problem przepływowy. Algorytmy równoległe symulowanego wyżarzania

W pracy rozpatrywany jest permutacyjny problem przepływowy z minimalizacją czasu wykonywania zadań. Przedstawiamy algorytmy (sekwencyjny i równoległy) oparte na metodzie symulowanego wyżarzania. W ich konstrukcji wykorzystano idee bloków z drogi krytycznej oraz dolne oszacowania wartości funkcji celu, a także różne schematy schładzania oraz funkcje akceptacji. Algorytmy testujemy na przykładach zaczerpniętych z pracy Taillarda [22].

---

This paper deals with the classic permutation flow shop scheduling problem with the make-span criterion. We describe an approximation algorithms (sequential and parallel) based on simulated annealing method. We research various accepting functions and cooling schedules.We propose neighbourhood using so called blocks of jobs on a critical path and also using lower bound of cost function.