Materiały kolokwium 2024/25

Kluczowe Koncepcje z Teorii Szeregowania Zadań:

To absolutna podstawa. Zrozumienie tej notacji pozwala natychmiast zidentyfikować rodzaj problemu.

α (alfa): Środowisko maszynowe. Odpowiada na pytanie "Gdzie?".
- 1: Jedna maszyna.
- P: Maszyny równoległe (zadanie idzie na jedną, dowolną maszynę).
- F: System przepływowy / Flow Shop (wszystkie zadania mają tę samą trasę).
- J: System gniazdowy / Job Shop (każde zadanie ma własną, unikalną trasę).
- FP, F:* flow shop permutacyjny/ przepływowy: kolejność zadań musi być identyczna na wszystkich maszynach.
β (beta): Ograniczenia i cechy zadań. Odpowiada na pytanie "Jakie są zasady?".
- prmu: Permutacyjność (kolejność zadań ta sama na wszystkich maszynach).
- r_j: Różne czasy gotowości.
- d_j: Zadania mają terminy ostateczne (deadlines).
- pmtn: Możliwość przerywania zadań.
- Puste pole: Brak dodatkowych ograniczeń.
γ (gamma): Kryterium optymalizacji. Odpowiada na pytanie "Co chcemy osiągnąć?".
- C_max: Minimalizacja maksymalnego czasu zakończenia (tzw. makespan).
- L_max: Minimalizacja maksymalnego opóźnienia względem terminów.
- Σw_jC_j: Minimalizacja sumy ważonych czasów zakończenia. Zakończenie ważniejszych zadań jest priorytetem.
- Σw_jT_j: Minimalizacja sumy ważonych spóźnień.

Praktycznie za każdym pytaniem kryła się kwestia złożoności obliczeniowej.

Problemy wielomianowe (klasa P): Istnieją dla nich szybkie, optymalne algorytmy (np. F2||C_max z algorytmem Johnsona, 1||ΣC_j z algorytmem SPT).