Production Scheduling for a Two-machine Flow Shop with a Batch Processing Machine

This paper deals with a scheduling problem for two–machine flow shop, in which the preceding machine is a batch processing machine that can process a number of jobs simultaneously. To minimize makespan of the system, we present a mixed integer linear programming formulation for the problem, and using this formulation, it is shown that an optimal solution for small problem can be obtained by a commercial optimization software. However, since the problem is NP–hard and the size of a real problem is very large, we propose a number of heuristic algorithms including genetic algorithm to solve practical big–sized problems in a reasonable computational time. To verify performances of the algorithms, we compare them with lower bound for the problem. From the results of these computational experiments, some of the heuristic algorithms show very good performances for the problem.