Robust scheduling with budgeted uncertainty

DOI10.1016/j.dam.2018.07.001zbMath1411.68181OpenAlexW2702954033MaRDI QIDQ2414457

Marin Bougeret, Michael Poss, Artur Alves Pessoa

Publication date: 17 May 2019

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://hal-lirmm.ccsd.cnrs.fr/lirmm-02020566/file/journal_v3_Fig.pdf

zbMATH Keywords

schedulingrobust optimizationapproximation algorithms

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (23)

Online makespan minimization with budgeted uncertainty ⋮ Investigating the recoverable robust single machine scheduling problem under interval uncertainty ⋮ Constant-Ratio Approximation for Robust Bin Packing with Budgeted Uncertainty ⋮ Branch-and-price approach for robust parallel machine scheduling with sequence-dependent setup times ⋮ Stability factor for robust balancing of simple assembly lines under uncertainty ⋮ Parallel Machine Scheduling Under Uncertainty: Models and Exact Algorithms ⋮ Robust combinatorial optimization with locally budgeted uncertainty ⋮ Robust single machine makespan scheduling with release date uncertainty ⋮ The distributionally robust machine scheduling problem with job selection and sequence-dependent setup times ⋮ A two-stage robust approach for minimizing the weighted number of tardy jobs with objective uncertainty ⋮ Robust permutation flow shop total weighted completion time problem: solution and application to the oil and gas industry ⋮ A single representative min-max-min robust selection problem with alternatives and budgeted uncertainty ⋮ Single machine robust scheduling with budgeted uncertainty ⋮ A robust optimization approach for the unrelated parallel machine scheduling problem ⋮ A perfect information lower bound for robust lot-sizing problems ⋮ Minimizing the weighted sum of completion times under processing time uncertainty ⋮ Exact lexicographic scheduling and approximate rescheduling ⋮ Robust allocation of operating rooms: a cutting plane approach to handle lognormal case durations ⋮ Solution algorithms for minimizing the total tardiness with budgeted processing time uncertainty ⋮ Approximation results for makespan minimization with budgeted uncertainty ⋮ Robust two-stage location allocation for emergency temporary blood supply in postdisaster ⋮ Approximation algorithms for cost-robust discrete minimization problems based on their LP-relaxations ⋮ An adaptive robust optimization model for parallel machine scheduling

Cites Work

• Unnamed Item
• Unnamed Item
• Robust combinatorial optimization with variable cost uncertainty
• The robust vehicle routing problem with time windows
• On the robust single machine scheduling problem
• Event-based MILP models for resource-constrained project scheduling problems
• Approximation algorithms for scheduling unrelated parallel machines
• Algorithms and complexity analysis for robust single-machine scheduling problems
• Complexity of single machine scheduling problems under scenario-based uncertainty
• A robust approach to the chance-constrained knapsack problem
• Geometric algorithms and combinatorial optimization
• Robust solutions of uncertain linear programs
• Robust discrete optimization and its applications
• Robust discrete optimization and network flows
• Robust combinatorial optimization with variable budgeted uncertainty
• Optimization over Integers with Robustness in Cost and Few Constraints
• Optimal Allocation of Surgery Blocks to Operating Rooms Under Uncertainty
• Approximating Single Machine Scheduling with Scenarios
• The Price of Robustness
• Polynomial algorithms in linear programming
• Exact and Approximate Algorithms for Scheduling Nonidentical Processors
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Robust constrained shortest path problems under budgeted uncertainty
• Robust Scheduling to Hedge Against Processing Time Uncertainty in Single-Stage Production
• Towards a Robust Scheduling on Unrelated Parallel Machines: A Scenarios Based Approach
• Scheduling

This page was built for publication: Robust scheduling with budgeted uncertainty