The Three-Machine No-Wait Flow Shop is NP-Complete

DOI10.1145/62.65zbMath0632.68038OpenAlexW1972819258WikidataQ130947726 ScholiaQ130947726MaRDI QIDQ3769960

H. Röck

Publication date: 1984

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/62.65

zbMATH Keywords

traveling salesmanNP-hardpermutation flow shopno wait in process

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items (50)

Some no-wait shops scheduling problems: Complexity aspect ⋮ Flow shop scheduling with flexible processing times ⋮ Three-machine flow shop scheduling with overlapping waiting time constraints ⋮ Complexity of flow shop scheduling problems with transportation constraints ⋮ Evolutionary hybrid particle swarm optimization algorithm for solving NP-hard no-wait flow shop scheduling problems ⋮ Multi-agent scheduling in a no-wait flow shop system to maximize the weighted number of just-in-time jobs ⋮ Scheduling in supply chain environment ⋮ Lot sizing in a no-wait flow shop ⋮ On no-wait and no-idle flow shops with makespan criterion ⋮ Permutation flow shop scheduling with dominant machines to minimize discounted total weighted completion time ⋮ Flow shop scheduling problems with decreasing linear deterioration under dominant machines ⋮ Two-stage no-wait scheduling models with setup and removal times separated ⋮ Predictive-reactive scheduling for single surgical suite subject to random emergency surgery ⋮ A branch-and-cut approach for the distributed no-wait flowshop scheduling problem ⋮ Unnamed Item ⋮ Benders decomposition for the mixed no-idle permutation flowshop scheduling problem ⋮ On Eulerian extensions and their application to no-wait flowshop scheduling ⋮ A note: Maximizing the weighted number of just-in-time jobs on a proportionate flowshop ⋮ Unnamed Item ⋮ \(\mathrm{A}^\ast\) search for prize-collecting job sequencing with one common and multiple secondary resources ⋮ Some effective heuristics for no-wait flowshops with setup times to minimize total completion time ⋮ Scheduling for parallel dedicated machines with a single server ⋮ Part sequencing in three-machine no-wait robotic cells ⋮ An efficient simple metaheuristic for minimizing the makespan in two-machine no-wait job shops ⋮ No-wait or no-idle permutation flowshop scheduling with dominating machines ⋮ Inapproximability results for no-wait job shop scheduling. ⋮ Scheduling two-machine no-wait open shops to minimize makespan ⋮ Makespan minimization for the \(m\)-machine ordered flow shop scheduling problem ⋮ New heuristics for no-wait flow shops with a linear combination of makespan and maximum lateness ⋮ Parameterized complexity of machine scheduling: 15 open problems ⋮ Scheduling algorithms for flexible flowshops: Worst and average case performance ⋮ No-Wait Flowshop Scheduling Is as Hard as Asymmetric Traveling Salesman Problem ⋮ Job sequencing with one common and multiple secondary resources: an A*/beam search based anytime algorithm ⋮ A novel differential evolution algorithm for bi-criteria no-wait flow shop scheduling problems ⋮ Two machine flow shop scheduling problem with no wait in process: Controllable machine speeds ⋮ Flowshop-scheduling problems with makespan criterion: a review ⋮ Minimizing makespan for a no-wait flowshop using genetic algorithm ⋮ Permutation, no-wait, no-idle flow shop problems ⋮ No-wait two-stage flowshop problem with multi-task flexibility of the first machine ⋮ The job shop scheduling problem: Conventional and new solution techniques ⋮ Scheduling no-wait robotic cells with two and three machines ⋮ A heuristic for scheduling two-machine no-wait flow shops with anticipatory setups ⋮ No-idle, no-wait: when shop scheduling meets dominoes, Eulerian paths and Hamiltonian paths ⋮ New directions in scheduling theory ⋮ A review of TSP based approaches for flowshop scheduling ⋮ SCHEDULING TWO-MACHINE FLOW SHOPS WITH EXACT DELAYS ⋮ Small and large TSP: Two polynomially solvable cases of the traveling salesman problem ⋮ The complexity of scheduling jobs in repetitive manufacturing systems ⋮ Nonpreemptive flowshop scheduling with machine dominance ⋮ Mathematical programming formulations for machine scheduling: A survey

This page was built for publication: The Three-Machine No-Wait Flow Shop is NP-Complete