Overview
Content
The course is application-oriented and is focused on three optimization contexts: production planning, service timetabling, and transportation routing. In the first context, application examples are project scheduling, job shop scheduling and scheduling in flexible assembly systems. In the second context, application examples are crew and workforce scheduling, education timetabling and employee timetabling. In the third context, application examples are the vehicle routing problems, with constraints that derives from capacities, time windows, pickup and delivery or back-haul. For each case, the problem will be formulated, modeled and solved. Cases under uncertainty of data will also be considered. The solution techniques are mainly heuristics, such as local search methods and metaheuristics, but exact methods, such as networks algorithms, integer programming and branch and bound, will also be outlined when they are feasible for the given problem. The configuration and tuning of these solvers on the specific application will be solved by means of a systematic methology.
Course Material
Text book
M.L. Pinedo, Planning and Scheduling in Manufacturing and
Services; Springer Series in Operations Research and Financial
Engineering, 2005. (388 DKK)
Supplementary books
M.L. Pinedo, Scheduling: Theory, Algorithms, and Systems; 2nd ed.,
Prentice Hall, 2002.
P. Toth, D. Vigo, eds. The Vehicle Routing Problem, SIAM
Monographs on Discrete Mathematics and Applications, Philadelphia,
2002.
Schedule
The course starts on Monday January 28, 2008 and will run on
Monday 14:15 - 16:00 in U28 and
Wednesday 14:15 - 16:00 in U25
until April 17, inclusive.
Oral exam: June, 19 2008.
Aims
The course aims at giving to the students the capacity to formulate and solve, through heuristic and exact methods, optimization problems that arise in scheduling, timetabling and routing.
After the course, the student is expected to be able to:
- Describe in a suitable language the basic principles of general
solution methods presented in the course;
- Classify problems arising in scheduling, timetabling and routing also
making use of opportune formal notation. Recognize new similar
problems within these schemes;
- For a specific problem, discuss in detail a few among the dedicated
algorithms (exact or heuristic, 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 saw in the course. Describe in a precise and
written language the resulting algorithms;
- Implement the designed algorithms in a specific language;
- Undertake an empirical examination of the performance of the
algorithms implemented and discuss the results.
Evaluation
Evaluation is based on a project report and an oral exam (30 minutes
without preparation). The oral exam counts 60% of the total grade. Marks are
according to the Danish 7-point marking scale and will be decided
jointly by the teacher and the external examiner.
Projects can be made in groups of up to three persons. The project
description is given to each group in one of the last lectures and the
report must be handed in before the date of the oral exam.
Contact Address
Marco Chiarandini
Phone: +45 6550 4031
Office:
Campus Ø17-606a-1 (1.717)
Lecture Program
| Lecture | Date | Topic | Slides | Notes |
|---|---|---|---|---|
| 21.05.07 | Course Presentation. | |||
| 1 | 28.01.08 | Introduction to Scheduling: Terminology, Classification. | html | |
| 2 | 31.01.08 | Classification, CPM/PERT Mathematical Programming |
html | |
| 3 | 04.02.08 | Review of Optimization Methods: Dynamic Programming, Branch and Bound, Constraint Programming | html | |
| 4 | 07.02.08 | Review of Heuristics for Optimization. | html | |
| 5 | 11.02.08 | Practical Exercises on Mixed Integer Programming. | html data |
|
| 6 | 14.02.08 | Practical Exercises on Heuristics. | html smtwt-c.tgz |
|
| 7 | 18.02.08 | Practical Exercises on Constraint Programming. | html data |
|
| 8 | 21.02.08 | Single Machine Models | html | |
| 9 | 25.02.08 | Single and Parallel Machine Models | html | |
| 10 | 28.02.08 | Flow Shops | html | |
| 11 | 03.03.08 | Flow Shops and Job Shops | html |
|
| 12 | 06.03.08 | Job Shops and Resource Constrained Project Scheduling | html |
|
| 13 | 17.03.08 | Resource Constrained Project Scheduling. Timetabling, Reservations |
html | |
| 14 | 27.03.08 | Educational Timetabling. | html | |
| 15 | 31.03.08 | Sport Timetabling | html | |
| 16 | 03.04.08 | Transportation Timetabling | html | |
| 17 | 07.04.08 | Workforce Scheduling | html | |
| 18 | 09.04.08 | Introduction to Vehicle Routing. MIP models and Construction Heuristics. | html | |
| 19 | 14.04.08 | Local Search and Metaheuristics for VRP and VRPTW | html | |
| 20 | 16.04.08 | VRP Extensions | html |
Exam
Project
Hand in deadline: June 10, 2008.
- Project description (Published on March 28, 2008. Last update: March 28, 2008)
- Instances (Published: March 28, 2008, Updated: April 11, 2008, Updated: April 18, 2008)
- Solution checker (Published: March 28, 2008, Updated: April 9, 2008, Updated: April 18, 2008; April 22, 2008; April 30, 2008; May 5, 2008; May 29, 2008)
- Machine benchmark program
Oral
Date: June 19, 2008.
- Syllabus (Published on March 31, 2008, Updated on April 7, 2008)
- List of possible questions (Published on March 31, 2008, Updated on April 16, 2008)
- All the slides of the course [3x6 per page] (Published on June 17, 2008)