Exact lexicographic scheduling and approximate rescheduling

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.

Automated summary

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.