A worst-case analysis of the three-machine flow shop scheduling

A worst-case analysis of the three-machine flow shop scheduling

0.00 Avg rating0 Votes
Article ID: iaor20031869
Country: India
Volume: 23
Issue: 2
Start Page Number: 229
End Page Number: 240
Publication Date: May 2002
Journal: Journal of Information & Optimization Sciences
Authors:
Keywords: flowshop
Abstract:

Chen, Glass, Potts, and Strusevich presented a heuristic algorithm, which has a worst-case performance ratio of 5/3 for the three-machine flow shop scheduling problem. They provided a worst-case instance of 3FSS with seven jobs to show the tightness of this bound. In this paper, we propose an alternative method to show that the bound of 5/3 is tight. Moreover, for the special case, this bound can be reduced to 1 + ρ, for 1/4 < ρ ≤ 1, which is better than 5/3.

Reviews

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