Better Approximation Guarantees for Job-Shop Scheduling

DOI10.1137/S0895480199326104zbMath0967.68084MaRDI QIDQ2706190

Leslie Ann Goldberg, Aravind Srinivasan, Elizabeth Sweedyk, Mike S. Paterson

Publication date: 19 March 2001

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

zbMATH Keywords

schedulingapproximationjob-shopjob-shop schedulingguarantees

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05)

Related Items

Scheduling Parallel-Task Jobs Subject to Packing and Placement Constraints ⋮ Scheduling on unrelated machines under tree-like precedence constraints ⋮ APPROXIMATION ALGORITHMS FOR FLEXIBLE JOB SHOP PROBLEMS ⋮ Grouping techniques for scheduling problems: simpler and faster ⋮ Approximation Algorithms for Generalized Path Scheduling ⋮ High-multiplicity cyclic job shop scheduling ⋮ Approximation schemes for job shop scheduling problems with controllable processing times ⋮ On some properties of optimal schedules in the job shop problem with preemption and an arbitrary regular criterion