DM204 – Scheduling, Timetabling, Routing
Study Plan for the Oral Exam, Fall 2010 [pdf format]

This is the list of questions that can be posed at the oral exam.

The exam will last 40 minutes and the questions will be extracted randomly from the list. It is allowed to bring hand written notes but not course material (slides, textbook, articles). The notes will lay on the table and can be consulted if needed. At each question there are 2-3 minutes to prepare the answer. Refinement questions on the topics presented should be expected.

1. Present and explain your best learning matching the goals of the course. You have a maximum of 10 minutes to address this question. The item can be chosen from the list below but it is possible to show creativity going out of the list (for example, by following a topic and developing it transversely to the arguments in the list).
2. Scheduling problems. Discuss:
   • Three alternative models for formulating single machine problems by Mathematical Programming. Advantages and disadvantages of the models. The question implies a definition of scheduling problems.
3. Single and parallel machine scheduling problem. Define and discuss one of the cases below:
   • Describe the dynamic programming algorithm for the case 1|prec|h_max.
   • Describe the branch and bound algorithm for the case 1|r_i|L_max.
   • Sketch the dynasearch by Congram, Potts and van de Velde for 1||∑_jw_jT_j.
   • Describe the Critical Path Method and PERT.
4. Flow shop scheduling problem. Define it and describe the digraph representation and the procedure for obtaining the makespan from a permutation of jobs when changes at machines are not allowed. Moreover, choose and treat one of the cases below:
   • Johnson’s rule for the case F2||C_max.
   • Tabu search for the case Fm|perm|C_max. Describe shortly the properties for the fast examination of the neighborhood,
   • Consider the case Fm|perm|C_max. Describe the Navaz, Enscore and Ham heuristic and how this heuristic can be enhanced through the iterated greedy metaheuristic.
5. Job shop scheduling problem. Define it and describe the disjunctive graph model, the alternative graph model and one of the following:
   • Consider the job shop case Jm||C_max. Describe a possible application of local search, by defining the candidate solutions, the solution representation, the neighborhood and possible pruning of the neighborhood.
   • Describe the Shifting Bottleneck heuristic for Jm||C_max (Adams, Balas and Zawack 1988).
6. Resource Constrained Project Scheduling Problem. Define it and describe the solution approach with heuristic methods, preprocessing, solution representation, neighborhoods, solution generation schemes.
7. Timetabling and coloring models. Discuss one of the following
   • Reservation problems
   • University Course timetabling. Problem definition, IP approaches, Heuristic approaches (solution representation, strategies).
8. Workforce timetabling. Discuss one of the following:
   • Shift scheduling problem. Definition, integer program formulation and observation on integrality of the linear relaxation.
   • Crew scheduling. Definition, mathematical programming formulation and column generation solution approach.
9. Capacitated Vehicle routing problem. Define it and discuss different mathematical programming models by stating variables and constraints.
10. Branch and Price for VRPTW. Describe the mathematical model, the decomposition, the master and the subproblems and the overall branch and price procedure
11. Heuristics for VRP. Treat one of the following:
    • Give a general classification of construction heuristics for CVRP, describe two at choice and mention how they can be adapted to the VRPTW (in particular, how time windows constraints can be checked efficiently).
    • Discuss local search procedures for CVRP and VRPTW and mention how constraints such as capacity and time windows can be treated in constant time.
    • Rich Vehicle Routing Problems. Define them briefly and describe the uniform model and the framework for efficient local search algorithms. Give examples of a couple of rich problems that can be treated in the model.