Parallel Algorithm of Balanced Sparse Packing of Rectangular Parallelepipeds

Abstract

Introduction. Varieties of the problem of packing of rectangular parallelepipeds have a wide practical application in various fields of activity, for example, in the optimal filling of containers, in the design and layout of a wide variety of technological objects and systems, in the creation of backup copies on removable media, in the optimization of storage, protection and transportation of goods, in additive manufacturing, etc. This work continues research on this topic and is devoted to the problem of balanced sparse packing of a given set of identically oriented rectangular parallelepipeds of different sizes into a rectangular parallelepiped of minimum volume. It presents a mathematical model for this packing problem and a parallel algorithm for solving it. This algorithm is based on the reduction of the original problem to an unconditional optimization problem using penalty functions, which is solved by the multistart method, in which r-algorithm is used to find local minima from the set of generated starting points. The purpose. Construction of a mathematical model and development of an algorithm for solving the problem of balanced sparse packing of a given set of identically oriented rectangular parallelepipeds into a rectangular parallelepiped of minimum volume. Results. A mathematical model and a parallel algorithm for balanced sparse packing of identically oriented rectangular parallelepipeds into a rectangular parallelepiped of minimum volume are presented. The algorithm is based on reducing the problem with the help of penalty functions to an unconditional nondifferentiable optimization problem, for finding the solution of which multistart method is used in combination with r-algorithm for finding local minima. The results of numerical experiments are given. Conclusions. The application of the algorithm described in the work based on non-smooth optimization methods allows to improve the results of balanced sparse packing of rectangular parallelepipeds in an acceptable time. Numerical experiments showed effectiveness of the algorithm in practice.

Keywords

• balanced sparse packing
• multistart method
• r-algorithm
• penalty function
• "master-slave" procedure
• numerical experiments