DM204 - Scheduling, Timetabling and Routing

Links
Schedule
Lectures
Literature
Evaluation

Schedule


Spring 2011, fourth quarter, weeks 14-21	Tuesday 16:15-18:00 in IMADA Seminarrum
First lecture: April 4, 2011.	Wednesday 10:00-12:00 in IMADA Seminarrum
Last lecture: May 27, 2010.	Thursday 12:00-14:00 in IMADA Seminarrum

Lectures


Lec.	Date	Topic	Literature and Assignments
L0	05.11.2010	Presentation
L1	05.04.2011	Scheduling: Classification, Complexity classes	[B1 ch1-2 ApA,D,E; B5 ch1-2; B2 ApC; A1; A2(e); B6, pp90-91(e)]
L2	06.04.2011	Scheduling: Single Machine Problems, Dynamic Programming	[B1 ch3 ApB.1]
E1	07.04.2011	Sport Timetabling	[A3; A4 (e); A5; B2 10.1-10.4]
L3	12.04.2011	Scheduling: Single Machine Problems, Branch and Bound, IP, LS	[B1 ch3; B2 sc4.1-4.3]
L4	14.04.2011	Scheduling: Parallel Machines, PERT	[B3; A8, sc4.1; B1 sc5.1; A6; B2 4.2-4.3]
L5@10	19.04.2011	Scheduling: Flow Shop and Job Shop Models	[B5 sc4.1-4.3; A9; B1 sc7.1, 7.2] [ exercise, solution in A16 ]
L6	26.04.2011	Scheduling: Resource-Constrained Project Scheduling Models	[B5 sc3.4; A10 (e); B7 sc3.13.1-3.13.3, 3.14.1-3.14.3]
L7	28.04.2011	Timetabling: Reservations and Education	[B2 sc9.1-9.5; A11; A12]
L8	03.05.2011	Timetabling: Education	[B2 sc12.1-12.6, A11, A12, Bjarne's conjecture ]
L8	04.05.2011	Timetabling: Education
L9@U10	05.05.2011	Timetabling: Workforce Scheduling, Crew Scheduling	[B2 sc11.1-11.4] [ exercise @ COatWork ]
L9	10.05.2011	Timetabling: Set Partitioning Models	[L2]
L10	11.05.2011	Timetabling: Public Transports	[A17, A13] [ RAS competition ] [ J. Clausen's DR talk ]
L11	12.05.2011	Routing: Classification & Mathematical Programming models	[B3 ch1(e), ch2,3,4]
L12	17.05.2011	Routing: Time Windows and Branch and Price	[A14]
L13	18.05.2011	Routing: Construction Heuristics	[B3 ch5(e)]
L14	19.05.2011	Routing: Local Search based Metaheuristics	[A15, A16]

Literature

Main books

[B1] Pinedo, M. Scheduling: Theory, Algorithms, and Systems Springer New York, 2008
[B2] Pinedo, M. Planning and Scheduling in Manufacturing and Services Springer Verlag, 2005
[B3] Toth, P. & Vigo, D. (ed.) The Vehicle Routing Problem SIAM Monographs on Discrete Mathematics and Applications, 2002

Further Books

[B4] Brucker, P. Scheduling Algorithms. Springer 2007
[B5] 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] J.N. Hooker, Integrated Methods for Optimization. Springer, 2007
[B8] Desrosiers, J. & Luebbecke, M. E. A Primer in Column Generation. in G. Desaulniers, J. Desrosiers and M.M. Solomon (ed.). Column Generation. Springer US, 2005.

Articles and Chapters

Methods:

[A1] Russell, S. & Norvig, P. Artificial Intelligence: A Modern Approach. Chapter 5 (Constraint Satisfaction Problems) Prentice Hall, Second Edition, 2003
[A2] H.P. Williams. Model building in mathematical programming. Chapter 9 (Building Integer Programming Models I) John Wiley & Sons, Chichester, 1999

Sport Timetabling

[A3] Trick, M. A. 2004. Using Sports Scheduling to Teach Integer Programming. INFORMS Trans. Ed. 5(1) 10-17.
[A4] K. Easton, G. Nemhauser and M. Trick. Sport Scheduling. J.Y.-T. Leung (ed.). Handbook of Scheduling: Algorithms, Models, and Performance Analysis, Chapman & Hall/CRC, 2004
[A5] R.V. Rasmussen and M.A. Trick. Round robin scheduling - a survey. European Journal of Operational Research, 2008, 188(3) , 617 - 636

Scheduling

[A6] 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
[A8] Akker, M.; Hoogeveen, H. & Velde, S. Applying Column Generation to Machine Scheduling. in G. Desaulniers, J. Desrosiers and M.M. Solomon (ed.). Column Generation. Springer US, 2005.
[A9] R. Ruiz and T. Stuetzle. A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. European Journal of Operational Research, 177(3), 2007, Pages 2033-2049.
[A10] P. Baptiste, P. Laborie, C.L. Pape and W. Nuijten. Constraint-Based Scheduling and Planning. Chp. 22, F. Rossi, P. van Beek and T. Walsh (ed.). Handbook of Constraint Programming, Elsevier, 2006

Timetabling

[A11] D. de Werra. An introduction to timetabling. European Journal of Operational Research, 1985, 19(2), 151-162
[A12] H. Cambazard, E. Hebrard, B. O'Sullivan and A. Papadopoulos. Local search and constraint programming for the post enrolment-based course timetabling problem. Annals of Operations Research, Springer Netherlands, 2010, 1-25
[A17] R. Lusby, J. Larsen, M. Ehrgott and D. Ryan. Railway track allocation: models and methods. OR Spectrum, Springer Berlin / Heidelberg, 2009, 1-41
[A13] C. Liebchen and R. Möhring. The Modeling Power of the Periodic Event Scheduling Problem: Railway Timetables and Beyond. F.G. et al. (ed.). Algorithmic Methods for Railway Optimization, Springer, 2007, 4359, 3-40
[A16] A. Mascis, D. Pacciarelli and M. Pranzo. Scheduling Models for Short-Term Railway Traffic Optimisation. M. Hickman, P. Mirchandani and S. Voß (ed.). Computer-aided Systems in Public Transport, Springer Berlin Heidelberg, 2008, 600, 71-90

Vehicle Routing

[A14] B. Kallehauge, J. Larsen, O.B. Madsen and M.M. Solomon. Vehicle Routing Problem with Time Windows. in G. Desaulniers, J. Desrosiers and M.M. Solomon (ed.). Column Generation. Springer US, 2005.
[A16] C. Groër, B. Golden and E. Wasil. A library of local search heuristics for the vehicle routing problem. Mathematical Programming Computation, Springer Berlin / Heidelberg, 2010, 2, 79-101
[A15] 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

Evaluation

The oral exam is scheduled for June 6, in room U42.

Students must prepare a portfolio of cases to be approved before May 25, 2011. At the oral exam students will be asked to talk about a few cases drawn randomly from their portfolio.

Example of portfolios from the past editions: 2010, 2009, 2008

The re-exam will be held following the same procedure on Monday, January 23, 2012.

Author: Marco Chiarandini

Date: 2011-05-31 08:48:34 CEST

HTML generated by org-mode 6.36c in emacs 22