An improvement of previously known upper bound of Multiple Strip Packing problem and probabilistic analysis of algorithm in case of large number of strips given
https://doi.org/10.15514/ISPRAS-2019-31(1)-9
Abstract
In this article, an analog of previously proposed algorithm Limited Hash Packing for Multiple Strip Packing Problem is studied using probabilistic analysis. Limited Hash Packing is an on-line algorithm, which works in closed-end mode, knowing the number of rectangles it has to pack before knowing the heights and width of the first rectangle.
About the Authors
Denis Olegovitch Lazarev
Ivannikov Institute for System Programming of the Russian Academy of Sciences
Russian Federation
Russian Federation
Nikolay Nikolaevitch Kuzyurin
Ivannikov Institute for System Programming of the Russian Academy of Sciences
Moscow Institute of Physics and Technology
Russian Federation
Russian Federation
References
1. . Two-dimensional packing problems and optimization in distributed computing systems N.N. Kuzyurin, D.A. Grushin, S.A. Fomin, Trudy ISP RAS/Proc. ISP RAS, vol. 26, issue 1, 2015, pp. 483–502(in Russian). DOI: 10.15514/ISPRAS-2014-26(1)-21
2. . 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
3. . S.N. Zhuk. Approximate algorithms for packing rectangles into several strips. Discrete Mathematics and Applications, vol 18, issue 1, 2006, pp. 91-105.
4. . Tchernykh A., Schwiegelshohn U., Yahyapour R., Kuzjurin N. On-line hierarchical job scheduling on grids with admissible allocation. Journal of Scheduling, vol. 13, issue 5, 2010, pp. 545-552.
5. . 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, vol. 3911, 2005, pp. 774-781.
6. . 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.
7. . Garey M.R. Graham R.L., Ullman J.D., Worst-case analysis of memory allocation algorithms. In Proc. of the fourths annual ACM symposium on theory of computing (STOC ’72), 1972, pp. 143-150.
8. . Garey M.R., Johnson D.S. Computers and intractability: a guide to the theory of NP-completeness. Freeman, San Francisco, 1979, 338 p.
9. . Johnson D.S. Near-optimal Bin Packing Algorithms. PhD Thesis, Massachusetts Institute of Technology, Department of Mathematics, Cambridge, 1973, 401 p.
10. . Vliet A. An improved lower bound for on-line bin packing algorithms. Journal of information Processing Letters, vol. 43, issue 5, 1992, pp. 277-284.
11. . 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 Proc. of the twenty-third annual ACM symposium on Theory of Computing (STOC '91), 1991, pp. 230-240.
12. . Shor P.W. How to pack better than Best Fit: tight bounds for average-case online Bin Packing. In Proc. of the 32nd Annual Symposium of foundations of Computer Science, 1991, pp. 752-759.
13. . 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.
14. . Kuzjurin N.N., Pospelov A.I. Probabilistic analysis of a new class of strip packing algorithms. Computational Mathematics and Mathematical Physics, vol. 51, no. 10, 2011, pp. 1817–1822.
15. . 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, doi: 10.15514/ISPRAS-2012-22-24
16. . Trushnikov M.A. Probabilistic analysis of a new strip packing algorithm. Trudy ISP RAN/Proc. ISP RAS, vol. 24, 2013, pp. 457-468, doi: 10.15514/ISPRAS-2013-24-21
17. . 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
Review
For citations:
Lazarev D.O., Kuzyurin N.N. An improvement of previously known upper bound of Multiple Strip Packing problem and probabilistic analysis of algorithm in case of large number of strips given. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2019;31(1):133-142. (In Russ.) https://doi.org/10.15514/ISPRAS-2019-31(1)-9
Email this article 