A Note on Permutation Flow Shop Problem

In this paper we present two approximation algorithms for the permutation flow shop problem with makespan objective. The first algorithm has an absolute performance guarantee, the second one is an O(square root of m log m)-approximation algorithm. The last result is almost best possible approximatio...

Full description

Saved in:
Bibliographic Details
Published in:Annals of operations research 2004-07, Vol.129 (1-4), p.247-252
Main Author: Sviridenko, M.I.
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Codes
Job shops
Operations research
Random variables
Schedules
Studies
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper we present two approximation algorithms for the permutation flow shop problem with makespan objective. The first algorithm has an absolute performance guarantee, the second one is an O(square root of m log m)-approximation algorithm. The last result is almost best possible approximation algorithm which can be obtained using the trivial lower bound (maximum of the maximum machine load and the maximum job length)(Potts, Shmoys, and Williamson, 1991). [PUBLICATION ABSTRACT]
ISSN:0254-5330
1572-9338
DOI:10.1023/B:ANOR.0000030691.65576.28