=Paper=
{{Paper
|id=Vol-2608/paper44
|storemode=property
|title=Irregular layout problem for additive production
|pdfUrl=https://ceur-ws.org/Vol-2608/paper44.pdf
|volume=Vol-2608
|authors=Andrey Chugay,Aleksandr Pankratov,Tetyana Romanova
|dblpUrl=https://dblp.org/rec/conf/cmis/ChugayPR20
}}
==Irregular layout problem for additive production==
https://ceur-ws.org/Vol-2608/paper44.pdf
Irregular layout problem for additive production
Andrey Chugay[0000-0002-4079-5632], Aleksandr Pankratov[0000-0002-2958-8923],
Tetyana Romanova[0000-0002-8618-4917]
A. Pidgorny Institute of Mechanical Engineering Problems of the National Academy of
Sciences of Ukraine, 2/10 Pozharsky St., 61046 Kharkiv, Ukraine
chugay.andrey80@gmail.com, pankratov2001@yahoo.com,
tarom27@yahoo.com
Abstract. One of the interesting applications of optimization layout problems is
additive production. The problem of layout of 3D objects (parts) inside a
container (a working chamber of a 3D printer) to minimize the container height
is studied. It is aimed to reduce printing costs by minimizing the number of 3D-
printing layers while reducing the number of the printer starts. A mathematical
model of the layout problem is provided in the form of nonlinear programming
problem using the phi-function technique. A solution algorithm to search for
optimized layouts is proposed. Computational results demonstrate the
efficiency of our approach.
Keywords: additive production, packing, mathematical modeling, phi-function,
quasi phi-function, nonlinear optimization.
1 Introduction
Optimization 3D layout problems have a wide spectrum of real-word applications,
including transportation, logistics, chemical and aerospace engineering, shipbuilding,
robotics, additive manufacturing, materials science. In this paper the smart technique
to optimize the 3D-printing process for selective laser sintering (SLS) additive manu-
facturing [1] is developed. The SLS technology uses high power laser sintering for
small particles of plastic, ceramic, glass or metal flour in three-dimensional structure.
This technology empowers the fast, flexible, cost-efficient, and easy manufacture
of prototypes for various application of required shape and size by using powder
based material. A physical prototype is an important for design confirmation and op-
erational examination by creating the prototype unswervingly from CAD data.
The main feature of this technology is the use of powder, consisting of particles of
metal coated polymer. After the sintering process piece is placed in a high tempera-
ture kiln to burn plastic and fusible took the bronze. The advantages of the technology
include no need for material support. Parts immersed into a powder, which works on
as a support [2].
Copyright © 2020 for this paper by its authors. Use permitted under Creative
Commons License Attribution 4.0 International (CC BY 4.0).
Recently 3D-prototyping technologies are evolving rapidly. The purpose of the re-
search is development of smart technology to improve 3D-printing process for ad-
vanced additive production. We propose the approach for accelerating printing cycle
due to the simultaneous printing of several parts providing dense filling the entire
volume of the working chamber 3D printer using SLS technology.
One of the important problems arising in the process of creating new prototypes
(final products) is reducing the time and cost production. For each start of SLS printer
requires time and energy for heating and maintaining temperature. In [3] data on what
savings can be achieved by optimizing the layout of objects to be created are pro-
vided.
Our approach allows optimizing the process of 3D printing for the following fac-
tors:
- printing of several prototypes (products) providing dense filling the volume of the
3D printer working chamber [4];
- minimizing the time and cost of 3D parts production by reducing printing cycle.
In this paper the optimization layout problem of irregular 3D objects into opti-
mized cuboid is studied.
Our approach is based on the mathematical modelling of relations between irregu-
lar geometric objects by means of the phi-function technique. It allows us reducing
the layout problem to nonlinear programming model.
2 Literature review
The list of publications related to the layout problem of irregular 3D objects, taking
into account the minimum allowable distances is very scarce within the field of Pack-
ing and Cutting. Arbitrary shaped objects in most cases are approximated by sets of
cuboids or spheres. To solve the layout problems heuristic and meta-heuristic algo-
rithms are used that resulting in the loss of optimal solutions.
3D object layout problems is NP-hard. In order to find feasible solutions some
researchers use different techniques, including heuristics (based on different
approximation rules heuristics [5], genetic algorithms [6], simulated annealing
algorithms [7], artificial bee colony algorithms [8]), extended pattern search [8],
traditional optimization methods [9, 10], nonlinear mathematical programming [11].
In the majority of papers, either orientation of 3D objects is fixed or only discrete
rotations (by 45 or 90 degrees) are allowed. In particular, paper [2] uses the parallel
translation algorithm for packing convex polytopes. The authors of [12] propose the
HAPE3D algorithm which can be applied to arbitrarily shaped polyhedra that can be
rotated around each coordinate axis at eight different angles. In [13] the issue is dis-
cussed that for 3D packing problems making calculations of 0 to 360 degrees orienta-
tions of objects with respect to each axis is impossible. Analysis of irregular three-
dimensional packing problems in additive manufacturing is provided in [14]. The
paper [15 22] presents an intelligent layout planning for rapid prototyping.
Only few works consider continuous rotations of 3D objects (see, e.g. [16- 22].
3 Problem statement
In order to minimize the time of 3D parts production using SLS-technology the num-
ber of layers should be minimized. The problem of minimizing layers can be formu-
lated as a problem of layout (packing) of parts in the container of minimum height
(fig.1).
Fig. 1. Minimizing of the height of the occupied part
of the 3D printer working chamber
Let the set of irregular 3D objects Ti , i I n = {1,2,..., n}, and container
= {( x, y, z ) R3 , 0 w1 x w2 , 0 l1 y l2 , 0 h1 z h2 } be given. Here h1
and h2 are variable. Denote the container of variable sizes by (h1 , h2 ) .
Each object Ti is presented by a union of convex polyhedra
n
i
Ti = Tik , i I n ,
k =1
where Tik is defined by the collection of vertices { pik } .
Layout of Ti in R3 determined by the translation vector vi = ( xi , yi , zi ) and the
vector of rotation angles i = ( i , i , i ), i I n Thus, vector ui = (vi , i ) determines
placement of Pi in the tree-dimensional space R 3 .
Further object Ti , translated on the vector vi and rotated by angles i , i , i is
denoted by Ti (ui ) .
Optimization layout problem. Find vector u (u1 ,..., un ) that provides layout of
objects Ti (ui ), i I , inside the container (h1 , h2 ) so that the height H h2 h1
will reach the minimum value.
4 Mathematical model and its properties
Using the phi-function technique [16-22] a mathematical model of the optimization
layout problem can be presented as the following nonlinear programming problem:
min H , (1)
X W
W = { X R m : ij (ui , u j , uij ) 0, i < j I n , i (ui , h1 , h2 ) 0, i I n , h2 h1 0} , (2)
where X (h1 , h2 , u , u ) , ij (ui , u j , uij ) is the quasi phi-function for polyhedra Ti
and T j [18, 21], u (uij , i < j I n ) , uij is the vector auxiliary variables for the
quasi phi-function ij (ui , u j , uij ) , i (ui , h1 , h2 ) is the phi-function for objects Ti and
* R3 \ int .
The inequality ij (ui , u j , uij ) 0 provides non-overlapping Ti and T j and
inequality i (ui , h1 , h2 ) 0 provides containment of Ti into .
The problem (1)-(2) is an exact formulation of the optimization layout problem of
3D objects.
The feasible region W of the problem (1)-(2), in the general case, is a disconnected
set, and each of its connected components is a multiply connected.
5 Solution approach
Our solution approach is addressed to the placement of non-convex continuously
rotated objects. To construct feasible starting points the clustering algorithm is pro-
posed. Local optimization is performed using the IPOPT code combined with the
decomposition strategy. To search for local extrema, a multistart strategy is used.
Firstly we solve the problem of clustering of pairs of 3D objects into optimized
containing spheres or cuboids. Then depending on the shape of clusters auxiliary sub-
problems of packing cuboids or spheres are solved, employing the clusters homothetic
transformations. This allows constructing fast feasible starting points.
The reduction of computational costs is also facilitated by the fact that the process
of finding a local extremum of the problem is divided into two stages: solving NLP
subproblems by fixing the rotation angles and solving NLP subproblems allowing free
object rotations. In addition, the strategy of finding an approximation to the global
extremum is used.
As an approximation to the global minimum of the optimization layout problem
(1)-(2) the best local minimum found by our approach is considered.
5.1 Generation of feasible starting points
In order to generate a feasible starting point for problem (1) - (2) we use the following
algorithm. Firstly, pairs of non-overlapping objects are placed into containing regions
(cuboids or spheres) of the minimum volume. Then we solve the problem of packing
the set of the obtained clusters into the container (cuboid) of minimum height. This
algorithm returns feasible placement parameters for each polyhedron. To compute
rotation angles of each of polyhedra the following algorithm is proposed.
The set of objects Ti , i I n , is divided into k groups. Each group involves lk
identical polyhedra.
Each object Ti is contained into the sphere Si of minimum radius ri* , using the
following NLP subproblem:
ri* = min ri , i I n ,
vi , ri Di R 4
Di = vi , ri R 4 : ij ri2 ( xij' xi )2 ( yij' yi ) 2 ( zij' zi ) 2 0, j J i .
Denote a local minimum point of the subproblem by (vi* , ri* ) . Then each object Ti
is translated by the vector vi* .
Further Сn2 n subproblems of packing the objects Ti , i I n , into cuboid ij of
minimum volume DijC are solved:
ri* = min Dijc (h1 , h2 ), (3)
(ui ,u j ,h1 ,h2 )Wij R18
Wij = {(ui , u j , h1 , h2 ) R18 : ij (ui , u j ) 0, i (ui , h1 , h2 ) 0,
(4)
j (u j , h1 , h2 ) 0, F (h1 , h2 ) 0}
where i j I n ,
Dijc (h1 , h2 ) = (h2 h1 )( w2 w1 )(l2 l1 ) , F (h1 , h2 ) = min{h2 h1 , w2 w1 , l2 l1} .
The inequality ij (ui , u j ) 0 implies that int Ti int T j = , while the inequali-
ties i (ui , h1 , h2 ) 0 and j (u j , h1 , h2 ) 0 guarantee the arrangement of Ti and T j
fully inside containing region ij .
Next we solve the layout problem of subset of clusters Qi , i M , inside the cu-
boid of minimum height.
Now the problem (1)-(2) is reduced to the following NLP model:
min~ H (h1 , h2 ), (5)
(u~ ,h1 ,h2 )W R 6 6
W = {(u , h1 , h2 ) R 6 6 : ij (ui , u j ) 0, i j M , i (ui , h1 , h2 ) 0,
(6)
i M , h2 h1 0},
where H(h1 , h2 )= h2 - h1 .
Let the point (u* , h1* , h2* ) R 6 6 be an approximation to the global minimum point
of the problem (5) - (6). The point corresponds to packing clusters Qi (ui* ), i M
into cuboid (h1* , h2* ) . Each cluster Qi . contains the pair of polyhedra Tk and Tt
i i
with placement parameters ukQ and utQ in the local coordinate system of the cluster
i i
Qi .
In order to construct a feasible point (u 0 , h10 , h20 ) W of the problem (1) - (2) re-
garding the arrangement of clusters Qi , i M , we set the arrangement of object Ti
using the equation vi0 vi* viQ for i I n .
To define the rotation angles i0 of polyhedra Ti , i I n , we solve the sequence of
n subproblems of the following form:
r13i* min r13i , (7)
Ri Di R9
Di = {Ri R9 : V1i R i V1i , V2i Ri V2i , V3i Ri V3i , rij rik jk ,
i
(8)
rji rki jk , i 1, 2,3}
i
where V1i , V2i , V3i are vectors of initial coordinates of the first three vertices of the
polyhedron Pi , V ji Ri* ( RiQV ji viQ ) , j 1, 2,3, Ri is the rotation matrix, i I n . Let
ri* be a solution of the problem (7) - (8). Then the angles of Ti can be derived in the
form: i arcsin r13i* i*
i arcsin(r23 / cos i ) , i arccos( r12i* / cos i ) .
5.2 Local optimization
To find a local extremum of the problem (1)-(2) the following algorithm is used. This
algorithm allows reducing CPU.
The feasible region of the problem (1)-(2) can be always represented by a union of
subregions (see e.g. [21]). It enables to search for a local minimum of the problem
(1)-(2) by solving a collection of NLP subproblems with a considerably smaller num-
ber of inequalities.
The key idea of the proposed algorithm is based on the decomposition strategy
(see, e.g. [23]). The large scale problem (1)-(2) is reduced to a sequence of subprob-
lems of smaller dimension. The following stages are performed:
generating feasible subregions of the feasible region (2) related to the appro-
priate starting points;
forming the system of active constraints;
searching for local extrema of the subproblems generated at the first step,
employing state-of-the-art NLP-solvers;
replacing subregions.
Now we consider the algorithm in detail.
Let the point X W be a starting point. Then we select an appropriate subregion
W0 , such that X W0 W and substitute the point X in the inequality system (2).
Each quasi phi-function has the form
ij' ui , u j , u max ijs ui , u j , u , s 1, ,ij .
a
Then we select one of the functions ijij ui , u j , u , aij 1, ,ij , i j I ,
such that
a
ij' ui , u j , u ijij ui , u j , u ij .
Similarly we choose i ui , u 0, i I . It results in the system of inequalities
0 X 0 describing the subregion W0 . Then the subproblem
F u0* = min
X W0 R
F u
is solved. The inequality system 0 X 0* 0 distinguishes the active inequality
j 0 0*
j 0, j 0 {1,..., 0 } {1,..., } . Denote the subsystem by
ija (ui , u j ) 0, i I 01 I , j I 02 I . This allows choosing quasi phi-functions
ij' ui , u j , u that involve functions ija (ui , u j ), for i I 01 , j I 02 .
Then we calculate the values of the functions at the point X 0* .
Let
ij' ui0 , u 0j ijс (ui0 , u 0j ) 0ij , i I 01 , j I 02 .
If ij0 0, i I 01 , j I 02 then replace subsystems ija (ui , u j ) 0 by systems
сij (ui , u j ) 0 , i I 01 , j I 02 . Thus a new subsystem of inequalities defining a
new subregion W1 W is generated. Obviously, X 0 W1.
Taking the starting point X 0 , we solve the problem
F u1*
= min
X W1 R m
F u ,
and search for a local minimum point X 1* .
The computational process is repeated until F u(1)* F u* .
The search for a local minimum of the problem (1) - (2) can be divided into two
stages: optimization of the system with linear constraints and nonlinear optimization.
The first stage is realized by fixing the rotation angles i0 of objects Ti , i I n at the
feasible starting point (u 0 , u0 ) W . Fixing rotation angles significantly reduces the
dimension of the problem (1) - (2) switching to the linear constraints to describe the
feasible region.
Figure 3 depicts layout of irregular 3D objects that corresponds to a) a feasible
starting point and b) the appropriate local minimum found by our algorithm.
a) b)
Fig. 1. Example of layouts of irregular objects corresponding: a) a starting point; b) a local
minimum point
6 Computation experiments
We present some examples to demonstrate the efficiency of our methodology. We
have run all experiments on an Intel I5 2320 computer, programming language C++,
Windows 10 OS. To solve NLP problems IPOPT [24] is used, which is available at an
open access software depository (https://projects.coin-or.org/Ipopt).
Figure 2 demonstrates some benchmark examples of irregular layouts obtained by
our approach.
In order to show the efficiency of our approach a number of benchmarks instances
given in [12] are tested. The results are shown in Table 1.
Fig. 2. Examples of 3D irregular object layouts
Table 1. Comparison of our results with those publised in [12]
Approach HAPE3D Our algorithm
The result of packing 20 irregular 3D objects
Volume 32550 28500
Runtime (sec) 26202 6656
The result of packing 30 irregular 3D objects
Volume 12480 10720
Runtime (sec) 9637 4789
The result of packing 36 irregular 3D objects
Volume 48300 42450
Runtime (sec) 53741 9543
The result of packing 40 irregular 3D objects
Volume 61950 56012
Runtime (sec) 99952 24543
The result of packing 50 irregular 3D objects
Volume 77280 71800
Runtime (sec) 125210 36543
7 Conclusions
The 3D-printing procedure using SLS technology takes a long time (many hours or
even days) and requires a great financial cost associated with: the printer running, the
camera heating and the temperature stabilization. Development of the optimization
techniques allowing saving time and material is of paramount importance.
The optimization problem of layout of irregular 3D objects into cuboid of mini-
mum height is formulated. The mathematical model is constructed, using the phi-
function technique. The solution strategy is proposed. To demonstrate the efficiency
of our methodology some instances are provided. Obtainment of optimized layouts of
3D objects makes possible reducing the printing cost by minimizing the number of
layers of 3D printing and therefore reducing the number of the printer starts.
Acknowledgments: The authors would like to thank anonymous referees for careful
reading the paper and constructive comments. The authors were partially supported
by the “Program for the State Priority Scientific Research and Technological (Ex-
perimental) Development of the Department of Physical and Technical Problems of
Energy of the National Academy of Sciences of Ukraine” (#6541230).
References
1. Ramya, A., Sai Vanapalli: 3D printing technologies in various applications. International
Journal of Mechanical Engineering and Technology 7(3), 396-409 (2016).
2. Egeblad, J., Nielse, B.K., Brazil, M.: Translational packing of arbitrary polytopes.
Computational Geometry 42, 269–288 (2009).
3. Baumers, M., Dickens, P., Tuck, C., Hague, R.M.: The cost of additive manufacturing:
machine productivity, economies of scale and technology-push. Technological Forecasting
& Social Change, 102, 193-201 (2016).
4. Romanova, T., Stoyan, Y., Pankratov, A., Litvinchev, I., Avramov, K., Chernobryvko, M.,
Yanchevskyi, I., Mozgova, I., Bennell, J.: Optimal layout of ellipses and its application for
additive manufacturing, International Journal of Production Research, 27 pages, (2019).
5. Verkhoturov, M., Petunin, A., Verkhoturova, G., Danilov, K., Kurennov, D.: The 3D
Object Packing Problem into a Parallelepiped Container Based on Discrete-Logical
Representation. IFAC-PapersOnLine 49(12), 1-5 (2016).
6. Karabulut, K., İnceoğlu, M.: A Hybrid Genetic Algorithm for Packing in 3D with Deepest
Bottom Left with Fill Method. Advances in Information Systems 3261, 441-450 (2004).
7. Cao, P., Fan, Z., Gao, R., Tang, J.: Complex Housing: Modeling and Optimization Using
an Improved Multi-Objective Simulated Annealing Algorithm. Proceedings of the ASME,
60563, V02BT03A034 (2016).
8. Guangqiang, L., Fengqiang, Z., Rubo, Z., Du, Jialu, Du., Chen, G.,Yiran, Z.: A Parallel
Particle Bee Colony Algorithm Approach to Layout Optimization. Journal of
Computational and Theoretical Nanoscience 13(7), 4151-4157 (2016).
9. Torczon, V., Trosset, M.: From evolutionary operation to parallel direct search: Pattern
search algorithms for numerical optimization. Computing Science and Statistics 29, 396-
401 (1998).
10. Birgin, E.G., Lobato, R.D., Martіnez, J.M.: Packing ellipsoids by nonlinear optimization.
Journal of Global Optimization 65, 709-743 (2016).
11. Fasano, G.: A global optimization point of view to handle non-standard object packing
problems. Journal of Global Optimization 55(2), 279 –299 (2013).
12. Liu, X., Liu, J., Cao, A., Yao, Z.: HAPE3D - a new constructive algorithm for the 3D
irregular packing problem. Frontiers of Information Technology & Electronic Engineering
16(5), 380-390 (2015).
13. Youn-Kyoung, Joung, Sang Do Noh.: Intelligent 3D packing using a grouping algorithm
for automotive container engineering. Journal of Computational Design and Engineering
1(2), 140-151 (2014).
14. Araújo, L. J. P., Özcan, E., Atkin, J. A. D., & Baumers, M. (2019). Analysis of irregular
three-dimensional packing problems in additive manufacturing: a new taxonomy and
dataset. International Journal of Production Research, 57(18), 5920–5934.
15. Gogate, A. S., & Pande, S. S. (2008). Intelligent layout planning for rapid prototyping.
International Journal of Production Research, 46(20), 5607–5631.
16. Stoyan, Y.G., Chugay, A.M.: Packing different cuboids with rotations and spheres into a
cuboid. Advances in Decision Sciences. Available at
https://www.hindawi.com/journals/ads/2014/571743 (2014).
17. Stoyan, Y.G., Semkin, V.V., Chugay, A.M.: Modeling Close Packing of 3D Objects.
Cybernetics and Systems Analysis 52 (2), 296-304 (2016).
18. Stoyan, Y.G., Chugay, A.M.: Mathematical modeling of the interaction of non-oriented
convex polytopes. Cybernetic and Systems Analysis 48, 837-845 (2012).
19. Grebennik, I.V., Pankratov, A.V., Chugay, A.M., Baranov, A.V.: Packing n-dimensional
parallelepipeds with the feasibility of changing their orthogonal orientation in an n-
dimensional parallelepiped. Cybernetics and Systems Analysis 46(5), 793-802 (2010).
20. Stoyan, Y., Pankratov, A., Romanova, T., Fasano, G., Pintér, J.D., Stoian, Y.E., Chugay,
A.: Optimized Packings in Space Engineering Applications, Springer Optimization and Its
Applications, 144, 478 (2019).
21. Romanova, T., Bennell, J., Stoyan, Y., Pankratov, A.: Packing of concave polyhedra with
continuous rotations using nonlinear optimisation, European Journal of Operational
Research, 268 (1), 37-53, (2018).
22. Kovalenko, A.A., Romanova, T.E., & Stetsyuk, P.I. (2015). Balance Layout Problem for
3D-Objects: Mathematical Model and Solution Methods. Cybernetics and Systems
Analysis, 51(4), 556–565.
23. Romanova, T., Stoyan, Y., Pankratov, A., Litvinchev, I., Marmolejo, J.A.: Decomposition
Algorithm for Irregular Placement Problems. In: Vasant P., Zelinka I., Weber GW. (eds)
Intelligent Computing and Optimization. Advances in Intelligent Systems and Computing,
1072, 214-221 (2019).
24. Wachter, A., Biegler, L.T.: On the implementation of an interior-point filter line-search
algorithm for large-scale nonlinear programming. Math. Program. 106 (1), 25-57 (2006).