Улучшение ранее известной верхней оценки для задачи Multiple Strip Packing и вероятностный анализ алгоритма для большого числа полос
https://doi.org/10.15514/ISPRAS-2019-31(1)-9
Аннотация
В работе рассмотрена задача упаковки прямоугольников в полосы единичной ширины Multiple Strip Packing. Рассмотрен аналог ранее предложенного алгоритма, алгоритм упаковки в области ограниченной высоты Limited Hash Packing и произведён его вероятностный анализ. Алгоритм онлайновый и работает в режиме closed-end, когда число прямоугольников, которые нужно упаковать известно алгоритму до начала работы.
Ключевые слова
Strip Packing,
Multiple Strip Packing,
онлайновый алгоритм,
режим closed-end,
вероятностный анализ,
алгоритм упаковки прямоугольников в ограниченные области,
Limited Hash Packing
При поддержке: РФФИ
Об авторах
Денис Олегович Лазарев
Институт системного программирования им. В.П. Иванникова РАН
Россия
Россия
Николай Николаевич Кузюрин
Институт системного программирования им. В.П. Иванникова РАН,
Московский физико-технический институт
Россия
Россия
Список литературы
1. . Кузюрин Н., Грушин Д., Фомин С. Проблемы двумерной упаковки и задачи оптимизации в распределенных вычислительных системах. Труды ИСП РАН, том 26, вып. 1, 2014 г., стр. 483–502, DOI: 10.15514/ISPRAS-2014-26(1)-21.
2. . С.Н. Жук. О построении расписаний выполнения параллельных задач на группах кластеров с различной производительностью. Труды ИСП РАН, том 23, 2012, стр. 447-454, 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. . Кузюрин Н.Н., Поспелов А.И. Вероятностный анализ нового класса алгоритмов упаковки прямоугольников в полосу. Журнал вычислительной математики и математической физики, том 51, no. 10, 2011, стр. 1931-1936.
15. . Трушников М.А. Об одной задаче Коффмана-Шора, связанной с упаковкой прямоугольников в полосу. Труды ИСП РАН, том 22, 2012 г., стр. 456-462, doi: 10.15514/ISPRAS-2012-22-24.
16. . Трушников М.А. Вероятностный анализ нового алгоритма упаковки прямоугольников в полосу. Труды ИСП РАН, том 24, 2013 г., стр. 457-468, doi: 10.15514/ISPRAS-2013-24-21/
17. . Лазарев Д.О., Кузюрин Н.Н. Алгоритм упаковки прямоугольников в несколько полос и анализ его точности в среднем. Труды ИСП РАН, том 29, выпуск 6, 2017 г., стр. 221-228, doi:: 10.15514/ISPRAS-2017-29(6)-13
Рецензия
Для цитирования:
Лазарев Д.О., Кузюрин Н.Н. Улучшение ранее известной верхней оценки для задачи Multiple Strip Packing и вероятностный анализ алгоритма для большого числа полос. Труды Института системного программирования РАН. 2019;31(1):133-142. https://doi.org/10.15514/ISPRAS-2019-31(1)-9
For citation:
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
Послать статью по эл. почте 