Exact algorithms for a parallel machine scheduling problem with workforce and contiguity constraints

Giulia Caselli, Maxence Delorme*, Manuel Iori, Carlo Alberto Magni

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

1 Citation (Scopus)

Abstract

We address a real-world scheduling problem where the objective is to allocate a set of tasks to a set of machines and to a set of workers in such a way that the total weighted tardiness is minimized. Our case study encompasses four types of constraints: precedence, resource, eligibility, and contiguity. While the first three constraints are common in the scheduling literature, contiguity constraints, which can be defined as a form of precedence constraints that requires both a predecessor and its successor to be processed on the same machine with no intermediate jobs in-between (but idle time is allowed), have never been studied in the literature. We present four exact methods to solve the problem: two methods use integer linear programming, one uses constraint programming, and one uses a combinatorial Benders’ decomposition. We introduce method-specific strategies to model the contiguity constraints for each of the proposed methods. We empirically evaluate, through an extensive set of computational experiments, the performance of the four methods on a heterogeneous dataset composed of real, realistic, and random instances, and outline that every method offers a competitive advantage on a targeted subset of instances. We also show that our algorithms can be generalized to solve related scheduling problems with contiguity constraints.
Original languageEnglish
Article number106484
Number of pages15
JournalComputers & Operations Research
Volume163
DOIs
Publication statusPublished - Mar 2024

Keywords

  • Combinatorial Benders’ decomposition
  • Constraint programming
  • Integer linear programming
  • Resource constraints
  • Scheduling

Fingerprint

Dive into the research topics of 'Exact algorithms for a parallel machine scheduling problem with workforce and contiguity constraints'. Together they form a unique fingerprint.

Cite this