Hostname: page-component-cd9895bd7-gbm5v Total loading time: 0 Render date: 2024-12-23T18:34:02.606Z Has data issue: false hasContentIssue false
  • English
  • Français

Bin Packing with Queues

Part of: Operations research and management science

Published online by Cambridge University Press:  14 July 2016

Devavrat Shah  and
John N. Tsitsiklis
Devavrat Shah*
Affiliation:
Laboratory for Information and Decision Systems, MIT
John N. Tsitsiklis*
Affiliation:
Laboratory for Information and Decision Systems, MIT
*
∗Postal address: Laboratory for Information and Decision Systems, MIT, 77 Massachusetts Avenue, Cambridge, MA 02139, USA.
∗Postal address: Laboratory for Information and Decision Systems, MIT, 77 Massachusetts Avenue, Cambridge, MA 02139, USA.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We study the best achievable performance (in terms of the average queue size and delay) in a stochastic and dynamic version of the bin-packing problem. Items arrive to a queue according to a Poisson process with rate 2ρ, where ρ ∈ (0, 1). The item sizes are independent and identically distributed (i.i.d.) with a uniform distribution in [0, 1]. At each time unit, a single unit-size bin is available and can receive any of the queued items, as long as their total size does not exceed 1. Coffman and Stolyar (1999) and Gamarnik (2004) have established that there exist packing policies under which the average queue size is finite for every ρ ∈ (0, 1). In this paper we study the precise scaling of the average queue size, as a function of ρ, with emphasis on the critical regime where ρ approaches 1. Standard results on the probabilistic (but static) bin-packing problem can be readily applied to produce policies under which the queue size scales as O(h2), where h = 1 / (1 - ρ), which raises the question of whether this is the best possible. We establish that the average queue size scales as Ω(hlogh), under any policy. Furthermore, we provide an easily implementable policy, which packs at most two items per bin. Under that policy, the average queue size scales as O(hlog3/2h), which is nearly optimal. On the other hand, if we impose the additional requirement that any two items packed together must have near-complementary sizes (in a sense to be made precise), we show that the average queue size must scale as Θ(h2).

Keywords

Bin packingqueueingheavy traffic

MSC classification

Secondary: 90B36: Scheduling theory, stochastic 90B22: Queues and service
Type
Research Article
Information
Journal of Applied Probability , Volume 45 , Issue 4 , December 2008 , pp. 922 - 939
Copyright
Copyright © Applied Probability Trust 2008 

References

[1] Ajtai, M., Komós, J. and Tusnády, G. (1983). On optimal matchings. Combinatorica 4, 259–264.CrossRefGoogle Scholar
[2] Bentley, J. L. et al.(1984). Some unexpected expected behavior results for bin packing. In Proc. 16th Annual ACM Symp. Theory Comput., ACM, New York, pp. 279–288.Google Scholar
[3] Bertsimas, D. J. and Van Ryzin, G. (1993). Stochastic and dynamic vehicle routing in the Euclidean plane with multiple-capacitated vehicles. Operat. Res. 41, 60–76.Google Scholar
[4] Bertsimas, D. J. and Van Ryzin, G. (1993). Stochastic and dynamic vehicle routing with general demand and interarrival time distributions. Adv. Appl. Prob. 20, 947–978.Google Scholar
[5] Coffman, E. G. and Stolyar, A. L. (2001). Bandwidth packing. Algorithmica 29, 70–88.Google Scholar
[6] Coffman, E. G. Jr., Galambos, G., Martello, S. and Vigo, D. (1998). Bin packing approximation algorithms: combinatorial analysis. In Handbook of Combinatorial Optimization, eds Du, D.-Z. and Pardalos, P. M., Kluwer, Boston.Google Scholar
[7] Dembo, A. and Zeitouni, O. (1998) Large Deviations Techniques and Applications, 2nd edn. Springer, New York.Google Scholar
[8] Gamarnik, D. (2004). Stochastic bandwidth packing process: stability conditions via Lyapunov function technique. Queueing Systems 48, 339–363.Google Scholar
[9] Karp, R. M., Luby, M. and Marchetti-Spaccamela, A. (1984). Probabilistic analysis of multidimensional bin packing problems. In Proc. 16th Annual ACM Symp. Theory Comput., ACM, New York, pp. 289–298.Google Scholar
[10] Knodel, W. (1981). A bin-packing algorithm with complexity O(n log n) and performance 1 in the stochastic limit. In Proc. Math. Foundations Comput. Sci. Springer, London, pp. 369–378.Google Scholar
[11] Leighton, T. and Shor, P. (1986). Tight bounds for minimax grid matching, with applications to the average case analysis of algorithms. In Proc. 18th Annual ACM Symp. Theory Comput., ACM, New York, pp. 91–103.Google Scholar
[12] Lueker, G. S. (1983). Bin packing with items uniformly distributed over intervals [a,b]. In Proc. 24th Annual Symp. Foundations Comput. Sci., IEEE Computer Society, Washington, DC, pp. 289–297.Google Scholar
[13] Motwani, R. and Raghavan, P. (1995). Randomized Algorithms. Cambridge University Press.CrossRefGoogle Scholar
[14] Rhee, W. T. (1988). Optimal bin-packing with items of random sizes. Math. Operat. Res. 13, 140–151.CrossRefGoogle Scholar
[15] Rhee, W. T. (1990). A note on optimal bin packing and optimal bin covering with items of random sizes. SIAM J. Comput. 19, 705–710.Google Scholar
[16] Rhee, W. T. and Talagrand, M. (1989). Optimal bin packing with items of random sizes. II. SIAM J. Comput. 18, 139–151.Google Scholar
[17] Rhee, W. T. and Talagrand, M. (1989). Optimal bin packing with items of random sizes. III. SIAM J. Comput. 18, 473–486.Google Scholar
[18] Rhee, W. T. (1993). Optimal bin packing of items of size uniformly distributed over [0,1]. Math. Operat. Res. 18, 694–704.Google Scholar
[19] Shor, P. W. (1986). The average case analysis of some on-line algorithms for bin packing. Combinatorica 6, 179–200.Google Scholar
[20] Vempala, S. and Vocking, B. (1999). Approximating multicast congestion. In Proc. 10th Int. Symp. Algorithms and Computation, Springer, London, pp. 367–372.Google Scholar
[21] Wolff, R. W. (1989). Stochastic Modeling and the Theory of Queues. Prentice-Hall, Englewood Cliffs, NJ.Google Scholar