Two-machine flowshop scheduling problem with coupled-operations

Nadjat Meziani (1, 2) , Ammar Oulamara (3) , Mourad Boudhar (2)

1 UB - Université Abderrahmane Mira [Université de Béjaïa] = University Abderrahmane Mira [University of Béjaïa]
2 USTHB - Université des Sciences et de la Technologie Houari Boumediene = University of Sciences and Technology Houari Boumediene [Alger]
3 OPTIMIST - OPTImisation Methods for Integrated SysTems

This paper addresses a generalization of the coupled-operations scheduling problem in the context of a flow shop environment. We consider the two-machine scheduling problem with the objective of minimizing the makespan. Each job consists of a coupled-operation to be processed first on the first machine and a single operation to be then processed on the second machine. A coupled-operation contains two operations separated by an exact time delay. The single operation can start on the second machine only when the coupled-operation on the first machine is completed. We prove the NP-completeness of two restricted versions of the general problem, whereas we also exhibit several other well solvable cases.

Mots clés: Polynomial time algorithms; Flowshop; Coupled-operations; Complexity

Domaines: Recherche opérationnelle [math.OC]

Nadjat Meziani, Ammar Oulamara, Mourad Boudhar. Two-machine flowshop scheduling problem with coupled-operations. Annals of Operations Research, 2019, 275 (2), pp.511-530. ⟨10.1007/s10479-018-2967-z⟩. ⟨hal-02981096⟩