Approximating Single Machine Scheduling with Scenarios

DOI10.1007/978-3-540-85363-3_13zbMath1159.68671OpenAlexW1553572425MaRDI QIDQ3541793

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

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

Related Items

Online makespan minimization with budgeted uncertainty ⋮ Robust scheduling with budgeted uncertainty ⋮ On the approximability of robust spanning tree problems ⋮ Single machine robust scheduling with budgeted uncertainty ⋮ Approximating a two-machine flow shop scheduling under discrete scenario uncertainty ⋮ Solution algorithms for minimizing the total tardiness with budgeted processing time uncertainty

Cites Work

• Robust discrete optimization and its applications
• Robust discrete optimization and network flows
• Polynomial time approximation algorithms for machine scheduling: Ten open problems
• Precedence constrained scheduling to minimize sum of weighted completion times on a single machine
• A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine
• 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
• A new multilayered PCP and the hardness of hypergraph vertex cover
• Approximating Min-Max (Regret) Versions of Some Polynomial Problems
• Decompositions, Network Flows, and a Precedence Constrained Single-Machine Scheduling Problem
• An algorithm for the single machine sequencing problem with precedence constraints
• Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Introduction to Stochastic Programming
• 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
• Single-Machine Scheduling with Precedence Constraints
• Robust Combinatorial Optimization with Exponential Scenarios