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

Předmět je náhradou za:

Rozvrhování v systémech diskrétních událostí (35RDU)

Přednášející:

Cvičící:

Předmět zajišťuje:

katedra řídicí techniky

Anotace:

Zabývá se formulací problémů 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 celočíselné lineární programování. 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. Dále se předmět zabývá periodickým rozvrhováním pro aplikace reálného času založené na prioritním preemptivním operačním systému. Analýza časových vlastností se opírá o časované automaty a temporální logiku.

http://dce.felk.cvut.cz/rdu/

Požadavky:

lineární algebra

Osnova přednášek:

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

2. Standardní notace a/b/g.

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

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

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

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

7. Identické procesory, aproximační algoritmy, list scheduling.

8. Paralelní identické procesory, relace následností, preempce.

9. Rozdílné procesory a rozvrhování s preempcí.

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

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

12. Periodické rozvrhování pro aplikace pod prioritním preemptivním operačním systémem.

13. Analýza doby odezvy.

14. Analýza vlastností pomocí časovaných automatů a temporální logiky.

Osnova cvičení:

1. Rozvrhování - Formulace úlohy v rozvrhování

2. Rozvrhování - Paralelní procesory (List scheduling)

3. Rozvrhování - Cyklické rozvrhování na paralelních procesorech

4. Verifikace - úvod do UPPAALu

5. Verifikace - synchronizace v UPPAALu

6. Poslední termín pro konkretizaci individuální práce

7. Verifikace - UPPAAL pro pokročilé

8. Test

9. Konzultace individuální práce - procesory/úlohy/kritérium nebo model/vlastnosti

10. Konzultace individuální práce - návrh algoritmu nebo tvorba modelu

11. Konzultace individuální práce - implementace algoritmu nebo tvorba modelu

12. Konzultace individuální práce - experimenty

13. Odevzdání individuální práce

14. Zápočet

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)

2. Butazzo, G.C.: Hard Real-Time Computing Systems - Periodic Scheduling Algorithms and Applications, Kluwer, (1997)

3. Liu, J.W.S.: Real-Time Systems, Prentice Hall, (2000)

Poznámka:

Rozsah výuky v kombinované formě studia: 14+4

Typ cvičení: s, c

Předmět je nabízen také v anglické verzi.

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)