Subjects

Your browser does not support JavaScript, or its support is disabled. Some features may not be available.

Planning and Scheduling - NAIL071

Title:	Plánování a rozvrhování
Guaranteed by:	Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
Faculty:	Faculty of Mathematics and Physics
Actual:	from 2014
Semester:	summer
E-Credits:	3
Hours per week, examination:	summer s.:2/0, Ex [HT]
Capacity:	unlimited
Min. number of students:	unlimited
4EU+:	no
Virtual mobility / capacity:	no
State of the course:	taught
Language:	English, Czech
Teaching methods:	full-time
Additional information:	http://ktiml.mff.cuni.cz/~bartak/planovani/

Guarantor:	prof. RNDr. Roman Barták, Ph.D.
Teacher(s):	prof. RNDr. Roman Barták, Ph.D.
Class:	Informatika Mgr. - Teoretická informatika
Classification:	Informatics > Theoretical Computer Science

Opinion survey results Examination dates SS schedule Noticeboard

Annotation -

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.

Last update: BARTAK/MFF.CUNI.CZ (31.03.2008)

Aim of the course -

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.

Last update: BARTAK/MFF.CUNI.CZ (31.03.2008)

Course completion requirements -

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

Last update: Barták Roman, prof. RNDr., Ph.D. (28.04.2020)

Literature -

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.

Last update: BARTAK/MFF.CUNI.CZ (31.03.2008)

Teaching methods -

lecture

Last update: BARTAK/MFF.CUNI.CZ (31.03.2008)

Requirements to the exam -

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

Last update: Barták Roman, prof. RNDr., Ph.D. (06.10.2017)

Syllabus -

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.

Last update: Barták Roman, prof. RNDr., Ph.D. (26.04.2007)