Some no-wait shops scheduling problems: Complexity aspect

DOI10.1016/0377-2217(86)90036-6MaRDI QIDQ1079487zbMATH OpenOpenAlexFDO

Authors Chelliah Sriskandarajah, 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 complexityNP-completeNP-hardpolynomial time algorithm3-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)

Recommendations

• No-wait shop scheduling: Computational complexity and approximate algorithms
• The Three-Machine No-Wait Flow Shop is NP-Complete
• NP-hardness of compact scheduling in simplified open and flow shops.
• Two-machine flow shop scheduling problems with no-wait jobs
• A Note On The Complexity Of Openshop Scheduling Problems

Cites work

• scientific article; zbMATH DE number 3550182 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 3633982 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3438402 (Why is no real title available?)
• scientific article; zbMATH DE number 3410790 (Why is no real title available?)
• A Scheduling Problem^*
• Complexity of Scheduling Shops with No Wait in Process
• Flowshop scheduling with limited temporary storage
• On general routing problems
• On the Flow-Shop Sequencing Problem with No Wait in Process^†
• Performance of scheduling algorithms for no-wait flowshops with parallel machines
• Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem
• Solution of the Flowshop-Scheduling Problem with No Intermediate Queues
• Some new results in flow shop scheduling
• The Complexity of Flowshop and Jobshop Scheduling
• The Three-Machine No-Wait Flow Shop is NP-Complete
• Unit Execution Time Shop Problems

Cited in

(34)

• A survey of scheduling problems with no-wait in process
• The hot strip mill production scheduling problem: A tabu search approach
• The non-stop disjoint trajectories problem
• Modified drum–buffer–rope scheduling mechanism for a non-identical parallel machine flow shop with processing-time variation
• Performance of scheduling algorithms for no-wait flowshops with parallel machines
• No-wait shop scheduling: Computational complexity and approximate algorithms
• The Three-Machine No-Wait Flow Shop is NP-Complete
• An efficient algorithm for a job shop problem
• A new heuristic for minimal makespan in flow shops with multiple processors and no intermediate storage.
• A Note On The Complexity Of Openshop Scheduling Problems
• Is a unit-job shop not easier than identical parallel machines?
• scientific article; zbMATH DE number 5774288 (Why is no real title available?)
• Scheduling multipurpose batch process industries with no-wait restrictions by simulated annealing
• On The Complexity Of The Process Shop
• The complexity of scheduling jobs in repetitive manufacturing systems
• A survey of job shop scheduling problem: the types and models
• Complete local search with limited memory algorithm for no-wait job shops to minimize makespan
• The proportionate two-machine no-wait job shop scheduling problem
• No-idle, no-wait: when shop scheduling meets dominoes, Eulerian paths and Hamiltonian paths
• Minimizing Total Completion Time in Two-Machine Flow Shops with Exact Delays
• Scheduling algorithms for flexible flowshops: Worst and average case performance
• Minimizing total completion time in two-machine flow shops with exact delays
• A pseudo-polynomial algorithm for a two-machine no-wait job-shop scheduling problem
• Two-machine shop scheduling with zero and unit processing times
• Combinatorial optimization models for production scheduling in automated manufacturing systems
• Minimizing makespan in hybrid flowshops
• A two-machine no-wait flow shop problem with two competing agents
• An introduction of dominant genes in genetic algorithm for FMS
• 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
• Two-machine flow shop scheduling problems with no-wait jobs
• Minimum deviation algorithm for two-stage no-wait flowshops with parallel machines
• On scheduling cycle shops: Classification, complexity and approximation
• On Eulerian extensions and their application to no-wait flowshop scheduling

This page was built for publication: Some no-wait shops scheduling problems: Complexity aspect

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1079487)