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

G-2017-82

An exact dynamic programming algorithm for the precedence-constrained class sequencing problem

, et

This article discusses the precedence-constrained class sequencing problem (PCCSP). In scheduling terms, this is a one-machine scheduling problem with precedence constraints and setups with the goal of minimizing the number of setups. From a practical perspective, PCCSP covers a wide range of applications such as, for example, scheduling problems in systems where multipurpose processors need retooling to switch from one operation to another. Previous research has shown that PCCSP is difficult to solve from both a theoretical and computational perspective, and only little research has been conducted on computational methods. This article bridges this gap by proposing a dynamic programming algorithm for solving PCCSP exactly. It comprises specialized dominance rules, lower bound computations, propagation algorithms, and heuristics that successfully exploit the problem's structure. Based on extensive numerical experiments, we analyze the algorithm in detail and show that it outperforms mixed-integer programming and constraints programming models.

, 32 pages

Ce cahier a été révisé en octobre 2019