Semi-parallel flow shop with a final synchronization operation scheduling problem.

Abstract

This article discusses a variant of flow shop scheduling problem based on a real case issued from an electro-electronic material industry. The environment under study consists of an assembly line formed by two semi-lines and a final synchronization operation. Semi-lines have parallel operations and provide semi-products for the synchronization operation which completes the manufacturing activity by the assembly of semi-products. The aim of this study is to achieve the schedule of jobs in order to minimize the makespan. This article presents the achieved results by a mixed integer linear programming model, variants of the NEH heuristic and an adaptation of Johnson’s algorithm dedicated to the proposed special case. The proposed methods are tested among different instances inspired from Taillard (1993)’s benchmark. Based on the obtained results, we discuss the performance of the different methods.