A PTAS for parallel batch scheduling with rejection and dynamic job arrivals

doi:10.1016/j.tcs.2009.04.006

CSpace > 系统科学研究所

	A PTAS for parallel batch scheduling with rejection and dynamic job arrivals
	Cao, Zhigang; Yang, Xiaoguang
	2009-06-28
发表期刊	THEORETICAL COMPUTER SCIENCE
ISSN	0304-3975
卷号	410 期号:27-29 页码:2732-2745
摘要	In the parallel batch scheduling model, a group of jobs can be scheduled together as a batch while the processing time of this batch is the greatest processing time among its members; in the model of scheduling with rejection, any job can be rejected with a corresponding penalty cost added to the objective value. In this paper, we present a PTAS for the combined model of the above two scheduling models where jobs arrive dynamically. The objective is to minimize the sum of the makespan of the accepted jobs and the total penalty of the rejected ones. Our basic approaches are dynamic programming and roundings. (C) 2009 Elsevier B.V. All rights reserved.
关键词	Scheduling Parallel batch Dynamic job arrivals Rejection PTAS
DOI	10.1016/j.tcs.2009.04.006
语种	英语
资助项目	National Natural Science Foundation of China[70425004] ; National Natural Science Foundation of China[90818026]
WOS研究方向	Computer Science
WOS类目	Computer Science, Theory & Methods
WOS记录号	WOS:000267160800017
出版者	ELSEVIER SCIENCE BV
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/8050
专题	系统科学研究所
通讯作者	Cao, Zhigang
作者单位	Chinese Acad Sci, Key Lab Management Decis & Informat Syst, Acad Math & Syst Sci, Beijing 100190, Peoples R China
推荐引用方式 GB/T 7714	Cao, Zhigang,Yang, Xiaoguang. A PTAS for parallel batch scheduling with rejection and dynamic job arrivals[J]. THEORETICAL COMPUTER SCIENCE,2009,410(27-29):2732-2745.
APA	Cao, Zhigang,&Yang, Xiaoguang.(2009).A PTAS for parallel batch scheduling with rejection and dynamic job arrivals.THEORETICAL COMPUTER SCIENCE,410(27-29),2732-2745.
MLA	Cao, Zhigang,et al."A PTAS for parallel batch scheduling with rejection and dynamic job arrivals".THEORETICAL COMPUTER SCIENCE 410.27-29(2009):2732-2745.