Makespan Minimization in Job Shops: A Linear Time Approximation Scheme

DOI10.1137/S0895480199363908zbMath1051.68153OpenAlexW2053608913MaRDI QIDQ4443085

M. I. Sviridenko, Roberto Solis-Oba, Klaus Jansen

Publication date: 8 January 2004

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmjob shop schedulingapproximation scheme

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25)

Related Items

Scheduling on unrelated machines under tree-like precedence constraints ⋮ A study on several combination problems of classic shop scheduling and shortest path ⋮ Combinations of Some Shop Scheduling Problems and the Shortest Path Problem: Complexity and Approximation Algorithms ⋮ A complexity analysis and algorithms for two-machine shop scheduling problems under linear constraints ⋮ Approximating a two-machine flow shop scheduling under discrete scenario uncertainty ⋮ Approximations for the two-machine cross-docking flow shop problem ⋮ Grouping techniques for scheduling problems: simpler and faster ⋮ Parallel machine scheduling with minimum number of tardy jobs: approximation and exponential algorithms ⋮ APPROXIMATION SCHEMES FOR SCHEDULING JOBS WITH CHAIN PRECEDENCE CONSTRAINTS ⋮ Parameterized complexity of machine scheduling: 15 open problems ⋮ On some properties of optimal schedules in the job shop problem with preemption and an arbitrary regular criterion ⋮ Moderate exponential-time algorithms for scheduling problems