Worst-case analysis of heuristics for open shops with parallel machines

DOI10.1016/0377-2217(93)90249-MzbMath0792.90036OpenAlexW2061722987MaRDI QIDQ1310023

Bo Chen, Vitaly A. Strusevich

Publication date: 20 December 1993

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

Full work available at URL: https://doi.org/10.1016/0377-2217(93)90249-m

zbMATH Keywords

makespanworst-case performanceheuristic algorithmsidentical parallel machinesmulti-stage open shop scheduling

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items (9)

Complexity and approximation of open shop scheduling to minimize the makespan: a review of models and approaches ⋮ Flexible open shop scheduling problem to minimize makespan ⋮ A new three-machine shop scheduling: complexity and approximation algorithm ⋮ A fully polynomial time approximation scheme for scheduling on parallel identical two-stage openshops ⋮ A note on LPT scheduling ⋮ A genetic algorithm for the proportionate multiprocessor open shop ⋮ Polynomial time algorithms for two special classes of the proportionate multiprocessor open shop ⋮ Approximation algorithms for the multiprocessor open shop scheduling problem ⋮ Two-stage open shop scheduling with a bottleneck machine

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Scheduling algorithms for flexible flowshops: Worst and average case performance
• Branch and bound algorithm for the flow shop with multiple processors
• No-wait shop scheduling: Computational complexity and approximate algorithms
• Scheduling open shops with parallel machines
• Tighter Bounds for the Multifit Processor Scheduling Algorithm
• Evaluation of a MULTIFIT-based scheduling algorithm
• Two-Stage, Hybrid Flowshop Scheduling Problem
• Open Shop Scheduling to Minimize Finish Time
• Approximation Algorithms for Three-Machine Open Shop Scheduling
• Short Shop Schedules
• Bounds for Certain Multiprocessing Anomalies
• Bounds on Multiprocessing Timing Anomalies
• A Survey of Machine Scheduling Problems with Blocking and No-Wait in Process

This page was built for publication: Worst-case analysis of heuristics for open shops with parallel machines