Scheduling - M1 - 6EC

Introduction

The term scheduling represents the assignment of resources over time to perform tasks, jobs or activities. Feasible schedules are compared with respect to a given optimality criterion. Mostly, the optimization problem is combinatorial and very complex. From a computational point of view, many of these problems are hard (NP-hard). In this course, an overview on the most classic scheduling models is given, and exact, as well as some heuristic solution methods are discussed for these models. 

In detail, the following topics are treated:
- Classification of scheduling models
- Single-machine models
- Parallel-machines models
- Open shop, flow shop and job shop models

- Scheduling under uncertainty

- Applications of scheduling

Aim of the course

In this course, students will learn techniques for a broad variety of scheduling problems. In particular, it is expected that after this course students will be able to construct mathematical models for the basic problems, classify them, address the questions on computational complexity of the problems, and apply standard algorithmic techniques to solve the problems.

Prerequisites

Basic knowledge (bachelor level) of analysis, linear algebra, and probability. Linear programming (modelling, not necessarily solving, see e.g. Chapter 1 of Linear Programming: Foundations and Extensions by Robert J. Vanderbei) and dynamic programming (see e.g. Chapter 5 of Integer Programming by Laurence A. Wolsey).

 

Rules about Homework / Exam

Examination consists of two parts: take home exercises and a written exam.
There will be two sets of homework exercises and these are supposed to be made in groups of 3 students. Larger groups are not allowed. The average grade for the homework exercises counts for 20% of the final grade. To be allowed to participate in the exam, you need to have at least a 5.0 average for the homework exercises.
The exam counts for 80% of the final grade. Note that the grade for the exam has to be at least a 5.0 to pass the course. A retake possibility is available for the exam, which counts for 80% of the grade, just like the exam. The homework will still count as part of the grade after the retake.

Literature

  1. M.L. Pinedo. Scheduling. Theory, Algorithms, and Systems. Springer.

  2. P. Brucker. Scheduling Algorithms. Springer. 

  3. M.L. Pinedo. Planning and Scheduling in Manufacturing and Services. Springer.

  4. Additional lecture notes

All these books are freely available online through your university.

Lecturers

Theresia van Essen (Delft University of Technology)

Ruben Hoeksma (University of Twente)