Approximation Bounds for a General Class of Precedence Constrained Parallel Machine Scheduling Problems

DOI10.1137/S0097539799358094zbMath1100.68010OpenAlexW2046471719MaRDI QIDQ5470732

Maurice Queyranne, Andreas S. Schulz

Publication date: 1 June 2006

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539799358094

zbMATH Keywords

schedulingapproximation algorithmprecedence constraintslinear programming relaxationperformance guarantee

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25)

Related Items (15)

Approximation algorithms for simple assembly line balancing problems ⋮ Minimising makespan on parallel machines with precedence constraints and machine eligibility restrictions ⋮ Some complexity results and an efficient algorithm for quay crane scheduling problem ⋮ Scheduling Parallel-Task Jobs Subject to Packing and Placement Constraints ⋮ Scheduling under the network of temporo-spatial proximity relationships ⋮ Approximation Algorithms for Scheduling with Resource and Precedence Constraints ⋮ Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations ⋮ The precedence constrained knapsack problem: separating maximally violated inequalities ⋮ Approximability of average completion time scheduling on unrelated machines ⋮ Scheduling of parallel machines to minimize total completion time subject to s-precedence constraints ⋮ Scheduling with bully selfish jobs ⋮ Unnamed Item ⋮ Approximating total weighted completion time on identical parallel machines with precedence constraints and release dates ⋮ Hybrid Flow Shop Scheduling: Heuristic Solutions and LP-Based Lower Bounds ⋮ Scheduling MapReduce jobs on identical and unrelated processors

This page was built for publication: Approximation Bounds for a General Class of Precedence Constrained Parallel Machine Scheduling Problems