Алгоритм для многомерной упаковки в контейнеры и его вероятностный анализ

Проводится анализ в среднем задачи упаковки -мерных прямоугольных параллелепипедов в контейнеры. Для решения задачи, предложен алгоритм увеличения размерности, позволяющий эффективно строить алгоритм упаковки в (d+1)-мерные контейнеры, используя алгоритм упаковки в d-мерные контейнеры. При упаковке, стремимся минимизировать ожидаемый объем незаполненного пространства использованных контейнеров. Ранее известные результаты верхней оценки числа упаковываемых параллелепипедов улучшены. Уменьшение объема незаполненного пространства подтверждают проведенные вычислительные эксперименты. При анализе алгоритмов в среднем, может возникать переобучение. Связано оно с тем, что минимальный ожидаемый объем незаполненного пространства может достигаться для одного конкретного распределения, или для семейства распределений входных параметров алгоритма, в решаемой задаче входные параметры – длины сторон параллелепипедов. Для борьбы с данным нежелательным эффектом, предложенный алгоритм увеличения размерности был обобщен на случай произвольного заранее известного распределения длин сторон параллелепипедов. Эффективность обобщенного алгоритма подтверждена вычислительными экспериментами.

1. Johnson, David S., et al. Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM Journal on computing 3.4, 1974, pp. 299-325. DOI: 10.1137/0203025.

2. Coffman Jr, Edward G., Michael R. Garey, and David S. Johnson. Approximation algorithms for bin-packing—an updated survey. Algorithm design for computer system design. Springer Vienna, 1984, pp. 49-106. DOI: 10.1007/978-3-7091-4338-4.

3. Li, Xueping, and Kaike Zhang. Single batch processing machine scheduling with two-dimensional bin packing constraints. International Journal of Production Economics 196, 2018, pp. 113-121. DOI: 10.1016/j.ijpe.2017.11.015.

4. Paquay, Célia, Michael Schyns, and Sabine Limbourg. A mixed integer programming formulation for the three‐dimensional bin packing problem deriving from an air cargo application. International Transactions in Operational Research 23.1-2, 2016, pp. 187-213. DOI: 10.1111/itor.12111.

5. Tchernykh, Andrei, et al. On-line hierarchical job scheduling on grids with admissible allocation. Journal of Scheduling 13.5, 2010, pp. 545-552. DOI: 10.1007/s10951-010-0169-x.

6. Tchernykh, Andrei, et al. Two level job-scheduling strategies for a computational grid. International Conference on Parallel Processing and Applied Mathematics. Berlin, Heidelberg: Springer Berlin Heidelberg, 2005, pp. 774-781. DOI: 10.1007/11752578_93.

7. Gohil, Bhavesh, et al. A comparative analysis of virtual machine placement techniques in the cloud environment. International Journal of Computer Applications 156.14, 2016, pp. 12-18. DOI: 0.5120/ijca2016912530.

8. Garey, Michael R., and David S. Johnson. Computers and intractability. Vol. 29. New York: wh freeman, 2002. 338 pp.

9. Brown, Donna J. A Lower Bound for On-Line One-Dimensional Bin Packing Algorithms. No. ACT19. 1979, pp. 1-21. DOI: 10.1016/S0020-0190(80)90077-0.

10. van Vliet, André. An improved lower bound for on-line bin packing algorithms. Information processing letters 43.5, 1992, pp. 277-284. DOI: 10.1016/0020-0190(92)90223-I.

11. Galambos, Gabor, and André van Vliet. Lower bounds for 1-, 2-and 3-dimensional on-line bin packing algorithms. Computing 52.3, 1994, pp. 281-297. DOI: 10.1007/BF02246509.

12. Han, Xin, et al. A new upper bound 2.5545 on 2d online bin packing. ACM Transactions on Algorithms (TALG) 7.4, 2011, pp. 1-18. DOI: 10.1145/2000807.2000818.

13. Csirik, János, and André Van Vliet. An on-line algorithm for multidimensional bin packing. Operations Research Letters 13.3, 1993, pp. 149-158. DOI: 10.1016/0167-6377(93)90004-Z.

14. Shor, Peter W. The average-case analysis of some on-line algorithms for bin packing. Combinatorica 6.2, 1986, pp. 179-200. DOI: 10.1007/BF02579171.

15. Shor, Peter W. How to pack better than best fit: tight bounds for average-case online bin packing. Proceedings 32nd Annual Symposium of Foundations of Computer Science, IEEE Computer Society, 1991, pp. 752-759, DOI: 10.1109/SFCS.1991.185444.

16. Leighton, Frank Thomson, and Peter Shor. Tight bounds for minimax grid matching, with applications to the average case analysis of algorithms. Proceedings of the eighteenth Annual ACM symposium on theory of computing, 1986, pp. 91-103, DOI: 10.1145/12130.12140.

17. Chang, Ee-Chien, Weiguo Wang, and Mohan S. Kankanhalli. Multidimensional on-line bin-packing: An algorithm and its average-case analysis. Information Processing Letters 48.3, 1993, pp. 121-125. DOI: 10.1016/0020-0190(93)90253-6.

18. Chung, Fan, and Linyuan Lu. Connected components in random graphs with given expected degree sequences. Annals of combinatorics 6.2, 2002, pp. 125-145. DOI: 10.1007/PL00012580.