| 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.