Some no-wait shops scheduling problems: Complexity aspect

DOI10.1016/0377-2217(86)90036-6zbMath0597.90045OpenAlexW1967348328MaRDI QIDQ1079487

Chelliah Skriskandarajah, Pierre Ladet

Publication date: 1986

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0377-2217(86)90036-6

zbMATH Keywords

computational complexitypolynomial time algorithmNP-hardNP-complete3-machine flowshopsno-wait shops schedulingoptimal finish time schedules

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35)

Related Items

Minimizing makespan in hybrid flowshops, A survey of job shop scheduling problem: the types and models, An efficient algorithm for a job shop problem, The proportionate two-machine no-wait job shop scheduling problem, Is a unit-job shop not easier than identical parallel machines?, Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity, Two-stage no-wait hybrid flowshop scheduling with inter-stage flexibility, A new heuristic for minimal makespan in flow shops with multiple processors and no intermediate storage., On Eulerian extensions and their application to no-wait flowshop scheduling, A pseudo-polynomial algorithm for a two-machine no-wait job-shop scheduling problem, An introduction of dominant genes in genetic algorithm for FMS, Minimum deviation algorithm for two-stage no-wait flowshops with parallel machines, Scheduling algorithms for flexible flowshops: Worst and average case performance, Minimizing total completion time in two-machine flow shops with exact delays, Complete local search with limited memory algorithm for no-wait job shops to minimize makespan, Combinatorial optimization models for production scheduling in automated manufacturing systems, Modified drum–buffer–rope scheduling mechanism for a non-identical parallel machine flow shop with processing-time variation, A two-machine no-wait flow shop problem with two competing agents, Two-machine shop scheduling with zero and unit processing times, Scheduling multipurpose batch process industries with no-wait restrictions by simulated annealing, Minimizing Total Completion Time in Two-Machine Flow Shops with Exact Delays, The complexity of scheduling jobs in repetitive manufacturing systems, Performance of scheduling algorithms for no-wait flowshops with parallel machines, On scheduling cycle shops: Classification, complexity and approximation, The hot strip mill production scheduling problem: A tabu search approach

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Performance of scheduling algorithms for no-wait flowshops with parallel machines
• Some new results in flow shop scheduling
• The Three-Machine No-Wait Flow Shop is NP-Complete
• Complexity of Scheduling Shops with No Wait in Process
• Flowshop scheduling with limited temporary storage
• Unit Execution Time Shop Problems
• On general routing problems
• The Complexity of Flowshop and Jobshop Scheduling
• Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem
• On the Flow-Shop Sequencing Problem with No Wait in Process^†
• Solution of the Flowshop-Scheduling Problem with No Intermediate Queues
• A Scheduling Problem^*