Makespan Minimization in Job Shops: A Linear Time Approximation Scheme

DOI10.1137/S0895480199363908MaRDI QIDQ4443085zbMATH OpenOpenAlexFDO

Authors Roberto Solis-Oba, Maxim Sviridenko, 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)

Recommendations

• Makespan minimization in job shops: a polynomial time approximation scheme
• scientific article; zbMATH DE number 1418275
• scientific article; zbMATH DE number 1560345
• A linear time approximation scheme for makespan minimization in an open shop with release dates
• scientific article; zbMATH DE number 1512677

Cited in

(21)

• Parallel machine scheduling with minimum number of tardy jobs: approximation and exponential algorithms
• Scheduling on unrelated machines under tree-like precedence constraints
• scientific article; zbMATH DE number 1560345 (Why is no real title available?)
• Grouping techniques for scheduling problems: simpler and faster
• Makespan minimization in job shops: a polynomial time approximation scheme
• Parameterized complexity of machine scheduling: 15 open problems
• Approximation schemes for scheduling jobs with chain precedence constraints
• Approximations for the two-machine cross-docking flow shop problem
• scientific article; zbMATH DE number 1418275 (Why is no real title available?)
• A linear time approximation scheme for makespan minimization in an open shop with release dates
• Minimizing Makespan in No-Wait Job Shops
• Combinations of some shop scheduling problems and the shortest path problem: complexity and approximation algorithms
• Approximating a two-machine flow shop scheduling under discrete scenario uncertainty
• A study on several combination problems of classic shop scheduling and shortest path
• Makespan minimization in open shops: A polynomial time approximation scheme
• A complexity analysis and algorithms for two-machine shop scheduling problems under linear constraints
• Linear programming-based algorithms for the minimum makespan high multiplicity jobshop problem
• On some properties of optimal schedules in the job shop problem with preemption and an arbitrary regular criterion
• Algorithms and Computation
• From fluid relaxations to practical algorithms for job shop scheduling: The makespan objective
• Moderate exponential-time algorithms for scheduling problems

This page was built for publication: Makespan Minimization in Job Shops: A Linear Time Approximation Scheme

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