Scheduling in semi parallel flow shop with a final synchronizing operation

Abstract

This study deals with a variant of the flow shop problem motivated by a practical situation. In this environment, there is an assembly line composed by two parallel semi- lines and independent operation. The first semi-line has a number q1 of machines and the second has a number q2 of machines. At the end of the two semi-lines there is a machine in charge of the union of the semi-products from the two semi-lines, each semi-line is devoted to different tasks, since each job requires operations in each machine of the semi-lines with different processing time. The tasks of one semi-line do not depend on the completion of the task of the other semi-line, so that a job is processed in parallel in each semi-line. The sequence of jobs in each parallel semi-line must be the same, although the first task of a job in each semi-line does not have to start at the same time. The final synchronizing operation can only start when the operations within both semi-lines have been finished. The solution to this problem is to determine one possible sequence of jobs that optimizes a given performance measure. In this sense, the objective of this study is to model the flow shop problem in the proposed production environment and to solve it with a mathematical model, heuristic and metaheuristic, considering the makespan as performance measure. In a first approach, a mixed integer linear programming model was defined. Due to the complexity of the problem, it was also solved by Johnsons rule, the NEH heuristics and by the Iterated Local Search,Simulated Annealing and GRASP metaheuristics. Finally, an extensive computational experiment was performed and a comparison of the proposed methods was made. The hybrid method that used the NEH algorithm with GRASP metaheuristic presented better quality than the other methods.