Plánování a rozvrhování

Z ωικι.matfyz.cz
Přejít na: navigace, hledání
Plánování a rozvrhování
Kód předmětu: NAIL071
Přednáší: Roman Barták

Základní informace[editovat | editovat zdroj]

Přednáška podává úvod do plánování a rozvrhování. Zaměřena je především na algoritmy pro řešení plánovacích a rozvrhovacích problémů s důrazem na použití technik splňování omezujících podmínek. Výklad nevyžaduje žádné předběžné znalosti.

I když znalost Programování s omezujícími podmínkami není na škodu.

Odkazy[editovat | editovat zdroj]

  • Slajdy (homepage přednášky). Jak je u Bartáka zvykem, zasloužily by 1*.
  • Samotná homepage.

Zkoušky[editovat | editovat zdroj]

Zkouška 24.01.2006[editovat | editovat zdroj]

Sešlo se nás asi pět. Vzal si nás všechny dovnitř a nechal nás vylosovat si otázky.

Já jsem dostal (není to přesně):

  1. Zdroje v rozvrhování a v plánování. Popište zdroje v plánování. Co je to zdrojový konflikt, jak se najde a jak se řeší. Popište pravidla pro rozvrhování s unárními, kumulativními a produkovatelnými/spotřebovatelnými zdroji.
  2. Napište optimalizační kritéria v rozvrhování.

Zdálo se mu, že toho mám moc, tak mi řekl, ať si u jedničky vyberu, buď zdroje v plánování nebo pravidla v rozvrhování. Protože jsem nebyl na poslední přednášce, vybral jsem si ty zdroje v plánování (čekal že si vyberu to druhý).

Občas se zeptá i na detaily. Když něco nevíte, doplní vás.

Odcházel jsem jako předposlední a pokud vím, tak všichni dostali za 1.

Zkouška 15.2.2006[editovat | editovat zdroj]

Na zkoušce nás bylo celkem devět, skoro plná kapacita. Vždy bral 4 lidi najednou, každý si vylosoval otázky, které byly recykolvány - tj. když někdo odešel, mohl další dostat jeho otázku.

Moje otázky:

  1. Co je to Job-Shop, jak se řeší - heuristický algoritmus pro Jm | | Cmax
  2. STRIPS - popis algoritmu

U první otázky jsem měl největší problém s určením release date a due date u podproblémů 1 | rj | Lmax, ale nakonec jsme se na tom spolu domluvili :)

Jenom upozornění - jeden den na přípravu nestačí, lepší je nechat si tak 3 (pokud nechcete moc tápat). Všichni dostali jedničku (buď to uměli hned, a nebo je to Barták nechal vymyslet na místě), zkouška trvá tak 1-1,5 hodiny.

Skúška 5.2.2007[editovat | editovat zdroj]

Tentokrát prebiehala skúška inou formou - každý dostal jednu úlohu, na ktorej mal demonštrovať nejaký konkrétny plánovací/rozvrhovací algoritmus (plus k tomu trochu teórie), napríklad:

Máme pračku, myčku a prívod vody, ktorý môže byť zapojený v jednom okamihu len do jedného z prístrojov. Potrebujeme umyť riad a vyprať prádlo. Navrhnite reprezentáciu plánovacej domény + problému a ukážte na ňom spôsob riešenia pomocou plánovania v priestore plánov. (veľmi podobné ako príklad s nákupmi v Tescu a OBI z prednášky) Zamyslite sa nad reprezentáciou pomocou stavovej premennej a obmedzenými zdrojmi (záver kapitoly 7, zrovna tej ktorú som nepochopil:))

Tiež mám dojem, že jednotka sa dá "vysedieť", pokiaľ človek príde na to, čo sa po ňom chce.