  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||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 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.
