Approximating Single Machine Scheduling with Scenarios

DOI10.1007/978-3-540-85363-3_13MaRDI QIDQ3541793zbMATH OpenOpenAlexFDO

Authors Monaldo Mastrolilli, Nikolaus Mutsanas, Ola Svensson

Publication date 27 November 2008

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-85363-3_13

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27)

Recommendations

• Single machine scheduling with scenarios
• Algorithms and complexity analysis for robust single-machine scheduling problems
• On the robust single machine scheduling problem
• Robust scheduling with budgeted uncertainty
• Complexity of single machine scheduling problems under scenario-based uncertainty

Cites work

• A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine
• A new multilayered {PCP} and the hardness of hypergraph vertex cover
• An algorithm for the single machine sequencing problem with precedence constraints
• Approximating Min-Max (Regret) Versions of Some Polynomial Problems
• Decompositions, Network Flows, and a Precedence Constrained Single-Machine Scheduling Problem
• Introduction to Stochastic Programming
• On the existence of an FPTAS for minmax regret combinatorial optimization problems with interval data
• On the power of unique 2-prover 1-round games
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Polynomial time approximation algorithms for machine scheduling: Ten open problems
• Precedence constrained scheduling to minimize sum of weighted completion times on a single machine
• Robust Combinatorial Optimization with Exponential Scenarios
• Robust discrete optimization and its applications
• Robust discrete optimization and network flows
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
• Scheduling to minimize total weighted completion time: performance guarantees of LP-based heuristics and lower bounds
• Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints
• Single-Machine Scheduling with Precedence Constraints

Cited in

(12)

• Minimizing worst-case and average-case makespan over scenarios
• Single machine scheduling with scenarios
• A family of inequalities valid for the robust single machine scheduling polyhedron
• An approximation scheme for the bi-scenario sum of completion times trade-off problem
• Solution algorithms for minimizing the total tardiness with budgeted processing time uncertainty
• Robust scheduling with budgeted uncertainty
• Scheduling over scenarios on two machines
• Approximating a two-machine flow shop scheduling under discrete scenario uncertainty
• Single machine robust scheduling with budgeted uncertainty
• On the approximability of robust spanning tree problems
• Online makespan minimization with budgeted uncertainty
• Complexity of single machine scheduling problems under scenario-based uncertainty

This page was built for publication: Approximating Single Machine Scheduling with Scenarios

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