A new heuristic for open shop total completion time problem

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|∑CjOm|n=km|∑Cj, where k   is positive integer. And then, the heuristic is extended to solve the general problem Om‖∑CjOm‖∑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.