Worst-case analysis of an approximation algorithm for flow-shop scheduling

A worst-case analysis of an algorithm proposed by Campbell et al. for the m-machine permutation flow-shop problem is presented. The tight worst-case performance ratio [ m/2] is found.

Saved in:
Bibliographic Details
Published in:Operations research letters 1989, Vol.8 (3), p.171-177
Main Authors: Nowicki, Eugeniusz, Smutnicki, Czesław
Format: Article
Language:English
Subjects:
Applied sciences
Exact sciences and technology
heuristics
Operational research and scientific management
Operational research. Management science
scheduling
Scheduling, sequencing
worst-case analysis
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A worst-case analysis of an algorithm proposed by Campbell et al. for the m-machine permutation flow-shop problem is presented. The tight worst-case performance ratio [ m/2] is found.
ISSN:0167-6377
1872-7468
DOI:10.1016/0167-6377(89)90045-X