DM204 – Scheduling, Timetabling and Routing

Schedule

Third quarter 2010 Fourth quarter 2010
Tuesday 10:15-12:00 Monday 10:15-12:00
Thursday 10:15-12:00. Thursday 12:15-14:00.

First lecture February 2, 2010.

All lectures take place in IMADA Seminarrum.

Lectures

Third quarter

Cl. Date Topic Slides [Literature] [Exercises]
0. 01.12.2009 Course Presentation slides
1. 02.02.2010 Scheduling: Terminology, Classification 1x1, 2x2 [chp2 of B2 or chp1 of B5 + par. 2.4 of B1] [ex 2.2 p. 29, B2; ex. 3.3, 3.4 p. 46, B1]
2. 04.02.2010 Scheduling: Complexity classes 1x1, 2x2 [par 2.3-2.4 + Appendix D-E of B2, pp. 90-91 of B6 (photocopies in Course Documents)] [ex 2.11, 2.13, 2.18, 2.22, 2.23 p. 31-32 of B2]
3. 09.02.2010 RCPSP + Methods: Mixed Integer Programming, intro 1x1, 2x2 [pp. 1-17 of B5, Appendix A of B1, pp 1-3,9-20 of B7]
4. 11.02.2010 Methods: Mixed Integer Programming, LP and simplex [excerpts from B8, B9] [Sheet 1]
E1. 17.02.2010 møde lokale Exercises on MIP 1x1, 2x2 [pp. 1-58 and 307-311 of B4] [Comet-1]
5. 18.02.2010 Methods: Mixed Integer Programming, Network Flows 1x1, 2x2 [pp. 4-9,38-43, 649-652 of B8; slides by Lap Chi Lau] [Sheet 2]
6. 23.02.2010 Methods: Constraint Programming (1) 1x1, 2x2 [chp5 of B10, pp. 63-166 of B4]
E2. 24.02.2010 U49C Exercises on MIP
7. 25.02.2010 Methods: Constraint Programming (2) 1x1, 2x2 [chp. 6(7) from B11]
8. 02.03.2010 Methods: Constraint Programming (3) see lec. 7 [pp. 212-217 of B12; pp. 30-31 of chp. 6(7) from B11]
E3. 03.03.2010 U49C Exercises on MIP
9. 04.03.2010 Methods: CP in COMET + Heuristics 1x1, 2x2 1x1, 2x2 [Sheet 3]
10. 09.03.2010 Methods: Heuristics see lec.9 [App. C of B1]
11. 10.03.2010 U49C Methods: Heuristics + LS in COMET cbls [ pp. 177-305 of B4]
E4. 11.03.2010 Exercises on CP in COMET [Comet-2]
12. 17.03.2010 U49C Scheduling: Single Machine Models, Dynamic Programming 1x1, 2x2 [chp. 3 and Appendix B1 of B2]
13. 18.03.2010 Scheduling: Single Machine Models, Dynasearch see lec.12 [chp. 3 of B2]

Fourth quarter

Week 15 16 17 18 19 20 21
Mon 10-12 (Seminarrum) Class 18 Class 20 Class 23 Class 27 Class 30
Tue 14-16 (U49C) Class 21 Class 28 Class 31
Wed 8-10 (U49B) Class 24 Class 29
Thu 12-14 (Seminarrum) Class 19 Class 22 Class 25 Class 26 Class 32
Cl. Date Topic Slides [Literature] [Exercises]
18. 12.04.2010 Scheduling: Single Machine Models, Branch and Bound; Parallel Machines, PERT 1x1, 2x2 [sec. 3.2, B2; sec. 4.1-4.3, B1]
19. 15.04.2010 Scheduling: Flow Shop models, local search 1x1, 2x2 [A4; sec. 4.1-4.3, B5b]
20. 19.04.2010 Scheduling: Job Shop Models, local search 1x1, 2x2 [sec. 4.1-4.3, B5b; sec. 7.1, 7.2, B2]
21. 20.04.2010 Exercises
22. 22.04.2010 Scheduling: Resource-Constrained Project Scheduling Models 1x1, 2x2 [sec. 3.4, B5b]
23. 26.04.2010 Timetabling: Reservations and Education 1x1, 2x2 [sec. 9.1-9.5, B1; A7]
24. 28.04.2010 Timetabling: University Timetabling 1x1, 2x2 [A8]
25. 29.04.2010 Exercises
26. 06.05.2010 Timetabling: Workforce Scheduling 1x1, 2x2 [sec. 12.3-12.5, B1; sec. 2.2.5, 3.8, 3.10, B7]
27. 10.05.2010 Timetabling: Crew Scheduling, Column Generation 1x1, 2x2 [sec. 12.6, B1; sec. 22.3 of B4 (note: last Comet version is 2.1.1); deepening A11 or A12 ]
28. 11.05.2010 Exercises
29. 12.05.2010 Routing: Classification & Mathematical Programming models 1x1, 2x2 [chp. 1, B3; excerpts of chp 2,3,4, B3]
30. 17.05.2010 Routing: Branch and Price 1x1, 2x2 [A9 or chp. 7, B3]
31. 25.05.2010 Routing: Construction Heuristics 1x1, 2x2 [chp. 5, B3]
32. 27.05.2010 Routing: Local Search 1x1, 2x2 [A10]

Course Material

Books

  • [B3] Toth, P. & Vigo, D. (ed.) The Vehicle Routing Problem SIAM Monographs on Discrete Mathematics and Applications, 2002

  • [B6] Garey, M. R. & Johnson, D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness Freeman, San Francisco, CA, USA, 1979

  • [B8] R.K. Ahuja, T.L. Magnanti and J.B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993

  • [B9] L.A. Wolsey. Integer programming. John Wiley & Sons, New York, USA, 1998

  • [B10] Russell, S. & Norvig, P. Artificial Intelligence: A Modern Approach Prentice Hall, 2003

  • [B11] F. Rossi, P. van Beek and T. Walsh (ed.). Handbook of Constraint Programming, Elsevier, 2006

  • [B13] G. Desaulniers, J. Desrosiers and M.M. Solomon (ed.). Column Generation. Springer US, 2005.

Scientific Articles

  • [A12] Desrosiers, J. & Lübbecke, M. E. A Primer in Column Generation. in [B13]

Web Links

Exam

Project

  • Text (issued: March 21, 2010)

  • Data (issued: March 21, 2010)

Hand in deadline: 14:00 of June 7, 2010.

Oral

Date: Saturday, June 26, 2010