Optimal Scheduling for Load Balance of Two-Machine Production Lines

A scheduling method for balancing work loads between a machine and the one succeeding it in a two-machine production line so as to maximize the overall production speed is proposed in this paper. The case where the production speeds are different from each other both for machines and for commodities is treated. The objective is to minimize the changeover loss under the constraints that 1) the due date must be met, 2) the queue length of commodity items must be shorter than the maximum space between the two machines, and 3) no idle time is acceptable for either machine. Both the lot size of each commodity for each production period and their production sequence is determined by the proposed method. The scheduling algorithm is a branch-and-bound procedure. In the conventional flow shop scheduling problem, the lot size of each commodity is given beforehand considering the inventory loss of the final products and the changeover loss of the production line. Only the flow sequence is determined there. Therefore, it can not perfectly balance the work loads between machines. Computational experience with the proposed method indicates that it is capable of solving problems involving 20 commodities over a planning horizon of 300 time periods. These are practical scheduling problems with a planning horizon of one week for a home appliance production line. These computation times are below one minute (using the HITAC M-180 operating at three million instructions per second (MIPS)).