Solving proportionate flexible flow shop scheduling problems: A column generation approach

This paper aims to illustrate a flow shop scheduling problem in which the processing time of each operation of job j is equal to p_j. 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.