PA167 Rozvrhování

Fakulta informatiky
jaro 2005
Rozsah
2/0. 2 kr. (plus ukončení). Ukončení: zk.
Vyučující
doc. Mgr. Hana Rudová, Ph.D. (přednášející)
Garance
prof. PhDr. Karel Pala, CSc.
Katedra strojového učení a zpracování dat – Fakulta informatiky
Rozvrh
Út 8:00–9:50 B204
Omezení zápisu do předmětu
Předmět je nabízen i studentům mimo mateřské obory.
Mateřské obory/plány
Cíle předmětu
Předmět se zabývá problematikou rozvrhování z teoretického a praktického pohledu. Jsou prezentovány klasické i novější metody řešení rozvrhovacích problémů. Je diskutován problém plánování, jeho vztah k rozvrhování a možná integrace metod plánování a rozvrhování. Rozvrhování a plánování je diskutováno jako problém splňování podmínek a jsou prezentovány modely i algoritmy vycházející z této oblasti. Vedle ukázek jednodušších příkladů budou na závěr probrány i studie rozsáhlejších problémů.
Osnova
  • Základní popis problémů rozvrhování a plánování, příklady problémů.
  • Klasické rozvrhování, Grahamova klasifikace, složitost problémů. Vybrané problémy klasického rozvrhování, modely a algoritmy: jeden stroj, paralelní stroje, rozvrhování výrobního provozu.
  • Rozvrhování jako problém splňování podmínek: modely a algoritmy propagace omezení.
  • Plánování, techniky ze splňování podmínek. Vztah a integrace plánování a rozvrhování.
  • Problémové studie: školní rozvrhování, rozvrhování v prostředí výpočetního GRIDu a další.
Literatura
  • BRUCKER, Peter. Scheduling algorithms. 2nd, rev. and enl. ed. Berlin: Springer, 1998, xii, 342 s. ISBN 3-540-64105-X. info
  • BAPTISTE, Philippe, Claude LE PAPE a Wim NUIJTEN. Constraint-based scheduling :applying constraint programming to scheduling problems. Boston: Kluwer Academic Publishers, 2001, xii, 198 s. ISBN 0-7923-7408-8. info
  • GHALLAB, Malik, Dana NAU a Paolo TRAVERSO. Automated Planning: Theory & Practice. Morgan Kaufmann, 2004. info
  • PINEDO, Michael. Scheduling :theory, algorithms and systems. Englewood Cliffs: Prentice Hall, 1995, xiv, 378 s. ISBN 0-13-706757-7. info
Metody hodnocení
Písemná práce pro každý řádný termín, představuje společnou přípravu pro všechny studenty, cca 5 otázek: přehledové, srovnávací, algoritmy, pojmy, příklady.
Ústní zkouška ve stejný den jako písemná práce, příprava na individuální otázky, během zkoušky diskuse nad písemnou prací.
Opravný termín pouze jako ústní zkouška.

The written exam for each regular date. It is a preparation for all students, it includes about 5 questions: outline of certain part, comparison of some approaches, algorithms, terminology and its explanation, examples.
The oral exam in the same day as the written exam, preparation on individual questions, discussion about written exam.
Irregular dates as oral exam only.
Informace učitele
http://www.fi.muni.cz/~hanka/rozvrhovani
Další komentáře
Předmět je vyučován každoročně.
Předmět je zařazen také v obdobích jaro 2006, jaro 2007, jaro 2008, jaro 2009, jaro 2010, jaro 2011, jaro 2012, jaro 2013, jaro 2014, jaro 2015, jaro 2017, jaro 2018, jaro 2019, jaro 2020, jaro 2021, jaro 2022, jaro 2023, jaro 2024.