Harmonogramowanie

Harmonogramowanie to dziedzina badań operacyjnych i informatyki zajmująca się planowaniem wykonywania zadań w czasie przy ograniczonych zasobach, takich jak maszyny, pracownicy czy procesory, w celu optymalizacji wybranych kryteriów. Celem jest ustalenie kolejności i czasu realizacji zadań tak, by spełnić ograniczenia i zminimalizować koszty lub czas realizacji.

Podstawowe problemy obejmują harmonogramowanie na jednej maszynie, na wielu maszynach identycznych lub różnych, a także modele przepływu (flow shop), job shop oraz open shop. Dane wejściowe to czasy przetwarzania zadań, ewentualne daty uwolnienia (release dates), terminy wykonania (due dates), ograniczenia precedencji między zadaniami oraz czasy przygotowań między zadaniami. W praktyce uwzględnia się także ograniczenia zasobów i transferów.

Funkcje celu w harmonogramowaniu obejmują m.in. minimalizację Cmax, czyli maksymalnego czasu zakończenia wszystkich zadań, minimalizację sumy czasów zakończenia (sum Cj), maksymalny opóźnienie (Lmax) oraz sumę ważonych opóźnień lub liczbę spóźnionych zleceń. Wybór funkcji zależy od kontekstu i celów organizacji.

Metody rozwiązywania obejmują algorytmy dokładne (branch-and-bound, dynamic programming), metody formułowe i heurystyczne, a także metody metaheurystyczne (algorytmy genetyczne, simulated annealing, tabu search). Dla niektórych klas problemów istnieją rozwiązania w czasie wielomianowym (np. reguła Johnsona dla dwumaszynowego flow shop), podczas gdy wiele zadań jest NP-trudnych.

Zastosowania obejmują przetwarzanie wytwórcze, logistykę, usługowy sektor zdrowia i IT (harmonogramowanie procesorów), a także projektowanie planów produkcyjnych i operacyjnych w przedsiębiorstwach. Planowanie może być offline (przy pełnej informacji z góry) lub online (reaktywne na zdarzenia w czasie rzeczywistym).