Rozvrhování

Plánování úloh na jednom stroji, úvod k plánování job-shopu.

Chyba: Odkazovaný objekt neexistuje nebo nemáte právo jej číst.
https://is.muni.cz/el/fi/jaro2024/PA167/um/7.pdf


Dotazy k přednášce

  1. Vysvětlete dle průsvitek důkaz, proč je pravidlo vážené nejkratší doby optimální pro problém 1||∑jwjCj.
  2. Vysvětlete, proč EDD není optimální pro problém 1|rj|Lmax.
  3. Vysvětlete, proč je EDD optimální pro problém 1|prmp, rj|Lmax.
  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|rj|Lmax.
  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?
  11. Připomeňte, co to je job-shop problém.
  12. Popište disjunktivní grafovou reprezentaci.
  13. Co to je výběr a co to je splnitelný výběr?
  14. Jak naleznete výběr pro daný rozvrh?
  15. Popište algoritmus, jak naleznete rozvrh pro daný výběr.
  16. Vysvětlete řešení příkladu na straně 32.

Předchozí
Následující