2017 Spring
Show the courses of study containg this course Se overgangsordninger
Dansk English

DM858: Scheduling, Timetabling and Routing (5 ECTS)

STADS: 15019301

Level
Master's level course approved as PhD course

Teaching period
The course is offered in the spring semester.

Teacher responsible
Email: marco@imada.sdu.dk

Timetable
There is no timetable available for the chosen semester.

Comment:
Ubegrænset deltagerantal.

Prerequisites:
Achievement of a Bachelor degree.

Academic preconditions:
Students taking the course are expected to:
  • Have knowledge of the content of the course: DM545 or DM559 "Linear and Integer Programming"
  • Be able to program
 


Course introduction
The course covers mathematical modeling and optimization in the three industrial application areas: production planning, service timetabling and vehicle routing. Examples of applications from these areas are: 

flow shop and job shop scheduling, resource constrained project scheduling, crew and workforce scheduling, education timetabling, employee timetabling, vehicle routing with constraints on capacities, time windows and visit order.

The course will provide a classification and a characterization of the optimization problems arising from these applications. Then, for the selected cases, the problem will be precisely formulated and modeled in mixed integer linear programming (MILP) terms. In actual practice, the models often are solvable only by a specifically adapted method. The course will outline advanced MILP techniques like column generation and dedicated algorithms based on dynamic programming or branch and bound where they are feasible. Alternatively, heuristics will be considered. 

The focus of the course may vary throughout the editions and it may be influenced by the partecipants' interests: it is possible to have a broad focus among the three areas or to go more in-depth on one of the three only.

The final aim of the course is to enable the student to recognize the precise variant of problems regarding scheduling, timetabling and transportation and to use advanced MILP techniques and heuristics to formulate and solve decision problems in these areas. Ideally at the end of the course the students should be also able to design solution methods themselves by developing and combining the presented methods.

The course builds on the knowledge acquired in the course DM545 or DM559 "Linear and Integer Programming" and gives an academic basis for doing a master thesis project and other theoretically or practically oriented study-activities, that can be chosen as part of the degrees in Computer Science, Mathematics-Economics, Applied Mathematics and others. 

In relation to the competence profile of the degree it is the explicit focus of the course to:

  • Give skills in planning and carrying out scientific projects at a high professional level including managing work-related situations that are complex, unpredictable and require new solutions
  • Provide skills to describe, analyze and solve advanced computational problems using the learned models
  • Provide skills to elucidate the advanced hypotheses on a qualified theoretical basis and to critically evaluate owns and others' research and scientific models
  • Provide skills in developing new variants of the methods learned where the specific problem requires it
  • Provide skills in communicating research-based knowledge and discuss professional and scientific problems with both peers and non-specialists
  • Provide expertise in a specific field of study, based on the highest international research in the fields of computer science and operations research
  • Provide knowledge about a variety of specialized models and methods developed in computer science and operations research based on the highest international research, including topics from the subject's research front
 


Expected learning outcome
The learning objective of the course is that the student demonstrates the ability to:
  • Recognize and classify problems arising in scheduling, timetabling and routing while making use of opportune formal notation.
  • Describe solution approaches based on mixed integer linear programming or heuristic models. 
  • Discuss in detail a few dedicated algorithms for specific cases treated in the lectures;
  • Analyze the solution methods with respect to computation time and solution quality.
Subject overview
The following main topics are contained in the course:
  • Classification of scheduling, timetabling and routing problems
  • Column generation
  • Construction heuristics
  • Selected problems from scheduling, timetabling and routing
 


Literature
    Meddeles ved kursets start.


Website
This course uses e-learn (blackboard).

Prerequisites for participating in the exam
None

Assessment and marking:


Expected working hours
The teaching method is based on three phase model.
Intro phase: 26 hours
Skills training phase: 22 hours, hereof:
 - Tutorials: 22 hours

Educational activities
  • Reading from text books
  • Solving homeworks
  • Applying acquired knowledge to practical, group projects
 
Educational form

Language
This course is taught in Danish or English, depending on the lecturer. However, if international students participate, the teaching language will always be English.

Course enrollment
See deadline of enrolment.

Tuition fees for single courses
See fees for single courses.