A new heuristic for open shop total completion time problem |
| |
Authors: | Lixin Tang Danyu Bai |
| |
Institution: | Liaoning Key Laboratory of Manufacturing System and Logistics, The Logistics Institute, Northeastern University, Shenyang 110004, PR China |
| |
Abstract: | The m -machine open shop problem to minimize the sum of the completion times is investigated in our paper. First, a heuristic algorithm, Shortest Processing Time Block, is presented to deal with problem Om|n=km|∑Cj, where k is positive integer. And then, the heuristic is extended to solve the general problem Om‖∑Cj. It is proved that the heuristic is asymptotically optimal when the job number goes to infinity. At the end of this paper, numerical experimentation results show the effectiveness of the heuristic algorithm. |
| |
Keywords: | Open shop problem Total completion time Asymptotical analysis |
本文献已被 ScienceDirect 等数据库收录! |
|