Problem planowania zadań
Wprowadzenie
Problem planowania zadań (ang. Task Scheduling lub Job Scheduling) to klasa problemów optymalizacyjnych związanych z przydzielaniem zasobów w czasie. Polega na optymalnym ułożeniu zadań tak, aby zmaksymalizować efektywność lub zminimalizować koszty.
Podstawowe warianty: - Activity Selection - wybór maksymalnej liczby nienakładających się aktywności - Interval Scheduling - harmonogramowanie przedziałów czasowych - Weighted Job Scheduling - zadania z wagami/priorytetami - Task Scheduling with Deadlines - zadania z terminami i karami
Problemy szeregowania występują w:
- Systemach operacyjnych (szeregowanie procesów CPU)
- Zarządzaniu projektami (harmonogramy zadań)
- Produkcji (planowanie maszyn, linie produkcyjne)
- Sieciach komputerowych (przesyłanie pakietów)
- Transporcie (rozkłady jazdy, lotniska)
- Medycynie (harmonogramy operacji, gabinety)
Problem 1: Activity Selection (Wybór aktywności)
Definicja problemu
Dane: - n aktywności z czasami rozpoczęcia sᵢ i zakończenia fᵢ - Aktywności się nie nakładają jeśli jedna kończy się przed rozpoczęciem drugiej
Cel: Wybrać maksymalną liczbę nienakładających się aktywności
Strategia zachłanna: Wybieraj aktywność kończącą się najwcześniej (Earliest Finish Time).
Implementacja podstawowa
Wyjście:
=== Problem wyboru aktywności ===
Dostępne aktywności:
Nazwa Start Koniec Czas trwania
----------------------------------------
A1 1 4 3
A2 3 5 2
A3 0 6 6
A4 5 7 2
A5 3 9 6
A6 5 9 4
A7 6 10 4
A8 8 11 3
A9 8 12 4
A10 2 14 12
A11 12 16 4
============================================================
Wybrane aktywności (maksymalna liczba: 4):
============================================================
Nazwa Start Koniec
------------------------------
A1 1 4
A4 5 7
A8 8 11
A11 12 16
Wizualizacja na osi czasu:
0 5 10 15 20
|----|----|----|----|
█████████ A1 [1-4]
██████ A4 [5-7]
█████████ A8 [8-11]
████████████ A11 [12-16]
Dowód poprawności strategii EFT
Alternatywne strategie (które NIE działają)
Wyjście:
=== Porównanie strategii wyboru ===
Strategia Liczba wybranych Optymalna?
------------------------------------------------------------
Earliest Finish (EFT) 4 ✓
Shortest Duration 3 ✗
Earliest Start 3 ✗
Fewest Conflicts 3 ✗
Szczegóły dla strategii nieptymalnych:
Shortest Duration:
Wybrane: ['A2', 'A4', 'A8']
Liczba: 3 (optymalna: 4)
Earliest Start:
Wybrane: ['A3', 'A7', 'A11']
Liczba: 3 (optymalna: 4)
Fewest Conflicts:
Wybrane: ['A1', 'A4', 'A8']
Liczba: 3 (optymalna: 4)
Problem 2: Weighted Job Scheduling
Definicja problemu
Dane: - n zadań z czasami rozpoczęcia sᵢ, zakończenia fᵢ i wagami/wartościami wᵢ - Zadania się nie nakładają jeśli jedno kończy się przed rozpoczęciem drugiego
Cel: Wybrać zbiór nienakładających się zadań maksymalizujący sumę wag
UWAGA: Dla tego problemu strategia zachłanna NIE działa! Potrzebujemy programowania dynamicznego.
Implementacja DP
Wyjście:
=== Weighted Job Scheduling ===
Dostępne zadania:
Nazwa Start Koniec Waga
----------------------------------------
J1 1 3 5
J2 2 5 6
J3 4 6 5
J4 6 7 4
J5 5 8 11
J6 7 9 2
============================================================
Optymalne rozwiązanie:
============================================================
Nazwa Start Koniec Waga
----------------------------------------
J1 1 3 5
J5 5 8 11
J6 7 9 2
Maksymalna suma wag: 18
============================================================
Porównanie z podejściem zachłannym:
============================================================
Zachłanne (sortuj po wadze):
Wybrane: ['J5', 'J6']
Suma wag: 13
Optymalne (DP):
Wybrane: ['J1', 'J5', 'J6']
Suma wag: 18
✗ Zachłanne dało 13, optimum to 18!
Problem 3: Task Scheduling with Deadlines
Minimalizacja maksymalnego opóźnienia
Problem: Mamy n zadań z czasami wykonania tᵢ i deadline'ami dᵢ. Szereguj aby zminimalizować maksymalne opóźnienie.
Strategia zachłanna: Earliest Deadline First (EDF)
Wyjście:
=== Minimalizacja maksymalnego opóźnienia ===
Zadania:
Nazwa Czas trwania Deadline
----------------------------------------
J1 3 6
J2 2 8
J3 1 9
J4 4 9
J5 3 14
J6 2 15
======================================================================
Harmonogram (Earliest Deadline First):
======================================================================
Zadanie Czas Start Koniec Deadline Opóźnienie
------------------------------------------------------------
J1 3 0 3 6 0
J2 2 3 5 8 0
J3 1 5 6 9 0
J4 4 6 10 9 1
J5 3 10 13 14 0
J6 2 13 15 15 0
Maksymalne opóźnienie: 1
Wizualizacja harmonogramu:
0 5 10 15 20
|----|----|----|----|
██████ J1 (deadline: 6)
████ J2 (deadline: 8)
██ J3 (deadline: 9)
████████ J4 (deadline: 9)
↓ OPÓŹNIENIE: 1
██████ J5 (deadline: 14)
████ J6 (deadline: 15)
Dowód poprawności EDF
Problem 4: Interval Scheduling Maximization
Wiele procesorów / zasobów
Problem: Mamy k identycznych procesorów i n zadań. Przydziel zadania do procesorów aby zmaksymalizować liczbę wykonanych zadań.
Wyjście:
=== Szeregowanie na wielu procesorach ===
Liczba procesorów: 3
Liczba zadań: 8
Zadania:
Nazwa Start Koniec Czas trwania
----------------------------------------
J1 0 3 3
J2 1 4 3
J3 2 5 3
J4 3 7 4
J5 4 6 2
J6 5 8 3
J7 6 9 3
J8 7 10 3
============================================================
Przydzielenie zadań do procesorów:
============================================================
Procesor 0:
J1: [ 0- 3]
J4: [ 3- 7]
J8: [ 7-10]
Procesor 1:
J2: [ 1- 4]
J5: [ 4- 6]
J7: [ 6- 9]
Procesor 2:
J3: [ 2- 5]
J6: [ 5- 8]
Przydzielonych zadań: 8/8
Wizualizacja:
Procesor 0:
0 5 10
|----|----|
█████████ J1
████████████ J4
█████████ J8
Procesor 1:
0 5 10
|----|----|
█████████ J2
██████ J5
█████████ J7
Procesor 2:
0 5 10
|----|----|
█████████ J3
█████████ J6
Problem 5: Load Balancing
Minimalizacja maksymalnego obciążenia
Problem: Przydziel n zadań do m procesorów tak, aby zminimalizować maksymalny czas pracy procesora.
Strategia zachłanna: Zawsze przydzielaj zadanie do najmniej obciążonego procesora.
Wyjście:
=== Load Balancing (zachłanne) ===
Zadania (czasy wykonania): [7, 5, 4, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1]
Liczba procesorów: 3
Przydzielenie zadań:
Procesor Zadania Obciążenie
------------------------------------------------------------
Procesor 0 T0(7), T3(4), T7(2), T11(1) 14
Procesor 1 T1(5), T4(3), T6(3), T8(2) 13
Procesor 2 T2(4), T5(3), T9(2), T10(1), T12(1) 11
Maksymalne obciążenie: 14
Średnie obciążenie: 12.67
Teoretyczne minimum: 12.67
Wizualizacja obciążenia:
Procesor 0: ████████████████████████████████████████ 14
Procesor 1: █████████████████████████████████████ 13
Procesor 2: ███████████████████████████████ 11
Złożoność obliczeniowa
Porównanie problemów
| Problem | Strategia | Złożoność | Poprawność |
|---|---|---|---|
| Activity Selection | EFT | O(n log n) | Optymalna |
| Weighted Job Scheduling | DP | O(n²) lub O(n log n) | Optymalna |
| Minimize Lateness | EDF | O(n log n) | Optymalna |
| Multi-processor Scheduling | EFT per processor | O(n log n) | Optymalna |
| Load Balancing | Greedy | O(n log n) | 2-aproksymacja |
Uwaga: Load Balancing zachłannie daje 2-aproksymację (wynik ≤ 2 × optimum).
Podsumowanie
Kluczowe strategie
| Problem | Kryterium wyboru | Działa? |
|---|---|---|
| Activity Selection | Najwcześniejsze zakończenie | ✓ Optymalne |
| Weighted Jobs | Programowanie dynamiczne | ✓ Optymalne |
| Minimize Lateness | Najwcześniejszy deadline | ✓ Optymalne |
| Load Balancing | Najmniej obciążony | ✓ 2-aproksymacja |
Kiedy używać którego?
✅ Activity Selection / EFT gdy: - Zadania bez wag - Chcemy maksymalną liczbę zadań - Wszystkie zadania równie ważne
✅ Weighted Scheduling / DP gdy: - Zadania mają różne priorytety/wartości - Potrzebujesz maksymalizować wartość - Nie zależy na liczbie zadań
✅ EDF (Earliest Deadline) gdy: - Mamy deadline'y - Chcemy minimalizować opóźnienia - Real-time systems
✅ Load Balancing gdy: - Wiele procesorów/zasobów - Chcemy równomiernego rozłożenia pracy - Minimalizacja czasu całkowitego
Co dalej?
Po opanowaniu problemów planowania zadań, następne tematy to:
- Lekcja 76: Kompresja Huffmana
- Drzewo Huffmana (zachłanne)
- Kodowanie i dekodowanie
-
Optymalne kodowanie prefiksowe
-
Algorytmy grafowe zachłanne:
- Dijkstra (najkrótsza ścieżka)
- Prim i Kruskal (MST)
-
Kolorowanie grafów
-
Zaawansowane szeregowanie:
- Flow shop scheduling
- Job shop scheduling
- Online algorithms
Zadania praktyczne
Zadanie 1: Classroom Assignment
Masz n zajęć i k sal. Przydziel zajęcia do sal aby zminimalizować liczbę potrzebnych sal.
Zadanie 2: Interval Partitioning
Podziel zbiór przedziałów na minimalną liczbę grup tak, aby w każdej grupie przedziały się nie nakładały.
Zadanie 3: Task z zależnościami
Rozszerz problem planowania o zależności między zadaniami (zadanie A musi być przed B).
Zadanie 4: Minimize sum of completion times
Szereguj zadania aby zminimalizować sumę czasów zakończenia (∑completion_time).
Zadanie 5: Udowodnij lub obal
Czy dla Load Balancing zachłanne daje zawsze wynik ≤ 2 × optimum? Udowodnij lub podaj kontrprzykład.
Następna lekcja: Kompresja Huffmana - optymalne kodowanie prefiksowe