A note on worst-case analysis of approximation algorithms for a scheduling problem

Worst-case analyses of two approximation algorithms for the m-machine permutation flow-shop problem are presented. Worst-case performane ratios m / √2 + O(1/ m) for the former and m − 1 for the latter algorithm are found.

Saved in:
Bibliographic Details
Published in:European journal of operational research 1994-04, Vol.74 (1), p.128-134
Main Authors: Nowicki, Eugeniusz, Smutnicki, Czesław
Format: Article
Language:English
Subjects:
Algorithms
Analysis of algorithms
Applied sciences
Approximation
Combinatorial problems
Estimating techniques
Exact sciences and technology
Job shops
Mathematical models
Operational research and scientific management
Operational research. Management science
Operations research
Performance evaluation
Scheduling
Scheduling, sequencing
Studies
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:Worst-case analyses of two approximation algorithms for the m-machine permutation flow-shop problem are presented. Worst-case performane ratios m / √2 + O(1/ m) for the former and m − 1 for the latter algorithm are found.
ISSN:0377-2217
1872-6860
DOI:10.1016/0377-2217(94)90210-0