A new heuristic for three-machine flow shop scheduling

A new heuristic for three-machine flow shop scheduling

0.00 Avg rating0 Votes
Article ID: iaor20003457
Country: United States
Volume: 44
Issue: 6
Start Page Number: 891
End Page Number: 898
Publication Date: Nov 1996
Journal: Operations Research
Authors: , , ,
Keywords: heuristics
Abstract:

This paper considers the problem of sequencing n jobs in a three-machine flow shop with the objective of minimizing the makespan, which is the completion time of the last job. An O(n log n) time heuristic that is based on Johnson's algorithm is presented. It is shown to generate a schedule with length at most 5/3 times that of an optimal schedule, thereby reducing the previous best available worst-case performance ratio of 2. An application to the general flow shop is also discussed.

Reviews

Required fields are marked *. Your email address will not be published.