Exact lexicographic scheduling and approximate rescheduling

Dimitrios Letsios*, Miten Mistry, Ruth Misener

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)469-478
Number of pages10
Issue number2
Publication statusPublished - 16 Apr 2021


  • Exact MILP methods
  • Lexicographic optimization
  • Price of robustness
  • Robust optimization
  • Scheduling


Dive into the research topics of 'Exact lexicographic scheduling and approximate rescheduling'. Together they form a unique fingerprint.

Cite this