No-Wait Flowshop Scheduling Is as Hard as Asymmetric Traveling Salesman Problem

DOI10.1287/moor.2015.0725zbMath1334.90054arXiv1302.2551OpenAlexW2569974777MaRDI QIDQ2800373

Marcin Mucha, M. I. Sviridenko

Publication date: 15 April 2016

Published in: Mathematics of Operations Research, Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1302.2551

zbMATH Keywords

approximationtraveling salesman problemno-wait scheduling

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (1)

A survey of scheduling problems with no-wait in process

Cites Work

• Unnamed Item
• Unnamed Item
• The no-wait flow-shop paradox
• New Inapproximability Bounds for TSP
• Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
• The Three-Machine No-Wait Flow Shop is NP-Complete
• Flowshop scheduling with limited temporary storage
• On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
• 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
• Solution of the Flowshop-Scheduling Problem with No Intermediate Queues
• A Survey of Machine Scheduling Problems with Blocking and No-Wait in Process

This page was built for publication: No-Wait Flowshop Scheduling Is as Hard as Asymmetric Traveling Salesman Problem