| Article ID: | iaor20062080 |
| Country: | China |
| Volume: | 33 |
| Issue: | 4 |
| Start Page Number: | 121 |
| End Page Number: | 124 |
| Publication Date: | Apr 2005 |
| Journal: | Journal of Huazhong University of Science and Technology |
| Authors: | Shi Ling |
| Keywords: | heuristics |
The flowshop scheduling with a single server was considered, to determine a feasible schedule, which minimizes a given objective function. This problem is NP-hard in the strong sense. It was proposed that even if all setups were constant or all processing times were constant, these problems were still NP-hard in the strong sense, so there is not a polynomially optimal solution. For the two-machine case, a new improved heuristic algorithm was introduced to solve this problem and to guarantee a tight worst-case ratio of 3/2.