Three-stage flow-shop scheduling with assembly operations to minimize the weighted sum of product completion times

A modified flow-shop scheduling problem for a production system, characterized by parts machining followed by their subsequent assembly (joining) operation, is studied. Several products of different kinds are ordered. Each part for the products is processed on machine M1 (the first stage) and then processed on machine M2 (the second stage). Each product is processed (e.g., joined) with the parts by one assembly operation on assembly stage MA (the third stage). The objective function to be minimized is the weighted sum of product completion times. The decision variables are the sequence of products to be assembled and the sequence of parts to be processed. In this paper, we assume that if product h is assembled before product h′, then, on each machine, processing of any part for product h′ is done after processing of all parts for product h is completed. We call this assumption “Assumption B(2)” and call this problem “SPconstrained”. An efficient solution procedure using a branch and bound method is developed based on this assumption, where Johnson's algorithm is used as a part of the solution procedure. Computational experiments are provided to evaluate the performance of the solution procedure. It has been found that the proposed solution procedure is effective to obtain an optimal or ε-optimal solution for larger-scaled problems. We further compare the optimal value for SPconstrained with the optimal value for another problem SPunconstrained defined without Assumption B(2); the optimal solution for SPunconstrained being significantly more difficult to obtain. We offer three propositions to analyze some special cases in which the difference between the optimal value of SPconstrained and the optimal value of SPunconstrained is zero. For general cases, we make some computational experiments to evaluate the difference between the optimal value of SPconstrained and the optimal value of SPunconstrained. It has been found that the difference is very small.