Exact lexicographic scheduling and approximate rescheduling
From MaRDI portal
Publication:2029366
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. , 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.
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
Cites work
- scientific article; zbMATH DE number 2109192 (Why is no real title available?)
- A hard integer program made easy by lexicography
- A new dominance procedure for combinatorial optimization problems
- A theory and algorithms for combinatorial reoptimization
- Adjustable robust solutions of uncertain linear programs
- Benchmarking optimization software with performance profiles.
- Binary decision rules for multistage adaptive mixed-integer optimization
- Bounds on Multiprocessing Timing Anomalies
- Candidate to Job Allocation Problem with a Lexicographic Objective
- Complexity and approximation in reoptimization
- Computing leximin-optimal solutions in constraint networks
- Convex hull characterizations of lexicographic orderings
- Convex hulls of superincreasing knapsacks and lexicographic orderings
- Equivalent weights for lexicographic multi-objective programs: Characterizations and computations
- Finite Adaptability in Multistage Linear Optimization
- Generalized lexicographic multiobjective combinatorial optimization. Application to cryptography
- Ideal representations of lexicographic orderings and base-2 expansions of integer variables
- Integer programming for minimal perturbation problems in university course timetabling
- Lexicographic bottleneck problems
- Lexicographically Minimum and Maximum Load Linear Programming Problems
- On Equitable Resource Allocation Problems: A Lexicographic Minimax Approach
- On recoverable and two-stage robust selection problems with budgeted uncertainty
- On the lexicographic minimax approach to location problems
- On the recoverable robust traveling salesman problem
- On the robust knapsack problem
- Online scheduling with bounded migration
- Preemptive and nonpreemptive multi-objective programming: Relationships and counterexamples
- Reallocation problems in scheduling
- Robust discrete optimization and network flows
- Robust optimization
- Robust polynomial-time approximation schemes for parallel machine scheduling with job arrivals and departures
- Robust scheduling with budgeted uncertainty
- Scheduling algorithms
- Technical Note—Convex Programming with Set-Inclusive Constraints and Applications to Inexact Linear Programming
- The Nucleolus of a Characteristic Function Game
- The Price of Robustness
- The concept of recoverable robustness, linear programming recovery, and railway applications
- Theory and applications of robust optimization
- \(K\)-adaptability in two-stage robust binary programming
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
- Approximate and robust bounded job start scheduling for Royal Mail delivery offices
- Extension of Rescheduling Based on Minimal Graph Cut
- Target-based distributionally robust optimization for single machine scheduling
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)
