Journal
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
Volume 290, Issue 2, Pages 469-478Publisher
ELSEVIER
DOI: 10.1016/j.ejor.2020.08.032
Keywords
Scheduling; Lexicographic optimization; Exact MILP methods; Robust optimization; Price of robustness
Funding
- Engineering and Physical Sciences Research Council Research (EPSRC) [EP/M028240/1, EP/P016871/1]
- EPSRC [EP/P016871/1, EP/K040723/1, EP/M028240/1] Funding Source: UKRI
Ask authors/readers for more resources
This study investigates the minimum makespan scheduling problem in industrial resource allocation, proposing a two-stage robust scheduling approach based on exact lexicographic scheduling and approximate rescheduling. The analysis is substantiated by parameterizing the price of robustness and utilizing lexicographic optimality for efficient rescheduling. Additionally, a lexigographic branch-and-bound algorithm is introduced for optimal substructure and computational validation.
In industrial resource allocation problems, an initial planning stage may solve a nominal problem instance and a subsequent recovery stage may intervene to repair inefficiencies and infeasibilities due to uncertainty, e.g. machine failures and job processing time variations. In this context, we investigate the minimum makespan scheduling problem, a.k.a. P vertical bar vertical bar C-max, under uncertainty. We propose a two-stage robust scheduling approach where first-stage decisions are computed with exact lexicographic scheduling and second-stage decisions are derived using approximate rescheduling. We explore recovery strategies ac- counting for planning decisions and constrained by limited permitted deviations from the original schedule. Our approach is substantiated analytically, with a price of robustness characterization parameterized by the degree of uncertainty, and numerically. This analysis is based on optimal substructure imposed by lexicographic optimality. Thus, lexicographic optimization enables more efficient rescheduling. Further, we revisit state-of-the-art exact lexicographic optimization methods and propose a lexicographic branchand-bound algorithm whose validated computationally. (C) 2020 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
Recommended
No Data Available