NF-based algorithms for online bin packing with buffer and bounded item size | |
Zheng, Feifeng1; Luo, Li2; 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. |
个性服务 |
查看访问统计 |
相关权益政策 |
暂无数据 |
收藏/分享 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论