An exact dynamic programming algorithm for the precedence-constrained class sequencing problem. (December 2020)

• Record Type: Journal Article
• Authors: Bürgy, Reinhard; Hertz, Alain; Baptiste, Pierre
• Is Part Of: Computers & operations research. Volume 124(2020)
• Publication Date: 2020-12
• Subjects: Sequencing -- Identical family setup times -- Precedence constraints -- One-machine scheduling -- Dynamic programming; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2020.105063
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: Dynamic programming algorithm for precedence-constrained class sequencing problem. Based on sub-procedures tailored to the structure of the problem. New lower bounding technique. Algorithm solves large instances to proven optimality. Abstract: This article discusses the precedence-constrained class sequencing problem (PCCSP). In scheduling terms, this is a single-machine problem with precedence constraints and family 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 with job families where multipurpose processors need retooling to switch from a job of one family to a job of another family. Previous research has shown that PCCSP is NP-hard and that no polynomial-time algorithm with constant worst-case performance exists unless P = NP . So far, only little research has been conducted on the development of specific computational methods for PCCSP. This article bridges this gap by proposing a dynamic programming algorithm for solving PCCSP exactly. It comprises specialized lower bound computations, node merging and precedence reasoning 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 constraint programming models.