An asymptotic PTAS for batch scheduling with nonidentical job sizes to minimize makespan

doi:10.1007/s10878-007-9128-7

CSpace

	An asymptotic PTAS for batch scheduling with nonidentical job sizes to minimize makespan
	Zhang, Yuzhong 2; Cao, Zhigang 1
	2008-08-01
发表期刊	JOURNAL OF COMBINATORIAL OPTIMIZATION
ISSN	1382-6905
卷号	16 期号:2 页码:119-126
摘要	Motivated by the existence of an APTAS (Asymptotic PTAS) for bin packing problem, we consider the batch scheduling problem with nonidentical job sizes to minimize makespan. For the proportional special version, i.e., there exists a fixed number alpha such that p(j) =alpha s(j) for every 1 <= j <= n, we first present a lower bound of 3/2 for the approximation ratio and then design an APTAS.
关键词	scheduling batching non-identical job sizes makespan asymptotic PTAS
DOI	10.1007/s10878-007-9128-7
语种	英语
WOS研究方向	Computer Science ; Mathematics
WOS类目	Computer Science, Interdisciplinary Applications ; Mathematics, Applied
WOS记录号	WOS:000256777800004
出版者	SPRINGER
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/6776
专题	中国科学院数学与系统科学研究院
通讯作者	Cao, Zhigang
作者单位	1.Chinese Acad Sci, Acad Math & Syst Sci, Inst Syst Sci, Beijing 100080, Peoples R China 2.Qufu Normal Univ, Sch Operat Res & Management Sci, Rizhao, Shandong, Peoples R China
推荐引用方式 GB/T 7714	Zhang, Yuzhong,Cao, Zhigang. An asymptotic PTAS for batch scheduling with nonidentical job sizes to minimize makespan[J]. JOURNAL OF COMBINATORIAL OPTIMIZATION,2008,16(2):119-126.
APA	Zhang, Yuzhong,&Cao, Zhigang.(2008).An asymptotic PTAS for batch scheduling with nonidentical job sizes to minimize makespan.JOURNAL OF COMBINATORIAL OPTIMIZATION,16(2),119-126.
MLA	Zhang, Yuzhong,et al."An asymptotic PTAS for batch scheduling with nonidentical job sizes to minimize makespan".JOURNAL OF COMBINATORIAL OPTIMIZATION 16.2(2008):119-126.