期刊论文、会议论文

Wu, Guangwei

英文

Lecture Notes in Computer Science

0302-9743

2018

10976

713-725

24th International Computing and Combinatorics Conference (COCOON)

Lecture Notes in Computer Science

JUL 02-04, 2018

Qing Dao, PEOPLES R CHINA

[Wu, Guangwei] Cent S Univ, Sch Informat Sci & Engn, Changsha, Hunan, Peoples R China.^[Wu, Guangwei] Cent South Univ Forestry & Technol, Coll Comp & Informat Engn, Changsha, Hunan, Peoples R China.^[Chen, Jianer] Guangzhou Univ, Sch Comp Sci & Educ Software, Guangzhou, Guangdong, Peoples R China.^[Chen, Jianer] Texas A&M Univ, Dept Comp Sci & Engn, College Stn, TX USA.

Wang, L Zhu, D

GEWERBESTRASSE 11, CHAM, CH-6330, SWITZERLAND

SPRINGER INTERNATIONAL PUBLISHING AG

978-3-319-94776-1; 978-3-319-94775-4

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

National Natural Science Foundation of ChinaNational Natural Science Foundation of China (NSFC) [61420106009, 61672536, 61472449]; Scientific Research Fund of Hunan Provincial Education DepartmentHunan Provincial Education Department [16C1660]

本校为通讯机构

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 \(\alpha \)-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 )\)-approximat...