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

Wyniki po sesji wrześniowej. Indeksy proszę zostawiać w sekretariacie katedry.

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.

Starsza wersja tej strony.