Approximation Algorithms on Multiple Two-Stage Flowshops

被引：5

作者：

Wu, Guangwei ^{[1
,2
]}

Chen, Jianer ^{[3
,4
]}

机构：

[1] Cent S Univ, Sch Informat Sci & Engn, Changsha, Hunan, Peoples R China

[2] Cent South Univ Forestry & Technol, Coll Comp & Informat Engn, Changsha, Hunan, Peoples R China

[3] Guangzhou Univ, Sch Comp Sci & Educ Software, Guangzhou, Guangdong, Peoples R China

[4] Texas A&M Univ, Dept Comp Sci & Engn, College Stn, TX USA

来源：

COMPUTING AND COMBINATORICS (COCOON 2018) | 2018年 / 10976卷

基金：

中国国家自然科学基金;

关键词：

Scheduling; Flowshops; Approximation algorithm; MAKESPAN; BOUNDS;

D O I：

10.1007/978-3-319-94776-1_59

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

This paper considers the problem of scheduling multiple two-stage flowshops that minimizes the makespan, where the number of flowshops is part of the input. We study the relationship between the problem and the classical MAKESPAN problem. We prove that if there exists an a-approximation algorithm for the MAKESPAN problem, then for the multiple two-stage flowshop scheduling problem, we can construct a 2 alpha-approximation algorithm for the general case, and (alpha+1/2)-approximation algorithms for two restricted cases. As a result, we get a (2+epsilon)-approximation algorithm for the general case and a (1.5 + epsilon)-approximation algorithm for the two restricted cases, which significantly improve the previous approximation ratios 2.6 and 11/6, respectively.

引用

页码：713 / 725

页数：13

共 23 条

[11] BOUNDS ON MULTIPROCESSING TIMING ANOMALIES
GRAHAM, RL
[J]. SIAM JOURNAL ON APPLIED MATHEMATICS, 1969, 17 (02) : 416 - &
[12] BOUNDS FOR CERTAIN MULTIPROCESSING ANOMALIES
GRAHAM, RL
[J]. BELL SYSTEM TECHNICAL JOURNAL, 1966, 45 (09): : 1563 - +
[13] The Cost of a Cloud: Research Problems in Data Center Networks
Greenberg, Albert
Hamilton, James
Maltz, David A.
Patel, Parveen
[J]. ACM SIGCOMM COMPUTER COMMUNICATION REVIEW, 2009, 39 (01) : 68 - 73
[14] A scheduling problem in glass manufacturing
He, DW
Kusiak, A
Artiba, A
[J]. IIE TRANSACTIONS, 1996, 28 (02) : 129 - 139
[15] USING DUAL APPROXIMATION ALGORITHMS FOR SCHEDULING PROBLEMS - THEORETICAL AND PRACTICAL RESULTS
HOCHBAUM, DS
SHMOYS, DB
[J]. JOURNAL OF THE ACM, 1987, 34 (01) : 144 - 162
[16] Johnson S. M., 1954, NAVAL RES LOGISTICS, V1, P61, DOI [10.1002/nav.3800010110, DOI 10.1002/NAV.3800010110]
[17] Kovalyov MY, 1985, Vesti Academii navuk Belaruskai SSR Ser Phiz -Mat Navuk, V3, P119
[18] Pinedo MichaelL., 2016, SCHEDULING THEORY AL, Vfifth, P1, DOI DOI 10.1007/978-3-319-26580-3
[19] ALGORITHMS FOR SCHEDULING INDEPENDENT TASKS
SAHNI, SK
[J]. JOURNAL OF THE ACM, 1976, 23 (01) : 116 - 127
[20] The use of flowlines to simplify routing complexity in two-stage flowshops
Vairaktarakis, G
Elhafsi, M
[J]. IIE TRANSACTIONS, 2000, 32 (08) : 687 - 699

← 1 2 3 →