An improved heuristic for two-machine flowshop scheduling with an availability constraint

被引：63

作者：

Cheng, TEC ^{[1
]}

Wang, GQ

机构：

[1] Hong Kong Polytech Univ, Off Vice President Res & Postgrad Studies, Kowloon, Hong Kong, Peoples R China

[2] Jinan Univ, Dept Business Adm, Guangzhou, Peoples R China

[3] Hong Kong Polytech Univ, Dept Management, Kowloon, Hong Kong, Peoples R China

来源：

OPERATIONS RESEARCH LETTERS | 2000年 / 26卷 / 05期

关键词：

flowshop scheduling; heuristics; error bound;

D O I：

10.1016/S0167-6377(00)00033-X

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this paper we study the two-machine flowshop scheduling problem with an availability constraint on the first machine. We first show that the worst-case error bound 1/2 of the heuristic provided by Lee [4] is tight. We then develop an improved heuristic with a worst-case error bound of 1/3. (C) 2000 Elsevier Science B.V. All rights reserved.

引用

页码：223 / 229

页数：7

共 5 条

[1] Two-machine flowshop scheduling with consecutive availability constraints
Cheng, TCE
Wang, GQ
[J]. INFORMATION PROCESSING LETTERS, 1999, 71 (02) : 49 - 54
[2] Johnson Selmer Martin., 1954, NAV RES LOG, V1, P61, DOI [10.1002/nav.3800010110, DOI 10.1002/NAV.3800010110, 10.1002/(ISSN)1931-9193]
[3] KUBIAK W, 1997, 10 M EUR CHAPT COMB, V38
[4] Two-machine flowshop scheduling with availability constraints
Lee, CY
[J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1999, 114 (02) : 420 - 429
[5] Minimizing the makespan in the two-machine flowshop scheduling problem with an availability constraint
Lee, CY
[J]. OPERATIONS RESEARCH LETTERS, 1997, 20 (03) : 129 - 139

← 1 →