In industrial scheduling, an initial planning phase may solve the nominal
problem and a subsequent recovery phase may intervene to repair inefficiencies
and infeasibilities, e.g. due to machine failures and job processing time
variations. This work investigates the minimum makespan scheduling problem with
job and machine perturbations and shows that the recovery problem is strongly
NP-hard, at least as hard as solving the problem with full input knowledge. We
explore recovery strategies with respect to the (i) planning decisions and (ii)
permitted deviations from the original schedule. The resulting performance
guarantees are parameterized by the degree of uncertainty. The analysis derives
from the optimal substructure imposed by lexicographic optimality, so
lexicographic optimization enables more efficient reoptimization. We revisit
state-of-the-art exact lexicographic optimization methods and propose a novel
lexicographic optimization approach based on branch-and-bound. Numerical
analysis using standard commercial solvers substantiates the method.