Připravené materiály představující doplňující dotazy k přednášce předmětu PA167 Rozvrhování.

Úvod do rozvrhování, příklady a reálné problémy

1. Jak byste popsali rozvrhovací problém? Jak lze pomocí Ganttova diagramu znázornit rozvrhovací problém?
2. Jaký je rozdíl mezi úplným/částečným/konzistentním a optimálním rozvrhem?
3. Jak byste popsali rozvrhovací příklad s montáží kola na průsvitce 4? Co je jeho (optimálním) řešením?
4. Jaké problémy se řeší při rozvrhování sester v nemocnici?
5. Jaké problémy se řeší při plánování nákladní automobilové dopravy?
6. Jaké problémy se řeší při rozvrhování předmětů na univerzitě?
7. Jaký je rozdíl mezi problémy scheduling/timetabling/planning? Uveďte jejich příklady.
8. Co to je AI planning? Uveďte vhodný příklad.
9. Jak byste popsali problémy seřazení (sequencing) a rostering? Uveďte jejich příklady.
10. Jaký je rozdíl mezi úlohou a operací?
11. Popište statické a dynamické parametry úlohy.

Grahamova klasifikace

1. Co to je Grahamova klasifikace?
2. Vysvětlete rozdíl mezi identickými paralelními stroji, paralelními stroji s různou rychlostí a nezávislými paralelními stroji.
3.  Jak byste popsali multi-operační (shop) problémy? 
4. Co to je flow shop problém a co to je flexible flow shop problém?
5. Popište job shop problém a co to je open shop problém. Jak se liší navzájem a od předchozích shop problémů?
6. Co to je makespan? Jak dosahujeme při minimalizaci makespan maximalizace výkonu?
7. Co to je zpoždění (lateness) a maximální zpoždění? Jak spočítáte maximální zpoždění pro příklad na průsvitce 21?
8. Co to je nezáporné zpoždění (tardiness) a celkové zpoždění? Jak spočítáte celkové zpoždění pro příklad na průsvitce 22?
9. Na co se používá kritérium, které minimalizuje součet časů konců úloh?
10. Odhadnete, proč je problém 1|rj|Lmax NP-úplný, zatímco problém 1||Lmax má polynomiální složitost?
11. Odhadnete, proč má problém P|pmtn|Cmax polynomiální složitost, zatímco  P2||Cmax je NP-úplný?

Řídící pravidla

1. Co to je řídící pravidlo? Ukažte na příkladu na průsvitce 3, jak funguje řídící pravidlo s nejdřívějším termínem dostupnosti pro rozvrhování na jednom stroji.
2. Ukažte, jak funguje řídící pravidlo s nejdřívějším termínem dokončení na příkladu na průsvitce 4.
3. Co to je minimální rezerva?  Jak funguje pravidlo minimální rezervy?
4. Ukažte rozdíl mezi pravidlem s nejdelší a nejkratší dobou trvání na příkladu na průsvitce 18. Jaká kritéria tyto pravidla minimalizují a proč?

Omezující podmínky

1. Co to je omezení? Uveďte také příklad omezení. Kdy je omezení splněno?
2. Co to je problém splňování podmínek? Uveďte příklad. Co je jeho řešením?
3. Co to je filtrace domén?
4. Co to je hranová konzistence? Ukažte na příkladech na průsvitce, kdy je podmínka hranově konzistentní a kdy není.
5. Popište, jak funguje algoritmus pro zajištění hranové konzistence.
6. Popište, jak používáme při řešení problémů prohledávání do hloubky.

Rozvrhování s omezujícími podmínkami

1. Jaké doménové proměné jsou svázány s aktivitou a jejím časem
2. Jaké typy základních omezení se používají při rozvrhování?
3. Jaké doménové proměné jsou svázány s aktivitou a jejím časem?
4. Jaké typy základních omezení se používají při rozvrhování?
5. Jaké doménové proměné jsou svázány se zdroji?
6. Co to je unární zdroj a jak s ním pracujeme?
7. Jaký je princip algoritmu hledání hran?
8. Popište odvozovací pravidla při hledání hran.
9. Jaký je princip algoritmu not-first?
10. Jaká odvozovací pravidla používáme při použití pravidla not-first?
11. Jakým způsobem lze realizovat propagaci pro alternativní zdroje?  Popište příslušná odvozovací pravidla.
12. Co to je kumulativní zdroj?
13. Jak se pracuje s agregovanými požadavky?
14. Co to je globální podmínka? Popište globální podmínku allDifferent.
15. Co to je intervalová a sekvenční proměnná? Co je cílem omezení noOverlap? 
16. Popište řešení job-shop problému dle kódu na str. 31.
17. Jak pracujeme s kumulativními funkcemi?
18. Co to je rezervoár a jak s jeho využitím můžeme zajistit propagaci požadovaného množství zdroje?
19. Co to je optimistický zdrojový profil? 
20. Jak můžeme propagovat na základě optimistického zdrojového profilu?
21. Vyřešte příklad na straně 7.
22. Co to je pesimistický zdrojový profil? 
23. Jak můžeme propagovat na základě pesimistického zdrojového profilu?
24. Jaké znáte způsoby větvení?
25. Co to je rezerva? Popište rezervu pro dané pořadí aktivit, pro dvě aktivity a pro skupinu aktivit.
26. Jak realizujeme větvení s pomocí uspořádání dvojic aktivit?
27. Jak realizujeme větvení s výběrem první resp. poslední aktivity?

Matematické programování

1. Co to je linerární program? A celočíselný lineární program?
2. Vysvětlete význam rovnic pro příklad na průsvitce 4.
3. Co to je směna? Jak byste naformulovali problém rozvrhování zaměstnanců na směny?

Lokální prohledávání

1. Jaký je rozdíl mezi konstruktivními metodami a lokálním prohledáváním?
2. Popište konstru algoritmu lokálního prohledávání.
3. Jak budeme reprezentovat rozvrh pro problém jednoho stroje a jaké můžeme použít okolí?
4. Jak vygenerujete iniciální řešení? Jak mohou vypadat podmínky ukončení?
5. Jaké znáte metody pro akceptování horšího rozvrhu?
6. Popište princip tabu prohledávání. Co to je aspirační kritérium?
7. Popište pseudokód algoritmu tabu prohledávání.
8. Popište jednotlivé kroky řešení příkladu na průsvitce 10.
9. Jaké myšlenky využívá algoritmus simulovaného žíhání?
10. Vysvětlete, jak funguje Metropolisovo kritérium.
11. Vysvětlete pseudokód algoritmu simulovaného žíhání.
12. Popište jednotlivé kroky řešení příkladu na průsvitce 17.
13. Popište princip genetických algoritmů.
14. Jaký je princip křížení? Proč nelze pro rozvrhování na jednom stroji použít operátor jednobodového (jednoduchého) křížení?
15. Popište křížení  dané pořadím na příkladu z průsvitky 22.
16. Jaké znáte typy mutace?
17. Jak funguje princip ruletového kola?
18. Jak funguje turnajový výběr a jak funguje elitářský model?
19. Popište pseudokód genetického algoritmu
20. Popište jednotlivé kroky řešení příkladu na průsvitce 27.

Plánování projektu

1. Popište problém plánování projektu s jeho rozšířeními.
2. jaké reprezentace používáme pro plánování projektu? Diskutujte jejich výhody a nevýhody.
3. Popište parametry problému plánování projektu.
4. Popište princip metody kritické cesty.
5. Jak určím úlohy s rezervou a jak spočítám jejich rezervu?
6. Co to je kritická úloha a kritická cesta?
7. Jak spočítám kritickou cestu?
8. Vyřešte problém na straně 10 metodou kritické cesty.
9. Jak pracujeme s variabilní dobou trvání úloh? Co to je marginální cena?
10. Jak spočítám náklady na provedení projektu při variabilní době trvání?
11. Co to je (vrcholový) řez a minimální řez?
12. Uměli byste na příkladu ze strany 20 vysvětlit, jak funguje algoritmus kompromisní heuristiky?
13. Jaké se používají proměnné, omezení a účelová funkce v lineárním programu řešícím problém plánování projektu s variabilní dobou trvání? Uměli byste tato omezení a účelovou funkci vysvětlit?
14. Jaké proměnné se používají v celočíselném programu pro  problém plánování projektu s variabilní dobou trvání?
15. Jak zde spočítáte kapacitu zdroje pro danou úlohu v každém časovém intervalu?
16. Jak zde určíte koncový čas jednotlivých úloh a makespan?
17. Jak zde zapíšete precedenční omezení, omezení na kapacitu a požadavek na jediné ukončení každé úlohy?

Plánování úloh na jednom stroji

1. Vysvětlete dle průsvitek důkaz, proč je pravidlo vážené nejkratší doby optimální pro problém 1||∑_jw_jC_j.
2. Vysvětlete, proč EDD není optimální pro problém 1|r_j|L_max.
3. Vysvětlete, proč je EDD optimální pro problém 1|prmp, r_j|L_max.
4. Vyzvětlete metodu větví a mezí. Jak lze spočítat dolní hranici na cenu řešení s pomocí zjednodušení původního problému?
5. Vysvětlete aplikaci metody větví a mezí na problém 1|r_j|L_max.
6. Vysvětlete s pomocí průsvitek řešení příkladu ze strany 14.
7. Vysvětlete, jak funguje paprskové prohledávání.
8. Jaký je význam proměnných v problému na průsvitce 21?
9. Dokážete vysvětlit formulaci účelové funkce pro tento problém?
10. Dokážete vysvětlit formulaci požadavku, že každá úloha právě jednou začne?

Plánování job-shopu

1. Připomeňte, co to je job-shop problém.
2. Popište disjunktivní grafovou reprezentaci.
3. Co to je výběr a co to je splnitelný výběr?
4. Jak naleznete výběr pro daný rozvrh?
5. Popište algoritmus, jak naleznete rozvrh pro daný výběr.
6. Vysvětlete řešení příkladu na straně 32.
7. Co to je disjunktivní programování?
8. Vysvětlete formulaci job-shop problému pomocí disjunktivního programování.
9. Jaký je rozdíl mezi aktivním rozvrhem a rozvrhem bez zdržení? Vysvětlete to také na příkladu.
10. Vysvětlete generování množiny všech aktivních rozvrhů.
11.  Vysvětlete řešení příkladu 27.3 ze sbírky (řešených) příkladů.
12. Jak probíhá výpočet dolní hranice?
13. Dokážete vysvětlit princip heuristiky posunování kritckého místa?

Plánování montážních systémů

1. Jaké jsou charakteristiky montážní linky? Čím se vyznačuje montážní linka s flexibilním časem?
2. Co to je cyklický rozvrh a kdy se používá?
3. Co to je minimální podílová množina?
4. Vysvětlete, jak vznikne rozvrh při posloupnosit úloh 1,2,3 na str. 8.
5. Co to je profil a jak se vypočítá čas odchodu úloh z jednotlivých strojů u  heuristiky padnoucího profilu? Jak se určí celková neproduktivní doba?
6. Dokážete vysvětlit řešení příkladu 29.8 ze sbírky (řešených příkladů)?
7. Jak byste popsali montážní linku s fixním časem?
8. Jak se používá heuristika seskupování a distribuce? 
9. Popište jednoduchý matematický model, který budeme používat u heuristiky seskupování a distribuce.
10. Popište řešení příkladu na str. 19.

Podpořeno z projektu NPO (MUNI 3.2.1)