Abstract:

This paper considers a two-stage flowshop scheduling problems with m identical parallel machines at stage one and a batch processor at stage two, and minimizes the total completion time. We get optimal solution in time of the order O(n3) when all jobs have the same processing time at stage one and stage two respectively. In the case that all jobs have same processing time at stage one but have arbitrary processing time at stage two, we analyze the worst-case of an approximation algorithm and show that the problem is strongly NP-hard in this case.