Exact lexicographic scheduling and approximate rescheduling

TY - JOUR

T1 - Exact lexicographic scheduling and approximate rescheduling

AU - Letsios, Dimitrios

AU - Mistry, Miten

AU - Misener, Ruth

PY - 2021/4/16

Y1 - 2021/4/16

N2 - 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||Cmax, 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 accounting 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 branch-and-bound algorithm whose performance is validated computationally.

AB - 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||Cmax, 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 accounting 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 branch-and-bound algorithm whose performance is validated computationally.

KW - Exact MILP methods

KW - Lexicographic optimization

KW - Price of robustness

KW - Robust optimization

KW - Scheduling

UR - http://www.scopus.com/inward/record.url?scp=85096179703&partnerID=8YFLogxK

U2 - 10.1016/j.ejor.2020.08.032

DO - 10.1016/j.ejor.2020.08.032

M3 - Article

AN - SCOPUS:85096179703

SN - 0377-2217

VL - 290

SP - 469

EP - 478

JO - EUROPEAN JOURNAL OF OPERATIONAL RESEARCH

JF - EUROPEAN JOURNAL OF OPERATIONAL RESEARCH

IS - 2

ER -