We study the on-line bin packing problem (BPP). In BPP, we are given a sequence B of items a1, a2, … an and a sequence of their sizes (s1, s2, … sn) (each size si ∈ (0,1]) and are required to pack the items into a minimum number of unit-capacity bins. Let R∞{α,β} be the minimal asymptotic competitive ratio of an on-line algorithm in the case when all items are only of two different sizes α and β. We prove that max{R∞{α,β} : , ∈ (0,1]} = 4/3. We also obtain an exact formula for R∞{α,β} when max{α,β) > 1/2. This result extends the result of Faigle et al. that R∞{α,β} = 4/3 for β=1/2−ε and α=1/2+ε for any fixed nonnegative ε<1/6.
