PA167 Scheduling

Faculty of Informatics
Spring 2005
Extent and Intensity
2/0. 2 credit(s) (plus extra credits for completion). Type of Completion: zk (examination).
Teacher(s)
doc. Mgr. Hana Rudová, Ph.D. (lecturer)
Guaranteed by
prof. PhDr. Karel Pala, CSc.
Department of Machine Learning and Data Processing – Faculty of Informatics
Timetable
Tue 8:00–9:50 B204
Course Enrolment Limitations
The course is also offered to the students of the fields other than those the course is directly associated with.
fields of study / plans the course is directly associated with
there are 7 fields of study the course is directly associated with, display
Course objectives
The course studies the area of scheduling from the theoretical and practical point of view. Both classical and new methods for solving scheduling problems are presented. Planning is also discussed, its relation and possible integration with scheduling is considered. Scheduling and planning are introduced as a constraint satisfaction problem along with corresponding models and algorithms. Solving of smaller examples and modelling of real-life problems is also shown.
Syllabus
  • Basic description of scheduling and planning problems, problem examples.
  • Classical scheduling, Graham classification, complexity. Selected problems of classical scheduling, models and algorithms: one machine, parallel machines, shop scheduling.
  • Scheduling as a constraint satisfaction problem: models and constraint propagation algorithms.
  • Planning, constraint satisfaction techniques for planning. Relation and integration of planning and scheduling.
  • Case studies: school timetabling, scheduling for GRID computing, and others.
Literature
  • 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 and 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 and 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
Assessment methods (in Czech)
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.
Language of instruction
Czech
Further Comments
The course is taught annually.
Teacher's information
http://www.fi.muni.cz/~hanka/rozvrhovani
The course is also listed under the following terms Spring 2006, Spring 2007, Spring 2008, Spring 2009, Spring 2010, Spring 2011, Spring 2012, Spring 2013, Spring 2014, Spring 2015, Spring 2017, Spring 2018, Spring 2019, Spring 2020, Spring 2021, Spring 2022, Spring 2023, Spring 2024.
  • Enrolment Statistics (Spring 2005, recent)
  • Permalink: https://is.muni.cz/course/fi/spring2005/PA167