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

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 $$(\alpha, 1/2]$$(,1/2] for some $$0\le \alpha < 1/2$$0≤ <1/2. 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 $$2/(1+\alpha )$$2/(1+ ). 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.