Nothing Special   »   [go: up one dir, main page]

skip to main content
article

Online bin packing problem with buffer and bounded size revisited

Published: 01 February 2017 Publication History

Abstract

In this paper we study the online bin packing with buffer and bounded size, i.e., there are items with size within $$(\alpha,1/2]$$(ź,1/2] where $$0 \le \alpha < 1/2 $$0≤ź<1/2, and there is a buffer with constant size. Each time when a new item is given, it can be stored in the buffer temporarily or packed into some bin, once it is packed in the bin, we cannot repack it. If the input is ended, the items in the buffer should be packed into bins too. In our setting, any time there is at most one bin open, i.e., that bin can accept new items, and all the other bins are closed. This problem is first studied by Zheng et al. (J Combin Optim 30(2):360---369, 2015), and they proposed a 1.4444-competitive algorithm and a lower bound 1.3333 on the competitive ratio. We improve the lower bound from 1.3333 to 1.4230, and the upper bound from 1.4444 to 1.4243.

References

[1]
Balogh J, Békési J, Galambos G (2012) New lower bounds for certain classes of bin packing algorithms. Theor Comput Sci 440-441:1-13.
[2]
Coffman EG, Garey JMR, Johnson DS (1996) Approximation algorithms for bin-packing: a survey. In: Hochbaumed DS (ed) Approximation algorithms of NP-hard problems. PWS Publishing Company, Boston.
[3]
Ding N, Lan Y, Chen X, Dsa G, Guo H, Han X (2014) Online Minimum makespan scheduling with a buffer. Int J Found Comput Sci 25(5):525-536.
[4]
Dosa G, Tuza Z, Ye DS (2013) Bin packing with "Largest In Bottom" constraint: tighter bounds and generalizations. J Combin Optim 26(3):416-436.
[5]
Eisemann K (1957) The trim problem. Manag Sci 3(3):279-284.
[6]
Epstein L, Levin A (2008) More on online bin packing with two item sizes. Discret Optim 5(4):705-713.
[7]
Gutin G, Jensen T, Yeo A (2006) Optimal on-line bin packing with two item sizes. Algorithm Oper Res 1(2):72-78.
[8]
Han X, Peng C, Ye D, Zhang DH, Lan Y (2010) Dynamic bin packing with unit fraction items revisited. Inf Process Lett 110(23):1049-1054.
[9]
Johnson DS (1974) Fast algorithms for bin packing. J Comput Syst Sci 8(3):272-314.
[10]
Lee CC, Lee DT (1985) A simple on-line bin-packing algorithm. J ACM 32(3):562-572.
[11]
Ramanan P, Brown DJ, Lee CC, Lee DT (1989) On-line bin packing in linear time. J Algorithm 10(3):305- 326.
[12]
Seiden SS (2002) On the online bin packing problem. J ACM 49(5):640-671.
[13]
Yao ACC (1980) New algorithms for bin packing. J ACM 27(2):207-227.
[14]
Zheng FF, Luo L, Zhang E (2015) NF-based algorithms for online bin packing with buffer and bounded item size. J Combin Optim 30(2):360-369.

Cited By

View all
  • (2021)Solving fully dynamic bin packing problem for virtual machine allocation in the cloud environment by the futuristic greedy algorithmJournal of Intelligent & Fuzzy Systems: Applications in Engineering and Technology10.3233/JIFS-20158140:3(4737-4760)Online publication date: 1-Jan-2021
  • (2018)Tight bounds for NF-based bounded-space online bin packing algorithmsJournal of Combinatorial Optimization10.1007/s10878-017-0175-435:2(350-364)Online publication date: 21-Dec-2018

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Combinatorial Optimization
Journal of Combinatorial Optimization  Volume 33, Issue 2
February 2017
444 pages

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 February 2017

Author Tags

  1. Asymptotic competitive ratio
  2. Bin packing
  3. Online algorithm

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 14 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2021)Solving fully dynamic bin packing problem for virtual machine allocation in the cloud environment by the futuristic greedy algorithmJournal of Intelligent & Fuzzy Systems: Applications in Engineering and Technology10.3233/JIFS-20158140:3(4737-4760)Online publication date: 1-Jan-2021
  • (2018)Tight bounds for NF-based bounded-space online bin packing algorithmsJournal of Combinatorial Optimization10.1007/s10878-017-0175-435:2(350-364)Online publication date: 21-Dec-2018

View Options

View options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media