An improved heuristic for two-machine flow shop scheduling with an availability constraint and nonresumable jobs

被引：0

作者：

Hatem Hadda

Najoua Dridi

Sonia Hajri-Gabouj

机构：

[1] Unité de Recherche URAII,

[2] INSAT-Tunis,undefined

[3] Unité de Recherche OASIS,undefined

[4] ENIT,undefined

来源：

4OR | 2010年 / 8卷

关键词：

Flow shop; Scheduling; Availability constraint; Heuristics; Worst case analysis; 68W40 Analysis of algorithms;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

In this paper, we deal with the two-machine flow shop scheduling problem having an unavailability interval on the first machine, and nonresumable jobs. We first present an enhancement procedure that, once applied to any arbitrary solution, produces a schedule that is at most equal 2 times the optimal makespan. We then develop an improved heuristic, with a relative worst-case error of 3/2.

引用

页码：87 / 99

页数：12

共 8 条

[1]

Breit J(2004)An improved approximation algorithm for two-machine flow shop scheduling with an availability constraint Inf Process Lett 90 273-278

[2]

Cheng TCE(2000)An improved heuristic for two-machine flowshop scheduling with an availability constraint Oper Res Lett 26 223-229

[3]

Wang G(2006)Scheduling two-stage hybrid flow shop with availability constraints Comput Oper Res 33 1399-1419

[4]

Hamid A(1954)Optimal two- and three-stage production schedules with setup times included Res Log Q 1 61-68

[5]

Artiba A(1997)Minimizing the makespan in the two-machine flow shop scheduling problem with an availability constraint Oper Res Lett 20 129-139

[6]

Johnson SM(1999)Two-machine flowshop scheduling with availability constraints Eur J Oper Res 114 420-429

[7]

Lee CY(undefined)undefined undefined undefined undefined-undefined

[8]

Lee CY(undefined)undefined undefined undefined undefined-undefined

← 1 →