Preview

Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS)

Advanced search

On on-line algorithms for Bin, Strip and Box Packing, and their worstand average-case analysis

https://doi.org/10.15514/ISPRAS-2018-30(4)-14

Abstract

In this survey, online algorithms for such packing problems as Bin Packing, Strip Packing and their generalizations, such as Multidimensional Bin Packing, Multiple Strip Packing and packing into strips of different width were considered. For the latter problem only worst-case analysis was described, for all other problems, both worst-case and average case (probabilistic analysis) asymptotical ratios were considered. Both lower and upper bonds were described. Basic algorithms and methods for their analysis were considered. For worst-case analysis of the Bin Packing Problem it was shown that for any online algorithm R^∞≥1.540, and an algorithm with R^∞≤1.589 was obtained. Both approaches for analyzing the algorithm and obtaining the lower bonds were discussed. Also it was shown that First Fit algorithm for Bin Packing has asymptotical competitive ratio of 17/10. For average case analysis in the case when object’s sizes have a uniform distribution on [0,1] in open-end analysis a construction for obtaining both lower bound of W_ ^n= Ω(√(n ln⁡n )) and algorithm with W_ ^n= θ(√(n ln⁡n )) was shown. In the case of closed-end analysis an algorithm with W_ ^n= θ(√n) was described. For Multidimensional Bin Packing with d dimensions an algorithm with R_ ^∞=(П_∞ )^d, where П_∞≈1.691, was obtained. For average case analysis an algorithm with W_A^n=O(n^((d+1)/(d+2))) was shown. For worst-case analysis of Strip Packing Problem and Multiple Strip Packing Problem algorithms with R^∞≤1.589 were also obtained. For the closed-end average case analysis algorithms with W_ ^n= θ(√n ln⁡n) were described. For the open-end average case analysis of Strip Packing Problem an algorithm with W_ ^n= O(n^(2/3) ) was considered. For generalization of Multiple Strip Packing Problem, where strips have different widths, an online algorithm with R_ ^∞≤2e/r for any r<1, where e=2.718…, was described.

About the Authors

D. O. Lazarev
Ivannikov Institute for System Programming of the Russian Academy of Sciences; Moscow Institute of Physics and Technology
Russian Federation


N. N. Kuzjurin
Ivannikov Institute for System Programming of the Russian Academy of Sciences; Moscow Institute of Physics and Technology
Russian Federation


References

1. Massobrio R., Nesmachnow S., Tchernykh A., Avetisyan A., Radchenko G. Towards a Cloud Computing Paradigm for Big Data Analysis in Smart Cities. Trudy ISP RAN/Proc.ISP RAS, vol. 28, issue 6, 2016. pp. 121-140 (in Russian). DOI: 10.15514/ISPRAS-2016-28(6)-9

2. Anichkin A.S., Semenov V.A. Mathematical formalization of project scheduling problems. Trudy ISP RAN/Proc. ISP RAS, vol. 29, issue 2, 2017. pp. 231-256 (in Russian). DOI: 10.15514/ISPRAS-2017-29(2)-9

3. Zelenova S.A., Zelenov S.V. Non-conflict scheduling criterion for strict periodic tasks. Trudy ISP RAN/Proc. ISP RAS, vol. 29, issue 6, 2017. pp. 183-202 (in Russian). DOI: 10.15514/ISPRAS-2017-29(6)-10

4. Ghalam L., Grosu D. A Parallel Approximation Algorithm for Scheduling Identical Machines. In IEEE International Parallel and Distributed Processing Symposium Workshops, 2017, pp. 619-628

5. Sheikhalishahi M., Wallace R. M., Grandinetti L., Vazquez-Poletti J. L., Guerriero F. A multi-dimensional job scheduling. Future Generation Computer Systems, vol. 54, 2016, pp. 123-131

6. Tchernykh A., Schwiegelshohn U., Yahyapour R., Kuzjurin N. On-line hierarchical job scheduling on grids with admissible allocation. Journal of Scheduling, 2010, vol. 13, issue 5, pp. 545-552

7. Tshernykh A., Ramirez J.M., Avetisyan A., Kuzjurin N., Grushin D., Zhuk S. Two-Level Job-Scheduling strategies for a Computational Grid. Lecture Notes in Computer Science book series, vol. 3911, pp. 774-781

8. Cohil B., Shah S., Goleshha Y., Patel D. A Comparative Analysis of Virtual Machine Placement Techniques in the Cloud Environment. International Journal of Computer Applications, vol. 156, no. 14, 2016, pp. 12-18

9. Garey M.R., Johnson D.S. Computers and intractability: a guide to the theory of NP-completeness. Freeman: San Francisco, 1979, 338 p.

10. Johnson D.S. Near-optimal Bin Packing Algorithms. PhD Thesis, Massachusetts Institute of Technology, Department of Mathematics, Cambridge, 1973. 401 p.

11. Johnson D.S., Demers A., Ullman J.D., Garey M.R., Graham R.L. Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms. SIAM Journal on computing, vol. 3, issue 4, 1974, pp. 299- 325

12. Garey M.R. Graham R.L., Ullman J.D., Worst-case analysis of memory allocation algorithms. Proceedings of the fourth annual ACM symposium on theory of computing. 1972, pp. 143-150

13. Garey M.R., Graham R.L., Johnson D.S., Yao A.C. Resource constrained scheduling as generalized bin packing. Journal of Combinatorial Theory, Series A, vol. 21, issue 3, 1976, pp. 257-298

14. Yao A.C. New Algorithms for Bin Packing. Journal of the ACM, vol. 27, issue 2, 1981, pp. 207-227

15. Gambosi G., Postiglione a., Talamo M.M. New algorithms for online Bin Packing. In Proceedings of the First Italian Conference on Algorithms and Complexity, 1990, pp. 44-59

16. Ivcović Z. and Lloyd E. Fully dynamic algorithms for Bin Packing: Being (mostly) myopic helps. Lecture Notes in Computer Science, vol. 726, pp. 224-235

17. Seiden S.S. On the Online Bin Packing Problem. Lecture Notes in computer science, vol. 2076, 2002, pp. 207-227

18. Brown J.D. A lower Bound for On-Line One Dimensional Bin Packing Algorithms. Technical Report R-864, coordinated Science laboratory, University of Illinois, Urbana, IL, 1979.

19. Vliet A. An improved lower bound for on-line bin packing algorithms. Information Processing Letters, vol. 43, issue 5, 1992, pp. 277-284

20. Breitgand D., Epstein A. Improving consolidations of virtual machines with risk-aware Bandwidth oversubscription in compute clouds. In Proceedings of the IEEE INFCOM, 2012, pp. 2861-2865

21. Ajtai M., Komlós J., Tusnadi G. On Optimal Matchings. Combinatorica, vol. 4, issue 4, 1984, pp. 259-264

22. Karp R.M., Luby M., Marchetti-Spaccamela A. A probabilistic analysis of multidimensional bin packing problem. In Proceedings of the sixteen annual ACM symposium on theory of computing, 1984, pp.289-298

23. Coffman E.G., Shor P.W. A Simple Proof of the sqrt(n log3/4 n) Upright Matching Bound. SIAM Journal on Discrete Mathematics, vol. 4, issue 1, 1991, pp. 48-57

24. Shor P.W. The average-case analysis of some on-line algorithms for bin packing. Combinatorica, vol. 6, issue 4, 1986, pp. 179-200

25. Leighton F.T., Shor P. Tight bonds for minimax grid matching, with application to the average-case analysis of algorithms. In Proceedings of the eighteenth Annual ACM symposium on theory of computing, 1986 , pp. 91-103

26. Coffman E.G., Courcoubetis C., Garey M.R., Johnson D.S., McGeoch L.A., Shor P.W., Weber R. and Yannakakis M. Fundamental discrepancies between average-case analysis under discrete and continuous distributions: a bin packing study. In Proceedings of the Twenty-first Annual ACM symposium on theory of computing, 1991, pp. 230-240

27. Shor P.W. How to pack better than Best Fit: tight bounds for average-case online Bin Packing. In Proceedings 32nd of the Annual Symposium of foundations of Computer Science, 1991, pp. 752-759

28. Galambos G., A. van Vliet. Lower bounds for 1-, 2-, and 3- dimensional on-line bin packing algorithms. Computing, vol. 52, issue 3, 1994, pp. 281-297

29. Han X., Chin F.Y.L., Ting H.-F., Zhang G., Zhang Y. A new upper bound 2.5545 on 2D Online Bin Packing. ACM Transactions on algorithms, vol. 7, issue 4, 2011, article No. 50

30. Csirik J., A. van Vliet. An on-line algorithm for multidimensional bin packing. Operation Research Letters, vol. 13, issue 3, 1993, pp. 149-158

31. Epstein l., R. van Stee. Optimal Online Algorithms for Multidimensional Packing Problems. In Proceedings of the Fifteenth Annual ACM-CIAM Symposium on Discrete algorithms, 2004, pp. 214-223

32. Chang E-C, Wang W., Kankanhalli M.S. Multidimensional on-line bin-packing: An algorithm and it’s average-case analysis. Information Processing Letters, vol. 48, issue 3, 1993, pp. 121-125

33. Baker B.S., Coffman E.G., Rivest R.L. Orthogonal Packings in Two Dimensions. SIAM Journal on Computing, vol. 9, issue 4, 1980, pp. 846-855

34. Baker B.S., Schwarz J.S. Shelf algorithms for two-dimensional packing problems. SIAM Journal on Computing, vol. 12, issue 3, 1983, pp. 508-525

35. Csirik J., Woeginger G.J. Shelf algorithms for on-line strip packing. Information Processing Letters, vol. 63, issue 4, 1997, pp. 171-175

36. Han X., Iwama K., Ye d., Zhang G. Strip Packing vs Bin Packing. Lecture Notes in Computer Science, vol. 4508, 2007, pp. 358-367

37. Coffman E.G., Shor P.W. Packing in two dimensions: Asymptotic average-case analysis of algorithms. Algorithmica, vol. 9, issue 3, 1993, pp. 253-277

38. Kuzjurin N.N., Pospelov A.I. Probabilistic analysis of different shelf algorithms for packing rectangles into a strip. Trudy ISP RAN/Proc. ISP RAS, vol. 12, 2007, pp. 17-26 (in Russian)

39. Kuzyurin N.N., Pospelov A.I. Probabilistic analysis of a new class of strip packing algorithms. Comput. Math. and Math. Phys., vol. 51, issue 10, 2011, article no. 1817

40. Trushnikov M.A. On one problem of Koffman-Shor connected to strip packing problem. Trudy ISP RAN/Proc. ISP RAS, vol. 22, 2012, pp. 456-462 (in Russian). DOI: 10.15514/ISPRAS-2012-22-24

41. Trushnikov M.A. Probabilistic analysis of a new strip packing algorithm. Trudy ISP RAN/Proc. ISP RAS, vol. 24, 2013, str. 457-468 (in Russian). DOI: 10.15514/ISPRAS-2013-24-21

42. Lazarev D.O., Kuzyrin N.N. An algorithm for Multiple Strip Package and its average case evaluation. Trudy ISP RAN/Proc. ISP RAS, vol. 29, issue 6, 2017. pp. 221-228 (in Russian). DOI: 10.15514/ISPRAS-2017-29(6)-13

43. Kuzjurin N.N., Grushin D.A., Fomin A. Two-dimensional packing problems and optimization in distributed computing systems. Trudy ISP RAN/Proc. ISP RAS, vol. 26, issue 1, 2014, pp. 483-502 (in Russian). DOI: 10.15514/ISPRAS-2014-26(1)-21

44. Ye D., Han X., Zhang G. Online multiple-strip packing. Theoretical Computer Science, vol. 412, issue 3, 2011, pp. 233-239

45. Zhuk S.N. Approximation algorithms for packing rectangles into several strips. Discrete Mathematics and Applications, vol. 16, issue 1, 2006, pp. 73-85

46. Zhuk S.N. Analysis of some heuristics of packing rectangles into several strips. Trudy ISP RAN/Proc. ISP RAS, vol. 6, 2004, pp. 13-26 (in Russian)

47. Zhuk S.N. Online algorithm for packing rectangles into several strips with guaranteed accuracy estimates. Trudy ISP RAN/Proc. ISP RAS, vol. 12, 2007, pp. 7-16 (in Russian)

48. Zhuk S.N. On-line algorithms for packing rectangles into several strips. Discrete Mathematics and Applications, vol. 17, issue 5, 2007, pp. 517-531

49. Zhuk S.N. On-line algorithm for scheduling parallel tasks on a group of related clusters. Trudy ISP RAN/Proc. ISP RAS, vol. 23, 2012, pp. 447-454 (in Russian). DOI: 10.15514/ISPRAS-2012-23-27


Review

For citations:


Lazarev D.O., Kuzjurin N.N. On on-line algorithms for Bin, Strip and Box Packing, and their worstand average-case analysis. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2018;30(4):209-230. (In Russ.) https://doi.org/10.15514/ISPRAS-2018-30(4)-14



Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License.


ISSN 2079-8156 (Print)
ISSN 2220-6426 (Online)