Groupe d’études et de recherche en analyse des décisions

G-2017-37

The carousel scheduling problem

, et

Scheduling problems on which constraints are imposed with regard to the temporal distances between successive executions of the same task have numerous applications, ranging from task scheduling in real-time systems to automobile production on a mixed-model assembly line. This paper introduces a new NP-hard optimization problem belonging to this class of problems, namely the Carousel Scheduling Problem (CSP). We present a mathematical formulation for the CSP based on mixed-integer linear programming (MILP) as well as a series of cuts to improve its resolution via exact methods. Finally, we propose an iterative solution method which greatly reduces the number of variables in the CSP formulation. The reported computational experiments show that, for a given time horizon, the proposed iterative method increases the size of CSP instances solved up to optimality.

, 20 pages