Badania operacyjne

Deterministyczne szeregowanie zadań

Treść wykładów:

• Wprowadzenie. Podstawowe własności modelu. Notacja trójpolowa.
• Metoda ścieżki krytycznej.
• Minimalizacja długości harmonogramu.
• Minimalizacja średniego czasu przepływu.
• Minimalizacja maksymalnego opóźnienia.
• Szeregowanie zadań na maszynach dedykowanych.

Materiały pomocnicze: slajdy z wykładu (ang)

Prezentacje niektórych algorytmów:

• Minimalizacja średniego czasu przepływu i heurystyka RPT.
• Szeregowanie listowe
• Algorytm Coffmana-Grahama
• Algorytm Bruckera
• Algorytm Liu
• Zmodyfikowany algorytm Liu
• Algorytm Hodgsona
• Zmodyfikowany algorytm Johnosna dla trzech maszyn

Zadania:

• Zestaw 1 (ang)
• Zestaw 2 (ang)
• Zestaw 3 (ang)
• Zestaw 4 (ang)

Przykładowe zadania z egzaminu.

Zaliczenie

Dla osób nie po raz pierwszy uczestniczących w kursie Badania Operacyjne: punkty przepisane z wcześniejszych edycji przedmiotu. W razie stwierdzenia braków proszę o kontakt mailowy do 30.04.2020.

Literatura:

1. J. Błażewicz, W. Cellary, R. Słowiński, J. Węglarz, Badania operacyjne dla informatyków.
2. J. Błażewicz, K. Ecker, E. Pesch, G. Schmidt, J. Węglarz, Scheduling Computer and Manufacturing Processes.
3. M. Sysło, N. Deo, J. Kowalik, Algorytmy optymalizacji dyskretnej.
4. Kompleksowy przegląd wyników dot. złożoności problemów szeregowania zadań.