Inapproximability results for no-wait job shop scheduling.

DOI10.1016/j.orl.2003.10.003zbMath1054.90042OpenAlexW2024793042MaRDI QIDQ703234

Gerhard J. Woeginger

Publication date: 11 January 2005

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2003.10.003

zbMATH Keywords

Approximation algorithmsAPX hardnessShop scheduling

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25)

Related Items (6)

The proportionate two-machine no-wait job shop scheduling problem ⋮ A survey of scheduling problems with no-wait in process ⋮ No-wait job shop scheduling: tabu search and complexity of subproblems ⋮ An efficient simple metaheuristic for minimizing the makespan in two-machine no-wait job shops ⋮ Model formulations for the machine scheduling problem with limited waiting time constraints ⋮ SCHEDULING TWO-MACHINE FLOW SHOPS WITH EXACT DELAYS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• Approximability of flow shop scheduling
• Makespan minimization in open shops: A polynomial time approximation scheme
• The hardness of approximation: Gap location
• Makespan minimization in job shops
• The Three-Machine No-Wait Flow Shop is NP-Complete
• Complexity of Scheduling Shops with No Wait in Process
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Short Shop Schedules
• Makespan Minimization in No-Wait Flow Shops: A Polynomial Time Approximation Scheme
• Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem
• A Survey of Machine Scheduling Problems with Blocking and No-Wait in Process

This page was built for publication: Inapproximability results for no-wait job shop scheduling.