Irregular layout problem for additive production

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 3Dprinting 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

-

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 manufacturing [ 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 operational 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 temperature 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 ].

Recently 3D-prototyping technologies are evolving rapidly. The purpose of the research is development of smart technology to improve 3D-printing process for advanced 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 provided.

Our approach allows optimizing the process of 3D printing for the following factors:

- 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 optimized cuboid is studied.

Our approach is based on the mathematical modelling of relations between irregular 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 Packing 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 algorithms 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 discussed that for 3D packing problems making calculations of 0 to 360 degrees orientations of objects with respect to each axis is impossible. Analysis of irregular threedimensional 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 ].

Problem statement

In order to minimize the time of 3D parts production using SLS-technology the number of layers should be minimized. The problem of minimizing layers can be formulated as a problem of layout (packing) of parts in the container of minimum height (fig.1).

Let the set of irregular 3D objects Ti , i  In = {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

ni Ti =  Tik , i  In ,

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  In Thus, vector ui = (vi , i ) determines placement of Pi in the tree-dimensional space R3.

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 , XW (1) W = {X  Rm : ij (ui , u j , uij )  0, i < j  In , i (ui , h1, h2 )  0, i  In , h2  h1  0} , (2) where X  (h1, h2 , u, u) , ij (ui , u j , uij ) is the quasi phi-function for polyhedra Ti and Tj [ 18, 21 ], u  (uij , i < j  In ) , uij is the vector auxiliary variables for the quasi phi-function ij (ui , u j ,uij ) , i (ui , h1, h2 ) is the phi-function for objects Ti and *  R3 \ int .

The inequality ij (ui , u j ,uij )  0 provides non-overlapping Ti and Tj 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 proposed. 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 subproblems 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  In , 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* = vi ,ri mDini R4 ri , i  In , is translated by the vector vi* . minimum volume DiCj are solved:

Di = vi , ri   R4 : ij  ri2  (xi'j  xi )2  ( yi'j  yi )2  (zi'j  zi )2  0, j  Ji  . Denote a local minimum point of the subproblem by (vi*, ri*) . Then each object Ti Further Сn2  n subproblems of packing the objects Ti , i  In , into cuboid ij of ri* = (ui ,u j ,h1,h2 )Wij R18 Dicj (h1, h2 ),

min Wij = {(ui , u j , h1, h2 )  R18 : ij (ui , u j )  0, i (ui , h1, h2 )  0,  j (u j , h1, h2 )  0, F (h1, h2 )  0} (3) (4) where i  j  In ,

Dicj (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 Tj =  , while the inequalities i (ui , h1, h2 )  0 and  j (u j , h1, h2 )  0 guarantee the arrangement of Ti and Tj fully inside containing region ij .

Next we solve the layout problem of subset of clusters Qi , i  M , inside the cuboid  of minimum height.

Now the problem (1)-(2) is reduced to the following NLP model:

(u~,h1,h2 m)Wi~nR6 6 H (h1, h2 ), W = {(u, h1, h2 )  R66 : ij (ui , u j )  0, i  j  M , i (ui , h1, h2 )  0, i  M , h2  h1  0}, where H(h1, h2 ) = h2 - h1 .

Let the point (u*, h1*, h2* )  R6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 (u0 , h10 , h20 ) W of the problem (1) - (2) regarding the arrangement of clusters Qi , i  M , we set the arrangement of object Ti using the equation vi0  vi*  viQ for i  In .

To define the rotation angles i0 of polyhedra Ti , i  In , we solve the sequence of n subproblems of the following form: where V1i , V2i , V3i are vectors of initial coordinates of the first three vertices of the polyhedron Pi , Vji  Ri* (RiQVji  viQ ) , j  1, 2, 3, Ri is the rotation matrix, i  In . Let ri* be a solution of the problem (7) - (8). Then the angles of Ti can be derived in the form: i  arcsin r1i3*

i  arcsin(r2i3* / cos i ) , i  arccos(r1i2* / 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 number 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 subproblems of smaller dimension. The following stages are performed:

 generating feasible subregions of the feasible region (2) related to the appropriate 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 isj ui , u j , u , s  1,,ij  .

Then we select one of the functions ijij ui , u j , u , aij 1,,ij  , i  j  I , a such that i'j ui , uj , u  ijij ui , uj , u  ij .

a

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 u0*  =

min XW0 R

F u  is solved. The inequality system 0  X 0*   0 distinguishes the active inequality  j0 0j*   0, j  0  {1,..., 0}    {1,..., } .

Denote the subsystem by iaj (ui , u j )  0, i  I01  I , j  I02  I . This allows choosing quasi phi-functions i'j ui , u j , u that involve functions iaj (ui , u j ), for i  I01 , j  I02 . Then we calculate the values of the functions at the point X 0* .

Let

'ij ui0 , u0j   iсj (ui0, u0j )  0ij , i  I01 , j  I02 .

If i0j  0, i  I01 , j  I02 then replace subsystems iaj (ui , u j )  0 by systems iсj (ui , u j )  0 , i  I01 , j  I02 . Thus a new subsystem of inequalities defining a new subregion W1  W is generated. Obviously, X 0 W . 1 Taking the starting point X 0 , we solve the problem

F u1*  =

min XW1Rm

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  In at the feasible starting point (u0 , u0 ) 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) 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.

Approach

Volume Runtime (sec)

Volume Runtime (sec)

Volume Runtime (sec)

Volume Runtime (sec)

Volume Runtime (sec) Fig. 2. Examples of 3D irregular object layouts Table 1. Comparison of our results with those publised in [12]

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 minimum height is formulated. The mathematical model is constructed, using the phifunction 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 (Experimental) 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 ndimensional 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 ).