Rozvrhování

Charakteristiky úloh, optimalizační kritéria. Řídící pravidla.

Přednáška 02
Dotazy k přednášce

  1. Co to je makespan? Jak dosahujeme při minimalizaci makespan maximalizace výkonu?
  2. 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 6?
  3. 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 7?
  4. Na co se používá kritérium, které minimalizuje součet časů konců úloh?
  5. Odhadnete, proč je problém 1|rj|Lmax NP-úplný, zatímco problém 1||Lmax má polynomiální složitost?
  6. Odhadnete, proč má problém P|pmtn|Cmax polynomiální složitost, zatímco  P2||Cmax je NP-úplný?
  7. Co to je řídící pravidlo? Ukažte na příkladu na průsvitce 13, jak funguje řídící pravidlo s nejdřívějším termínem dostupnosti pro rozvrhování na jednom stroji.
  8. Ukažte, jak funguje řídící pravidlo s nejdřívějším termínem dokončení na příkladu na průsvitce 14.
  9. Co to je minimální rezerva?  Jak funguje pravidlo minimální rezervy?
  10. 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č?

Předchozí
Následující