PA167 Vzorová písemná práce
1. Jaké znáte typy optimalizačních kritérií používaných při rozvrhování? Uveďte tři různé typy kritérií a jejich formální definici.
2. Uvažujte rozvrhovací problém s 11 d3• | J] WjTj
úlohy	1	2	3	4
Pi	1	2	3	1
dj	2	1	2	10
Wj	1	2	5	3
a tabu prohledávání s následujícími parametry:
• okolí tvoří všechny rozvrhy, které získáme párovou výměnou sousedních úloh;
• iniciální rozvrh je (1, 2, 3,4);
• tabu seznam tvoří pár úloh, který byl přehozen při jedné poslední změně. Ukažte, jakým způsobem probíhá výpočet v prvních dvou iteracích.
3. Co je to marginální cena? Uveďte definici.
4. Popište některé z odvozovacích pravidel pro zdroje používané v kontextu programování s omezujícími podmínkami.
5. Znáte některý rozvrhovací problém, který lze formulovat jako problém barvení grafu? Popište jej a uveďte korespondenci mezi oběma problémy.
6. Popište problém intervalového rozvrhování.
7. Pracovní doba v továrně je od 6:00 do 22:00. Zaměstnanci mohou pracovat v následujících směnách a za každou z nich jsou placeni uvedeným platem
směna	doba	plat
1	6-14	750
2	14-22	850
3	6-18	1200
4	8-14	550
5	6-10	370
V době od 6:00 do 8:00 jsou potřeba 4 zaměstnanci, mezi 8:00 a 14:00 je vyžadováno 8 zaměstnanců, od 14:00 do 18:00 celkem 5 zaměstanců a večer od 18:00 do 22:00 jsou nutni pouze 3 zaměstnanci. Popište, jakým způsobem je možné nalézt takový počet zaměstnanců na každou směnu, aby byla minimalizována celková výše peněz nutná na platy.
8. Popište metodu větví a mezí (branch&bound).