NF-based algorithms for online bin packing with buffer and bounded item size

doi:10.1007/s10878-014-9771-8

CORC > 上海财经大学 > 上海财经大学

	NF-based algorithms for online bin packing with buffer and bounded item size
	Zheng, Feifeng 1; Luo, Li 2; Zhang, E.3
刊名	JOURNAL OF COMBINATORIAL OPTIMIZATION
	2015-08
卷号	30 期号:2 页码:360-369
关键词	Bin packing Online algorithm Asymptotic competitive ratio
ISSN号	1382-6905
DOI	10.1007/s10878-014-9771-8
英文摘要	This paper studies a variation of online bin packing where there is a capacitated buffer to temporarily store items during packing, and item size is bounded within for some . The problem is motivated by surgery scheduling such that we regard the planned uniform available time interval in each day as a unit size bin and surgeries as items to be packed. Our focus is on the asymptotic performance of NF (Next Fit) and NF-based online algorithms. We show that the classical NF algorithm without use of the buffer has an asymptotic competitive ratio of . An NF-based algorithm which makes use of the buffer is further proposed, and proved to be asymptotic 13/9-competitive for any given buffer size not less than 1. We also present a lower bound of 4/3.
WOS研究方向	Computer Science ; Mathematics
语种	英语
出版者	SPRINGER
WOS记录号	WOS:000357045600010
内容类型	期刊论文
源URL	[http://10.2.47.112/handle/2XS4QKH4/1506]
专题	上海财经大学
通讯作者	Zhang, E.
作者单位	1.Donghua Univ, Glorious Sun Sch Business & Management, Shanghai 200092, Peoples R China; 2.Sichuan Univ, Sch Business, Chengdu 610064, Peoples R China; 3.Shanghai Univ Finance & Econ, Sch Informat Management & Engn, Shanghai 200433, Peoples R China
推荐引用方式 GB/T 7714	Zheng, Feifeng,Luo, Li,Zhang, E.. NF-based algorithms for online bin packing with buffer and bounded item size[J]. JOURNAL OF COMBINATORIAL OPTIMIZATION,2015,30(2):360-369.
APA	Zheng, Feifeng,Luo, Li,&Zhang, E..(2015).NF-based algorithms for online bin packing with buffer and bounded item size.JOURNAL OF COMBINATORIAL OPTIMIZATION,30(2),360-369.
MLA	Zheng, Feifeng,et al."NF-based algorithms for online bin packing with buffer and bounded item size".JOURNAL OF COMBINATORIAL OPTIMIZATION 30.2(2015):360-369.