Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard
From MaRDI portal
Publication:1266667
DOI10.1016/S0377-2217(96)90070-3zbMath0908.90164OpenAlexW2153144242MaRDI QIDQ1266667
Hoogeveen, J. A., Bart Veltman, Jan Karel Lenstra
Publication date: 7 October 1998
Published in: European Journal of Operational Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0377-2217(96)90070-3
Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35)
Related Items
Optimizing resource speed for two-stage real-time tasks, Total completion time minimization in a computer system with a server and two parallel processors, A genetic algorithm for an industrial multiprocessor flow shop scheduling problem with recircu\-lation, Review and classification of hybrid flow shop scheduling problems from a production system and a solutions procedure perspective, An approximation scheme for minimizing the makespan of the parallel identical multi-stage flow-shops, Complexity and approximation of open shop scheduling to minimize the makespan: a review of models and approaches, An immune algorithm approach to hybrid flow shops scheduling with sequence-dependent setup times, Two-stage, single-lot, lot streaming problem for a \(1+2\) hybrid flow shop, Taking advantage of a diverse set of efficient production schedules: a two-step approach for scheduling with side concerns, A discrete inter-species cuckoo search for flowshop scheduling problems, Optimal scheduling of a two-stage hybrid flow shop, Flowshop scheduling with interstage job transportation, A fully polynomial time approximation scheme for scheduling on parallel identical two-stage openshops, Approximation algorithms for the parallel flow shop problem, Batch scheduling in a two-stage flexible flow shop problem, A hybrid heuristic approach to master surgery scheduling with downstream resource constraints and dividable operating room blocks, Two-stage proportionate flexible flow shop to minimize the makespan, Unnamed Item, Two-stage open-shop scheduling with a two-machine flow shop as a stage: approximation algorithms and empirical experiments, A PTAS for the Multiple Parallel Identical Multi-stage Flow-Shops to Minimize the Makespan, A two-stage hybrid flowshop scheduling problem with a function constraint and unrelated alternative machines, A PTAS for a particular case of the two-machine flow shop with limited machine availability, An FPTAS for the parallel two-stage flowshop problem, Minimizing makespan in a two-stage hybrid flow shop scheduling problem with open shop in one stage, Bounding strategies for the hybrid flow shop scheduling problem, A review of exact solution methods for the non-preemptive multiprocessor flowshop problem, The hybrid flow shop scheduling problem, Scheduling two-stage hybrid flow shop with availability constraints, Preemptive hybrid flowshop scheduling problem of interval orders, An approximation algorithm for proportionate scheduling in the two-stage hybrid flow shop, Minimizing makespan in two-stage hybrid cross docking scheduling problem, Heuristics for a two-stage hybrid flowshop scheduling problem with ready times and a product-mix ratio constraint, Mixed integer linear programming models for flow shop scheduling with a demand plan of job types, A bottleneck-based heuristic for minimizing makespan in a flexible flow line with unrelated parallel machines, A polynomial time approximation scheme for the two-stage multiprocessor flow shop problem, A hybrid two-stage flowshop with part family, batch production, major and minor set-ups, A polynomial-time approximation scheme for an arbitrary number of parallel two-stage flow-shops, Branch and bound crossed with GA to solve hybrid flowshops, Flexible flow shop scheduling with uniform parallel machines, An improved particle swarm optimization algorithm to solve hybrid flowshop scheduling problems with the effect of human factors -- a case study, Local search algorithms for the multiprocessor flow shop scheduling problem, Geometrical heuristics for multiprocessor flowshop scheduling with uniform machines at each stage, Complexity and algorithms for two-stage flexible flowshop scheduling with availability constraints, A heuristic for scheduling in a two-stage hybrid flowshop with renewable resources shared among the stages
Cites Work
- Scheduling algorithms for flexible flowshops: Worst and average case performance
- Branch and bound algorithm for the flow shop with multiple processors
- On pedigree polytopes and Hamiltonian cycles
- Scheduling with Deadlines and Loss Functions
- Optimal two- and three-stage production schedules with setup times included
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
