Two-machine flowshop scheduling problem with coupled-operations

被引：0

作者：

Nadjat Meziani

Ammar Oulamara

Mourad Boudhar

机构：

[1] Abderrahmane Mira University,LORIA Laboratory, UMR CNRS 75003

[2] University of Lorraine,RECITS Laboratory, Faculty of Mathematics

[3] University of Sciences and Technology Houari Boumediene (USTHB),undefined

来源：

Annals of Operations Research | 2019年 / 275卷

关键词：

Flowshop; Coupled-operations; Complexity; Polynomial time algorithms;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

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.

引用

页码：511 / 530

页数：19

共 40 条

[1]

Ageev AA(2007)Approximation algorithms for UET scheduling problems with exact delays Operations Research Letters 35 533-540

[2]

Baburin AE(2004)An exact algorithm for scheduling identical coupled tasks Mathematical Methods of Operational Research 59 193-203

[3]

Ahr D(2010)Scheduling of coupled tasks with unit processing times Journal of Scheduling 13 453-461

[4]

Békési J(2012)New algorithms for coupled tasks scheduling—A survey RAIRO - Operations Research 46 335-353

[5]

Galambos G(2009)Scheduling of coupled tasks and one-machine no-wait robotic cells Computers and Operational Research 36 301-307

[6]

Oswald M(1996)Shop problems with two machines and time lags Operations Research 44 777-787

[7]

Reinelt G(2006)Permutation flowshop scheduling problem with maximal and minimal time lags Computers and Operations Research 33 1540-1556

[8]

Blazewicz J(2008)Permutation flow shop scheduling problems with time lags to minimize the weighted sum of machine completion times International Journal of Production Economics 112 168-176

[9]

Ecker K(1954)Optimal two and three stage production schedules with setup time included Naval Research Logistics Quarterly 1 61-67

[10]

Kis T(1958)Sequencing Management Science 5 293-298

← 1 2 3 4 →