Flowshop scheduling problem with parallel semi-lines and final synchronization operation

Irce F.G. Guimarães (1) , Yassine Ouazene (2) , Mauricio C de Souza (1) , Farouk Yalaoui (2)

1 UFMG - Universidade Federal de Minas Gerais = Federal University of Minas Gerais [Belo Horizonte, Brazil]
2 LOSI - Laboratoire d'Optimisation des Systèmes Industriels

This paper deals with a particular variant of the flowshop scheduling problem motivated by a real case configuration issued from an electro-electronic material industry. The shop floor environment is composed of two parallel semi-lines and a final synchronization operation. The jobs must follow the same technological order through the machines on each parallel semi-line. However, the operations on each semi-line are independent. The final synchronization operation, operated by a dedicated machine, can only start when the job is finished on both semi-lines. The objective is to determine a schedule that minimizes the makespan for a given set of jobs. Since this problem class is NP-hard in the strong sense, constructive heuristic procedures and metaheuristics methods are introduced to achieve optimal or near-optimal solutions. The performances of the proposed GRASP and the Simulated Annealing algorithms are evaluated and compared with the adaptation of two well-known heuristics. Computational experiments show that the proposed metaheuristics provide very good results in low computational times.

Domaines: Recherche opérationnelle [math.OC]

Irce F.G. Guimarães, Yassine Ouazene, Mauricio C de Souza, Farouk Yalaoui. Flowshop scheduling problem with parallel semi-lines and final synchronization operation. Computers and Operations Research, 2019, 108, pp.121-133. ⟨10.1016/j.cor.2019.04.011⟩. ⟨hal-02311165⟩