Rozvrhování v systémech diskrétních událostí

Přednášející:

Cvičící:

Předmět zajišťuje:

katedra řídicí techniky

Anotace:

Zabývá se formulací úloh rozvrhování operací v počítačových a výrobních systémech. Uvádí přehled základních principů užitých v algoritmech rozvrhování formulovaných jako metody diskrétní optimalizace. Opírá se o teorii grafů, algoritmy větví a mezí, lineární programování a heuristiky. Předmět zahrnuje zadání a přehled algoritmů rozvrhování pro jeden procesor pro kritéria - maximální doba vykonávání Cmax, vážená střední doba rozvrhování Fw a maximální zpoždění Lmax. Rozvrhování na paralelních procesorech je zaměřeno na úlohy bez/s relacemi následností a s/bez povolení přerušení. Řešení úloh rozvrhování s dedikovanými procesory se zabývá úlohami typu flow-shop a job-shop.

Požadavky:

Osnova přednášek:

1. Formulace úlohy rozvrhování ve výrobních systémech.

2. Standardní notace a/b/g.

3. Složitost problémů rozvrhování.

4. Klasifikace a obecné principy metod rozvrhování

5. Úloha rozvrhování pro jeden stroj, kritérium Cmax.

6. Úloha rozvrhování pro jeden stroj, minimalizace Fw.

7. Rozvrhování pro jeden stroj, kritérium Lmax.

8. Problémy s paralelními procesory, minimalizace Cmax.

9. Identické procesory, list scheduling.

10. Uniformní procesory.

11. Rozdílné procesory a rozvrhování s preemcí.

12. Dedikované stroje a rozvrhování typu flow-shop

13. Dedikované stroje a rozvrhování typu open-shop

14. Dedikované stroje a rozvrhování typu job-shop

Osnova cvičení:

1. Motivační příklady úloh rozvrhování

2. Formulace úloh rozvrhování, zadání samostatných úloh

3. Řešení úlohy rozvrhování pro jeden stroj, kritérium Cmax

4. Řešení úlohy rozvrhování pro jeden stroj, kritérium Fw, Lmax

5. Řešení úlohy rozvrhování pro paralelní stroje, kritérium Cmax

6. Řešení úlohy rozvrhování, paralelní stroje, kritérium Fw, Lmax

7. Řešení úlohy rozvrhování typu flow-shop

8. Řešení úlohy rozvrhování typu open-shop

9. Řešení úlohy rozvrhování typu job-shop, část I

10. Řešení úlohy rozvrhování typu job-shop, část II

11. Rozvrhování v pružných výrobních systémech

12. Ukázky komerčních programových prostředků rozvrhování

13. Prezentace a diskuse k řešení samostatných úloh I

14. Prezentace a diskuse k řešení samostatných úloh II

Cíle studia:

Studijní materiály:

1. Blazewicz, J., Ecker, K., Schmidt, G., Weglarz, J.: Scheduling in Computer and Manufacturing Systems, Springer- Verlag, Berlin (1993,1996)

Poznámka:

Další informace:

Pro tento předmět se rozvrh nepřipravuje

Předmět je součástí následujících studijních plánů:

• Kybernetika a měření - řídicí technika- strukturované studium (povinně volitelný předmět)
• Kybernetika a měření - umělá inteligence- strukturované studium (povinně volitelný předmět)
• Kybernetika a měření - měřicí a přístrojové systémy- strukturované studium (povinně volitelný předmět)
• Kybernetika a měření - letecké informační a řídicí systémy- strukturované studium (povinně volitelný předmět)