DM204: Scheduling, Timetabling and Routing (10 ECTS)

STADS: 15005401

Level
PhD course

Teaching period

Offered according to needs.

Teacher responsible
Email: marco@imada.sdu.dk

Timetable
There is no timetable available for the chosen semester.

Comment:
Ubegrænset deltagerantal. 3. + 4. kvartal.

Prerequisites:
None

Academic preconditions:
The Bachelor’s degree has to be passed. The contents of DM507 Algorithms and Data Structures and DM508 Algorithms and Complexity should be known.

Course introduction
The goal of the course is giving to the students the capacity to formulate and solve, through exact and heuristic methods, optimization problems that arise in scheduling, timetabling and routing.

Expected learning outcome
After the course, the student is expected to be able to:

- Describe in a precise and suitable language the basic principles of general solution methods presented in the course;
- Classify problems arising in scheduling, timetabling and routing while making use of opportune formal notation.
- Discuss in detail the dedicated algorithms for a specific problem treated in the lectures (see syllabus);
- Formulate integer programming models for the cases treated in the lecture;
- Apply the general methods to new combinatorial problems that resemble in nature the ones seen in the course. Describe in a precise written language the resulting algorithms;
- Implement the designed algorithms in a suitable programming language;
- Analyze the heuristics applied with respect to quality of solution, time and space usage, and other relevant characteristics of the methods.
- Undertake an empirical examination of the performance of the algorithms implemented and discuss the results.

Subject overview
The course will teach mathematical modelling and optimization in the three industrial application areas of production planning, service timetabling and vehicle routing. Examples of applications that will be treated during the course are flow shop and job shop scheduling, resource constrained project scheduling, crew and workforce scheduling, education timetabling, employee timetabling, and vehicle routing with constraints on capacities, time windows and visit order. For each case, the problem will be formally formulated, mathematically modeled and computationally solved. Among the solution methods that we will introduce and use are integer programming, constraint programming and heuristics. Dedicated algorithms based on dynamic programming or branch and bound, will also be outlined in the cases where these algorithms are feasible.

Literature

Meddeles ved kursets start.

Syllabus
See syllabus.

Website
This course uses e-learn (blackboard).

Prerequisites for participating in the exam
None

Assessment and marking:
(a) Project assignment. Danish 7 mark scale, internal examiner. The project assignment must be passed in order to take the oral exam.
The project assignment contributes to 40% of the final mark.

(b) Oral exam. Danish 7 mark scale, external examiner. The oral exam contributes to 60% of the final mark.
A single combined grade is given for the course.

Terms for reexam according to the rules decided by the Study Board.

Expected working hours
The teaching method is based on three phase model.

Forelæsninger, antal timer 50.
Laboratorieøvelser, antal timer 10.
Educational activities

Language
This course is taught in English.

Course enrollment
See deadline of enrolment.

Tuition fees for single courses
See fees for single courses.