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: | Tang Hui-Chin |
Keywords: | flowshop |
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.