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

G-2017-82

An exact solution approach for the precedence-constrained class sequencing problem

, et

This article discusses the precedence-constrained class sequencing problem (PCCS). In scheduling terms, this problem models a one-machine problem with precedence constraints and setups where the goal is to minimize the number of setups. From a practical perspective, the PCCS problem can be used to address a wide range of applications such as, for example, decision problems in systems where multipurpose processors need retooling to switch from one operation to another.

Previous research has shown that the PCCS problem 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 branch-and-bound solution approach for the PCCS problem. Specialized reasoning, bounding, and heuristic procedures successfully exploit the problem's structure. Thus, the branch-and-bound approach solves large instances to optimality. The computational experiments further shed new light on what makes a PCCS instance difficult.

, 27 pages