TY - JOUR
T1 - Exact algorithms for a parallel machine scheduling problem with workforce and contiguity constraints
AU - Caselli, Giulia
AU - Delorme, Maxence
AU - Iori, Manuel
AU - Magni, Carlo Alberto
N1 - Publisher Copyright:
© 2023 The Author(s)
PY - 2024/3
Y1 - 2024/3
N2 - 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.
AB - 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.
KW - Combinatorial Benders’ decomposition
KW - Constraint programming
KW - Integer linear programming
KW - Resource constraints
KW - Scheduling
U2 - 10.1016/j.cor.2023.106484
DO - 10.1016/j.cor.2023.106484
M3 - Article
AN - SCOPUS:85178380898
SN - 0305-0548
VL - 163
JO - Computers & Operations Research
JF - Computers & Operations Research
M1 - 106484
ER -