DM204 – Scheduling, Timetabling and Routing

Marco Chiarandini (marco@imada.sdu.dk)

Schedule

Third quarter 2008		Fourth quarter 2008
Tuesday 10:15-12:00		Wednesday 12:15-14:00
Friday 8:15-10:00.		Friday 10:15-12:00.

First lecture 03.02.2009.

All lectures take place in IMADA Seminarrum.

Lectures

Third quarter

Lec.	Date	Topic	Slides	Literature
0.	01.12.2008	Course Presentation	[slides]
1.	03.02.2009	Scheduling: Terminology, Classification	[slides]	[chp2 of B2]
2.	06.02.2009	Scheduling: Complexity classes	[slides]	[examples from chp1 of B2, pp. 90-91 of B4, Appendix E of B2]
3.	13.02.2009	Scheduling: RCPSP Model. General Methods: Mixed Integer Programming	[slides]	[chp1 from B5, slides]
4.	17.02.2009	General Methods: Mixed Integer Programming (2)	[slides by Lap Chi Lau]	[assignment n.1]
5.	20.02.2009	General Methods: Exercises	[slides]	[assignment n.2]
6.	20.02.2009	General Methods: Constraint Programming	[slides]	[chp. 5 from B6]
7.	27.02.2009	General Methods: Constraint Programming (2)	[slides]	[sec. 3.9, 3.13, 3.14 and chp. 5 from B7]
8.	03.03.2009	General Methods: Exercises		[CP] [data] [model to complete] [assignment n.3]
9.	06.03.2009	General Methods: Heuristics	[slides]	[slides on GLSM by Hoos & Stuetzle] [smtwc] [instances] [chp. 1 and chp. 7 of B8]
10.	10.03.2009	Scheduling: Single Machine Models, Dynamic Programming	[slides]	[B2, chp. 3 and Appendix B] [A1, sec. 3]
11.	13.03.2009	Scheduling: Single Machine Models, Branch and Bound	[slides]	[chp. 3 and 4, B2]
12.	17.03.2009	Scheduling: Single Machine Models, Column Generation	[slides]	[A3, A4]
13.	20.03.2009	Scheduling: Single Machine Models, Column Generation (2)	[slides]	[A3, A4]
14.	24.03.2009	Scheduling: Parallel Machine and Flow Shop Models	[slides]	[assignment n.4] [sec. 5.1 and 5.2 from B2; chp.6 from B9; A5]

Fourth quarter

Lec.	Date	Topic	Slides	Literature
15.	15.04.2009	Scheduling: Flow Shop + Job Shop (Local Search)	[slides]	[A6] [A8] [B5, pages 189-200]
16.	17.04.2009	Scheduling: Job Shop Models and Generalizations	[slides]	[A7] [A9] [B5, pages 203-208] [assignment n.5]
17.	22.04.2009	Scheduling: Resource Constraint Project Scheduling Models	[slides]	[B5, pages 142-156]
18.	24.04.2009	Timetabling: Reservations and Education	[slides]	[B1, chp. 9, sec. 9.1-9.5, pages 205-221] [A10]
19.	29.04.2009	Timetabling: University Timetabling	[slides]	[A12]
20.	01.05.2009	Timetabling: Tanker Scheduling and Air Transport	[slides]	[B10, pages 176-177] [B1, sec. 11.2, 11.3] [A13]
21.	06.05.2009	Timetabling: Public Transports	[slides]	[B10, Chp. 17] [A14, sec. 1, 2 or Course TUB]
22.	07.05.2009	Steffen Godskesen’s Introduction to Comet	[slides, examples]
23.	13.05.2009	Timetabling: Workforce Scheduling	[slides]	[A15, sec. 1,2,3][B1, chp. 12]
24.	15.05.2009	Timetabling: Workforce Scheduling + Routing: Classification	[slides]	[B7, sec. 2.2.5, 3.8, 3.10], [B3, chp. 1]
25.	20.05.2009	Routing: Mathematical Programming CVRP	[slides]	[B3, chp. 1] [excerpts of B3, chp 2,3,4]
26.	22.05.2009	Routing: Mathematical Programming for VRPTW	[slides]	[A16] or [B3, chp. 7]
27.	27.05.2009	Routing: Heuristics	[slides]	[B3, chp. 5] [A17]
28.	29.05.2009	Routing: Rich problems	[slides]	[A19]
			[All slides]

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] Garey, M. R. & Johnson, D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness Freeman, San Francisco, CA, USA, 1979

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

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

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

[B8] Michiels, W.; Aarts, E. & Korst, J. Theoretical Aspects of Local Search Springer Berlin Heidelberg, 2007

[B9] P. Brucker. Scheduling Algorithms. Springer 2007

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

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

Scientific Articles

[A1] 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

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

[A3] Desrosiers, J. & Lübbecke, M. E. A Primer in Column Generation. in [B11]

[A4] Akker, M.; Hoogeveen, H. & Velde, S. Applying Column Generation to Machine Scheduling. in [B11]

[A5] 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] J. Adams, E. Balas and D. Zawack. The shifting bottleneck procedure for job shop scheduling. Manage. Sci., INFORMS, 1988, 34(3), 391-401

[A8] J. Grabowskil and M. Wodecki. A Very Fast Tabu Search Algorithm for Job Shop Problem. Metaheuristic Optimization via Memory and Evolution, 2005, 117-144

[A9] C. Meloni, D. Pacciarelli and M. Pranzo. A Rollout Metaheuristic for Job Shop Scheduling Problems. Annals of Operations Research, 2004, 131(1), 215-235

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

[A11] G. Lach and M. Lübbecke. Optimal University Course Timetables and the Partial Transversal Polytope. C. McGeoch (ed.). 7th International Workshop on Efficient and Experimental Algorithms (WEA08), Springer, 2008, 5038, 235-248

[A12] 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)

[A13] G. Desaulniers, J. Desrosiers, Y. Dumas, M.M. Solomon and F. Soumis. Daily Aircraft Routing and Scheduling. Management Science, 1997, 43(6), 841-855

[A14] C. Liebchen and R. Möhring. The Modeling Power of the Periodic Event Scheduling Problem: Railway Timetables and Beyond. Algorithmic Methods for Railway Optimization, LNCS 4359, Springer, 2007, 3-40

[A15] C. Liebchen, M. Proksch and F.H. Wagner. Performance of Algorithms for Periodic Timetable Optimization. M. Hickman, P. Mirchandani and S. Voss (ed.). Computer-aided Systems in Public Transport, 2008, 600, 151-180

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

[A17] G. Kindervater and M. Savelsbergh. Vehicle Routing: Handling Edge Exchanges. E. Aarts and J. Lenstra (ed.). Local Search in Combinatorial Optimization, Wiley, 1997(), 337-360

[A18] P. Shaw. Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems. Principles and Practice of Constraint Programming CP98, 1998, 417-431

[A19] 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

Web Links

Constraint Programming References
Comet
Complexity results for scheduling problems by Peter Brucker, Sigrid Knust.
Result of the second International Timetabling Competition 2007
Unitime, a University Timetabling system by Tomáš Müller
Course on Transport Optimization at TU Berlin
Matheon project on public transport
Math Programming Blog
Michael Trick’s Operations Research Blog

Exam

Project

Project A [text] [instances] (issued: March 27, 2009)
Project B [text] [instance] (issued: March 27, 2009)

List of errors to avoid in writing the report (issued: May 31, 2009, at 12:00)

Submission Deadline: Monday, June 15, 2009 at 17:00

Oral

List of questions (issued May 31, 2009)