4.7 Article

Branch-and-price approach for robust parallel machine scheduling with sequence-dependent setup times

Journal

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
Volume 301, Issue 3, Pages 875-895

Publisher

ELSEVIER
DOI: 10.1016/j.ejor.2021.11.023

Keywords

Integer programming; Robust optimization; Branch-and-price; Parallel machine scheduling

Ask authors/readers for more resources

This paper investigates a machine scheduling problem on unrelated parallel machines with the objective of minimizing the worst-case total tardiness. The authors propose a robust optimization model and discuss important properties of the mathematical formulation. The paper also addresses the issue of alternative optimal solutions for scheduling problems and presents a branch-and-price algorithm to solve realistic instances effectively. Numerical results demonstrate the effectiveness of the proposed approach in terms of optimality and improvement in objective function value.
This paper studies a machine scheduling problem that minimizes the worst-case total tardiness for unrelated parallel machines with sequence-dependent setup and uncertain processing times. We propose a robust optimization reformulation of the related machine scheduling problem and discuss several important properties of the mathematical model and the reformulation approach. The proposed model generalizes robust parallel machine scheduling problems by including sequence-dependent setup times and ellipsoidal uncertainty sets. Another key contribution of the paper is to show that scheduling problems usually have alternative optimal solutions for the worst-case tardiness objective, whose performance under nominal processing times may vary or vice a versa. This issue has been addressed by studying the Pareto efficient extensions of the proposed robust optimization models to provide solutions that are immune to changes in processing times. A branch-and-price algorithm has been developed to solve realistically sized instances in less than one hour, which a commercial solver cannot achieve. Numerical results show the effectiveness of the proposed approach since realistically sized instances such as (4 machines, 32 jobs) and (150 machines, 300 jobs) can be solved to optimality within the time limit, and the (average) objective function value improvement made by the robust approach can get as high as 56% compared with the (nominal) optimal solutions that ignore uncertainty in problem data.(c) 2021 Elsevier B.V. All rights reserved.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.7
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available