Two-machine flowshop scheduling problem with coupled-operations |
| |
Authors: | Meziani Nadjat Oulamara Ammar Boudhar Mourad |
| |
Institution: | 1.Abderrahmane Mira University, Bejaia, Algeria ;2.LORIA Laboratory, UMR CNRS 75003, University of Lorraine, Campus Scientifique, 615 Rue du Jardin-Botanique, 54506, Vandoeuvre-lès-Nancy, France ;3.RECITS Laboratory, Faculty of Mathematics, University of Sciences and Technology Houari Boumediene (USTHB), BP 32, El-Alia, 16111, Bab-Ezzouar, Algiers, Algeria ; |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|