Exact lexicographic scheduling and approximate rescheduling

DOI10.1016/J.EJOR.2020.08.032zbMATH Open1487.90303arXiv1805.03437OpenAlexW3080772958MaRDI QIDQ2029366FDOQ2029366

Miten Mistry, Dimitrios Letsios, Ruth Misener

Publication date: 3 June 2021

Published in: European Journal of Operational Research (Search for Journal in Brave)

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

Full work available at URL: https://arxiv.org/abs/1805.03437

Recommendations

• Investigating the recoverable robust single machine scheduling problem under interval uncertainty
• Robust Scheduling to Hedge Against Processing Time Uncertainty in Single-Stage Production
• Rescheduling for machine disruption to minimize makespan and maximum lateness
• Rescheduling for multiple new orders
• A lexicographic approach to the robust resource-constrained project scheduling problem

zbMATH Keywords

robust optimizationschedulingprice of robustnesslexicographic optimizationexact MILP methods

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Robustness in mathematical programming (90C17)

Cites Work

• Benchmarking optimization software with performance profiles.
• The Nucleolus of a Characteristic Function Game
• On Equitable Resource Allocation Problems: A Lexicographic Minimax Approach
• Theory and Applications of Robust Optimization
• Title not available (Why is that?)
• The Price of Robustness
• Robust discrete optimization and network flows
• Title not available (Why is that?)
• Technical Note—Convex Programming with Set-Inclusive Constraints and Applications to Inexact Linear Programming
• Convex hulls of superincreasing knapsacks and lexicographic orderings
• On the lexicographic minimax approach to location problems
• Bounds on Multiprocessing Timing Anomalies
• Scheduling algorithms
• Adjustable robust solutions of uncertain linear programs
• On the Robust Knapsack Problem
• The concept of recoverable robustness, linear programming recovery, and railway applications
• Equivalent weights for lexicographic multi-objective programs: Characterizations and computations
• Lexicographic bottleneck problems
• Lexicographically Minimum and Maximum Load Linear Programming Problems
• Preemptive and nonpreemptive multi-objective programming: Relationships and counterexamples
• Ideal representations of lexicographic orderings and base-2 expansions of integer variables
• Integer programming for minimal perturbation problems in university course timetabling
• Complexity and approximation in reoptimization
• Convex hull characterizations of lexicographic orderings
• On the recoverable robust traveling salesman problem
• Finite Adaptability in Multistage Linear Optimization
• Online Scheduling with Bounded Migration
• K-Adaptability in Two-Stage Robust Binary Programming
• A new dominance procedure for combinatorial optimization problems
• On recoverable and two-stage robust selection problems with budgeted uncertainty
• Reallocation problems in scheduling
• A hard integer program made easy by lexicography
• Robust scheduling with budgeted uncertainty
• Robust Polynomial-Time Approximation Schemes for Parallel Machine Scheduling with Job Arrivals and Departures
• Computing leximin-optimal solutions in constraint networks
• A theory and algorithms for combinatorial reoptimization
• Binary decision rules for multistage adaptive mixed-integer optimization
• Candidate to Job Allocation Problem with a Lexicographic Objective
• Generalized Lexicographic MultiObjective Combinatorial Optimization. Application to Cryptography

Cited In (5)

• A greedy and distributable approach to the Lexicographic Bottleneck Assignment Problem with conditions on exactness
• Parallel Machine Scheduling Under Uncertainty: Models and Exact Algorithms
• Extension of Rescheduling Based on Minimal Graph Cut
• Approximate and robust bounded job start scheduling for Royal Mail delivery offices
• Target-based distributionally robust optimization for single machine scheduling

Uses Software

• GitHub

This page was built for publication: Exact lexicographic scheduling and approximate rescheduling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2029366)