Group for Research in Decision Analysis

High Multiplicity Scheduling Problems

Yves Crama

Dans le cadre de la semaine de l'Université de Liège et de la Faculté universitaire des sciences agronomiques de Gembloux et en collaboration avec le Centre d'études interdisciplinaires Wallonie-Bruxelles à l'UQAM.

It frequently happens that the input of a scheduling problem can be described in a compact way due to the fact that the jobs naturally fall into a small number of distinct job types, where all the jobs of a same type share exactly the same attribute values. When this is the case, we only need to describe one representative job of each type in order to define an instance, and we say that we are dealing with a "high multiplicity scheduling problem".

High multiplicity scheduling problems have been investigated by several researchers over the last decade. The purpose of this presentation is to present a selective overview of recent results. It is based on joint work with Nadia Brauner, Alexander Grigoriev, and Joris van de Klundert.