Makespan Minimization in Job Shops: A Linear Time Approximation Scheme
From MaRDI portal
Publication:4443085
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
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
