Scheduling with rejection and non-identical job arrivals

CSpace

	Scheduling with rejection and non-identical job arrivals
	Cao, Zhigang 1,2; Zhang, Yuzhong 2
	2007-12-01
发表期刊	JOURNAL OF SYSTEMS SCIENCE & COMPLEXITY
ISSN	1009-6124
卷号	20 期号:4 页码:529-535
摘要	In this paper, we address the scheduling problem with rejection and non-identical job arrivals, in which we may choose not to process certain jobs and each rejected job incurs a penalty. Our goal is to minimize the sum of the total penalties of the rejected jobs and the maximum completion time of the processed ones. For the off-line variant, we prove its NP-hardness and present a PTAS, and for the on-line special case with two job arrivals, we design a best possible algorithm with competitive ratio (root 5+1/2).
关键词	non-identical job arrival on-line rejection scheduling
语种	英语
WOS研究方向	Mathematics
WOS类目	Mathematics, Interdisciplinary Applications
WOS记录号	WOS:000255240600007
出版者	SPRINGER
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/5078
专题	中国科学院数学与系统科学研究院
通讯作者	Cao, Zhigang
作者单位	1.Chinese Acad Sci, Inst Syst Sci, Acad Math & Syst Sci, Beijing 100080, Peoples R China 2.Qufu Normal Univ, Sch Operat Res & Management Sci, Rizhao 276826, Shandong, Peoples R China
推荐引用方式 GB/T 7714	Cao, Zhigang,Zhang, Yuzhong. Scheduling with rejection and non-identical job arrivals[J]. JOURNAL OF SYSTEMS SCIENCE & COMPLEXITY,2007,20(4):529-535.
APA	Cao, Zhigang,&Zhang, Yuzhong.(2007).Scheduling with rejection and non-identical job arrivals.JOURNAL OF SYSTEMS SCIENCE & COMPLEXITY,20(4),529-535.
MLA	Cao, Zhigang,et al."Scheduling with rejection and non-identical job arrivals".JOURNAL OF SYSTEMS SCIENCE & COMPLEXITY 20.4(2007):529-535.