Plánování a rozvrhování - NAIL071

• Anglický název: Planning and Scheduling
• Zajišťuje: Katedra teoretické informatiky a matematické logiky (32-KTIML)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2014
• Semestr: letní
• E-Kredity: 3
• Rozsah, examinace: letní s.:2/0, Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: vyučován
• Jazyk výuky: angličtina, čeština
• Způsob výuky: prezenční
• Způsob výuky: prezenční
• Další informace: http://ktiml.mff.cuni.cz/~bartak/planovani/
• Garant: prof. RNDr. Roman Barták, Ph.D.
• Třída: Informatika Mgr. - Teoretická informatika
• Kategorizace předmětu: Informatika > Teoretická informatika

Anotace

čeština

Poslední úprava: T_KTI (04.05.2004)

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.

angličtina

Poslední úprava: BARTAK/MFF.CUNI.CZ (31.03.2008)

The course gives an introduction to planning and scheduling. It is focused on the algorithms for solving planning and scheduling problems with emphasis on using constraint-based techniques.

Cíl předmětu

čeština

Poslední úprava: T_KTI (23.05.2008)

Naučit studenty základní techniky plánovacích a rozvrhovacích algoritmů a teorii o nich.

angličtina

Poslední úprava: BARTAK/MFF.CUNI.CZ (31.03.2008)

The course gives an introduction to planning and scheduling. The students will learn the fundamental planning techniques including forward and backward planning, partial order planning and Graphplan. Planning with time and resources is also presented together with selected scheduling algorithms.

Podmínky zakončení předmětu

čeština

Poslední úprava: prof. RNDr. Roman Barták, Ph.D. (28.04.2020)

Předmět je zakončen ústní zkouškou, která může být ve výjimečných případech distanční.

angličtina

Poslední úprava: prof. RNDr. Roman Barták, Ph.D. (28.04.2020)

The course is concluded by an oral exam, that could be, in exceptional cases, in on-line form.

Literatura

čeština

Poslední úprava: BARTAK/MFF.CUNI.CZ (31.03.2008)

Brucker, Peter. Scheduling algorithms. 2nd, rev. and enl. ed. Berlin : Springer, 1998. xii, 342 s.

Baptiste, Philippe - Le Pape, Claude - Nuijten, Wim. Constraint-based scheduling : applying constraint programming to scheduling problems. Boston : Kluwer Academic Publishers, 2001. xii, 198 s. International series in operations research & management science.

Ghallab, Malik - Nau, Dana - Traverso, Paolo. Automated Planning: Theory & Practice. San Francisco : Morgan Kaufmann, 2004.

Metody výuky

čeština

Poslední úprava: BARTAK/MFF.CUNI.CZ (31.03.2008)

přednáška

angličtina

Poslední úprava: BARTAK/MFF.CUNI.CZ (31.03.2008)

lecture

Požadavky ke zkoušce

čeština

Poslední úprava: prof. RNDr. Roman Barták, Ph.D. (06.10.2017)

Zkouška se skládá z písemné přípravy a ústní části. Požadavky odpovídají sylabu předmětu.

angličtina

Poslední úprava: prof. RNDr. Roman Barták, Ph.D. (06.10.2017)

The exam consists of a written preparation and an oral part. The requirements are given by the course syllabus.

Sylabus

čeština

Poslední úprava: prof. RNDr. Roman Barták, Ph.D. (26.04.2007)

1. Úvod: definice problému plánování a rozvrhování, příklady použití, řešící formalismy (prohledávací algoritmy, omezující podmínky, SAT), reprezentace plánovacích problémů (množinová, klasická).

2. Plánování ve stavovém prostoru (dopředné, zpětné, STRIPS), plánování v prostoru plánů (PSP, PoP), neoklasické plánování (plánovací graf, Graphplan).

3. Plánovaní jako SAT a CSP, plánovací heuristiky.

4. Plánování s časem a zdroji (temporální problémy, plánování s kronikami, alokace zdrojů).

5. Řešení rozvrhovacích problémů: klasické rozvrhování, Grahamova klasifikace problémů, rozvrhování jako problém splňování omezujících podmínek, podmínky popisující zdroje a precedence, rozvrhovací strategie.

6. Problémové studie.

angličtina

Poslední úprava: prof. RNDr. Roman Barták, Ph.D. (26.04.2007)

1. Introduction: definitions of planning and scheduling problems, examples, solving mechanisms (search, constraint satisfaction, SAT), representation of planning problems (set-theoretic, classical).

2. State-Space Planning (forward search, backward search, STRIPS), Plan-Space Planning (PSP, PoP), Neoclassical Planning (planning graph, Graphplan).

3. Planning as SAT, planning as a CSP, planning heuristics.

4. Planning with Time and Resources (temporal problems, planning with chronicles, resource allocation).

5. Scheduling problems: traditional scheduling problems, Graham’s classification, scheduling as constraint satisfaction, resource and precedence constraints, scheduling strategies.

6. Case studies.