DM204 – Scheduling, Timetabling and Routing

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

• [B1] Pinedo, M. Planning and Scheduling in Manufacturing and Services Springer Verlag, 2005

• [B2] Pinedo, M. Scheduling: Theory, Algorithms, and Systems Springer New York, 2008

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

• [B4] Comet Tutorial (see doc in Comet Application)

• [B5] Brucker, P. Scheduling Algorithms. Springer 2007

• [B5b] Brucker, P. & Knust, S. Complex Scheduling Springer Berlin Heidelberg, 2006

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

• [B7] M. Grötschel, L. Lovász and A. Schrijver. Geometric Algorithms and Combinatorial Optimization. Springer, 1993, 2

• [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

• [B12] Hooker, J. N. Integrated Methods for Optimization. Springer US, 2007, 100

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

Scientific Articles

• [A1] L. Michel and P.V. Hentenryck. A constraint-based architecture for local search. OOPSLA ’02: Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, ACM, 2002, 83-100

• [A2] Congram, R. K.; Potts, C. N. & van de Velde, S. L. INFORMS Journal On Computing An Iterated Dynasearch Algorithm for the Single-Machine Total Weighted Tardiness Scheduling Problem, 2002, 14, 52-67

• [A3] Jens Clausen. Contents Branch and Bound Algorithms - Principles and Examples

• [A4] R. Ruiz and T. Stützle. A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. European Journal of Operational Research, 177(3), 2007, Pages 2033-2049.

• [A6] J. Grabowski and M. Wodecki. A very fast tabu search algorithm for the permutation flow shop problem with makespan criterion. Computers & Operations Research, 2004, 31, 1891-1909

• [A7] D. de Werra. An introduction to timetabling. European Journal of Operational Research, 1985, 19(2), 151-162

• [A8] G.Lach and M.E.Lübbecke. Curriculum based course timetabling: Optimal solutions to the Udine benchmark instances. TU Berlin, Institut für Mathematik, 2008(9)

• [A9] B. Kallehauge, J. Larsen, O.B. Madsen and M.M. Solomon. Vehicle Routing Problem with Time Windows. in [B11]

• [A10] S. Irnich. A Unified Modeling and Solution Framework for Vehicle Routing and Local Search-Based Metaheuristics. INFORMS Journal on Computing, 2008, 20(2), 270-287

• [A11] M. Lübbecke and J. Desrosiers. Selected Topics in Column Generation. Oper. Res., 2005, 53(6), 1007-1023

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

Web Links

• Complexity results for scheduling problems by Peter Brucker, Sigrid Knust.

• Movie: Periodic Timetable Optimization

• “Discrete Optimizers, A Goal by many Routes. How Mathematics makes Everyday Life Easier” Dr. Marco Lübbecke and his staff in a video series about “Scheduling Material Flows in Logistics Networks” (in German)

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

• List of questions (under update during the course)

• Syllabus (to be published)