This paper aims to illustrate a flow shop scheduling problem in which the processing time of each operation of job j is equal to pj. This class of the flow shop problem is known as the proportionate flow shop problem. A proportionate flexible flow shop problem is generalization of the proportionate flow shop problem with multiple identical machines at any stage. The general WSPT rule minimizes the total weighted completion time in the case of a single machine. Unfortunately, this result cannot be generalized to parallel machines. We propose a decomposition approach applied to a Restricted Master Problem (RMP) with a set covering formulation in which the linear programming relaxation is solved efficiently by column generation. If the linear programming relaxation forms to be integral, an optimal solution for the problem is obtained. Otherwise, we apply a branch and bound algorithm which is based on the completion time of jobs appearing in a fraction solution, through some computational results, the effectiveness and the capability of solving large scale problems. Finally, the proposed approach is proven to be able to effectively minimize the total weighted completion time for the proportionate flexible flow shop problem by some analyses.
|頁（從 - 到）||417-422|
|期刊||Proceedings of the IASTED International Conference on Modelling, Simulation, and Optimization|
|出版狀態||Published - 2004 十二月 27|
|事件||Proceedings of the Fourth IASTED International Conference on Modelling, Simulation, and Optimization - Kauai, HI, United States|
持續時間: 2004 八月 17 → 2004 八月 19
All Science Journal Classification (ASJC) codes