Об онлайновых алгоритмах для задач упаковки в контейнеры и полосы, их анализе в худшем случае и в среднем

В работе рассмоторены онлайновые алгоритмы для классических задач упаковки Bin Packing и Strip Packing и их обобщений: задач Multidimensional Bin Packing, Multiple Strip Packing и задаче об упаковке в полосы различной ширины. Для последней задачи описан анализ в худшем случае; для остальных задач приведен как анализ в худшем случае, так и анализ в среднем (вероятностный анализ). Рассмотрены лучшие известные нижние и верхние оценки. Приведены основные алгоритмы и описаны методы их анализа.

Bin Packing, Multidimensional Bin Packing, Strip Packing, Multiple Strip Packing, задача об упаковке в полосы различной ширины, вероятностный анализ, анализ в худшем случае

1. Массобрио Р., Несмачнов С., Черных А., Аветисян А., Радченко Г. Применение облачных вычислений для анализа данных большого объёма в умных городах. Труды ИСП РАН, том 28, вып. 6, 2016 г., стр. 121-140, DOI: 10.15514/ISPRAS-2016-28(6)-9

2. Аничкин А.С., Семенов В.А. Математическая формализация задач проектного планирования в расширенной постановке. Труды ИСП РАН,том 29, вып. 2, 2017 г., стр. 231-256. DOI: 10.15514/ISPRAS-2017-29(2)-9

3. Зеленова С.А., Зеленов С.В. Критерий существования бесконфликтного расписания для системы строго периодических задач. Труды ИСП РАН, том 29, вып. 6, 2017 г., стр. 183-202. 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. Кузюрин Н.Н., Поспелов А.И. Вероятностный анализ различых шельфовых алгоритмов упаковки прямоугольников в полосу. Труды ИСП РАН, том 12, 2007 г., стр. 17-26

39. Кузюрин Н.Н., Поспелов А.И. Вероятностный анализ нового класса алгоритмов упаковки прямоугольников в полосу. Ж. вычисл. матем. и матем. физ., том 51, no. 10, 2011, стр. 1931-1936

40. Трушников М.А. Об одной задаче Коффмана-Шора, связанной с упаковкой прямоугольников в полосу. Труды ИСП РАН, том 22, 2012 г., стр. 456-462, DOI: 10.15514/ISPRAS-2012-22-24

41. Трушников М.А. Вероятностный анализ нового алгоритма упаковки прямоугольников в полосу. Труды ИСП РАН, том 24, 2013 г., стр. 457-468, DOI: 10.15514/ISPRAS-2013-24-21

42. Лазарев Д.О., Кузюрин Н.Н. Алгоритм упаковки прямоугольников в несколько полос и анализ его точности в среднем. Труды ИСП РАН, том 29, вып. 6, 2017 г., стр. 221-228, DOI: 10.15514/ISPRAS-2017-29(6)-13

43. Кузюрин Н.Н., Грушин Д.А., Фомин А. Проблемы двумерной упаковки и задачи оптимизации в распределённых вычислительных системах. Труды ИСП РАН, том 26, вып. 1, 2014 г., стр. 483-502, 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. Жук С.Н. Анализ некоторых эвристик упаковки прямоугольников в несколько полос. Труды ИСП РАН, том 6, 2004 г., стр. 13-26

47. Жук С.Н. Онлайновый алгоритм упаковки прямоугольников в несколько полос с гарантированными оценками точности. Труды ИСП РАН, том 12, 2007 г., стр. 7-16

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. Жук С.Н. О построении расписаний выполнения параллельных задач на группах кластеров с различной производительностью. Труды ИСП РАН, том 23, 2012 г., стр. 447-454, DOI: 10.15514/ISPRAS-2012-23-27