| Article ID: | iaor20071171 |
| Country: | China |
| Volume: | 20A |
| Issue: | 4 |
| Start Page Number: | 417 |
| End Page Number: | 423 |
| Publication Date: | Dec 2005 |
| Journal: | Applied Mathematics (A Journal of Chinese Universities) |
| Authors: | Lu Xiwen, Cheng Gang |
| Keywords: | flowshop |
In this paper, the computational complexity of the three-stage flow-shop with some batch machines to minimize the makespan is studied. Both the situation when batch machines have finite capacity and the situation when batch machines have infinite capacity are considered. When the second machine is a batch machine and the other two are discrete machines, NP-hardness of this problem is solved. So far, the computational complexity of the makespan of the three-stage flow-shop with some batch machines in all situations is completely solved.