Heuristics for Online Scheduling on Identical Parallel Machines with Two GoS Levels

doi:10.1007/s11424-019-7427-6

CSpace > 应用数学研究所

	Heuristics for Online Scheduling on Identical Parallel Machines with Two GoS Levels
	Cai Shuang 1,2,3; Liu Ke2,3
	2019-08-01
发表期刊	JOURNAL OF SYSTEMS SCIENCE & COMPLEXITY
ISSN	1009-6124
卷号	32 期号:4 页码:1180-1193
摘要	This paper considers the online scheduling problem on m (m >= 3) parallel machines (the first k machines with grade 1 and the remaining m - k machines with grade 2) with two GoS levels and makespan as the objective function. The jobs arrive over time with grade 1 or 2 and an arrival job can be assigned to a machine only when the grade of the job is no less than the grade of the machine. Three cases are considered: (i) For k = 1, the authors present an online algorithm with competitive ratio of 9/5. (ii) For 1 < k < m - 1, an online algorithm with competitive ratio of 2.280 is proposed. (iii) For k = m - 1, an online algorithm is presented with competitive ratio of 2. All the three algorithms are based on greedy algorithm with a similar structure. At last, numerical instances are given and the average competitive ratios of the instances show good performance of the proposed algorithms.
关键词	Grade of Service (GoS) constraints heuristic algorithm online scheduling parallel machine scheduling
DOI	10.1007/s11424-019-7427-6
语种	英语
资助项目	National Natural Science Foundation of China[71390334] ; National Natural Science Foundation of China[11271356]
WOS研究方向	Mathematics
WOS类目	Mathematics, Interdisciplinary Applications
WOS记录号	WOS:000480484700012
出版者	SPRINGER HEIDELBERG
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/35488
专题	应用数学研究所
通讯作者	Cai Shuang
作者单位	1.Beijing Jingdong Zhenshi Informat Technol Co Ltd, Logist R&D Dept, Beijing 100176, Peoples R China 2.Chinese Acad Sci, Acad Math & Syst Sci, Beijing 100190, Peoples R China 3.Univ Chinese Acad Sci, Beijing 100190, Peoples R China
推荐引用方式 GB/T 7714	Cai Shuang,Liu Ke. Heuristics for Online Scheduling on Identical Parallel Machines with Two GoS Levels[J]. JOURNAL OF SYSTEMS SCIENCE & COMPLEXITY,2019,32(4):1180-1193.
APA	Cai Shuang,&Liu Ke.(2019).Heuristics for Online Scheduling on Identical Parallel Machines with Two GoS Levels.JOURNAL OF SYSTEMS SCIENCE & COMPLEXITY,32(4),1180-1193.
MLA	Cai Shuang,et al."Heuristics for Online Scheduling on Identical Parallel Machines with Two GoS Levels".JOURNAL OF SYSTEMS SCIENCE & COMPLEXITY 32.4(2019):1180-1193.