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 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][17][18][19][20][21][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). ( , )

h h  .

Each object i T is presented by a union of convex polyhedra =1 = , ,

n i i i k n k T T i I   where ik T is defined by the collection of vertices { } ik p .

Layout of i T in 3 R determined by the translation vector = ( , , )

i i i i v

x y z and the vector of rotation angles = ( , , ),

i i i i     n i I  Thus, vector = ( , ) i i i u v  determines

placement of i P in the tree-dimensional space 3 . R Further object i T , translated on the vector i v and rotated by angles ,

i i   , i  is denoted by ( ) i i T u .

Optimization layout problem. Find vector 1 ( ,..., )

n u u u  that provides layout of objects ( ), i i T u , i I  inside the container 1 2 ( , ) h h  so that the height 2 1 H h h  

will reach the minimum value.

Mathematical model and its properties

Using the phi-function technique [16][17][18][19][20][21][22] a mathematical model of the optimization layout problem can be presented as the following nonlinear programming problem:

min

X W H  ,(1) 1 2 2 1

= { : ( , , ) 0, < , ( , , ) 0, , 0}

m ij i j ij n i i n W X R u u u i j I u h h i I h h            ,(2) where 1 2

( , , , )

X h h u u  , ( , , ) ij i j ij u u u   

is the quasi phi-function for polyhedra i T and j T [18,21], ( , < )

ij n u u i j I    

, ij u is the vector auxiliary variables for the quasi phi-function ( , , ) 2) is an exact formulation of the optimization layout problem of 3D objects.

ij i j ij u u u    , 1 2 ( , , ) i i u h h  is the phi-function for objects i T and * 3 \ R int    . The inequality ( , , ) 0 ij i j ij u u u     provides non-overlapping i T and j T and inequality 1 2 ( , , ) 0 i i u h h   provides containment of i T into  . The problem (1)-(

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.

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 , i T ,

n i I  is divided into k groups. Each group involves k l identical polyhedra.

Each object i T is contained into the sphere i S of minimum radius * i r , using the following NLP subproblem:

  , min = , * i R D r v i r r i i i   , n i I      4 2 ' 2 ' 2 ' 2 = , : ( ) ( ) ( ) 0, i i i ij i ij i ij i ij i i D v r R r x x y y z z j J            .

Denote a local minimum point of the subproblem by * * ( , )

h h D r c ij R W h h u u i ij j i   ( 3 ) 18 1 2 1 2 1 2 1 2

={( , , , ) : ( , ) 0, ( , , ) 0, ( , , ) 0, ( , ) 0}

ij i j ij i j i i j j W u u h h R u u u h h u h h F h h        ( 4 )

where

n i j I   , 1 2 2 1 2 1 2 1 ( , ) = ( )( )( ) c ij D h h h h w w l l    , 1 2 2 1 2 1 2 1 ( , ) = min{ , , } F h h h h w w l l    .

The inequality ( , ) 0

ij i j u u   implies that int int = i j T T   , while the inequali- ties 1 2 ( , , ) 0 i i u h h   and1 2

( , , ) 0

j j u h h  h h H R W h h u     ( 5 ) 6 6 1 2 1 2 2 1 = {( , , ) : ( , ) 0, , ( , , ) 0, , 0 } , ij i j i i W u h h R u u i j M u h h i M h h                (6)

where

1 2

,

2 1 H(h h ) = h -h . Let the point * * * 6 6 1 2 ( , , ) u h h R   

be an to the global minimum point of the problem ( 5) -( 6). The point corresponds to packing clusters * ( ),

i i Q u i M  into cuboid * * 1 2 ( , ) h h  . EachQ , i M 

we set the arrangement of object i T using the equation 0

* Q i i i v v v    for n i I  .

To define the rotation angles 0 i  of polyhedra , min ,

i i i i R D R r r    ( 7 ) 9 1 2 3 1 2 3 = { : , , , ,, 1,2,

3}

i i i i i i i i i i i ij ik jk i ji ki jk i D R R V R V V R V V R V r r r r i             ( 8 )

where

1 i V , 2 i V , 3 i

V are vectors of initial coordinates of the first three vertices of the polyhedron ,

i P * ( ) i Q i Q j i i j i V R R V v     , 1, 2, 3, j  i R is the rotation matrix, n i I  . Let * i

r be a solution of the problem ( 7) - (8). Then the angles of i T can be derived in the form:

* 13 arcsin i i r    * 23 arcsin( / cos ) i i i r     , * 12 arccos( / cos ) i i i r     .

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 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 0 W , such that 0 X W W    and substitute the point X  in the inequality system (2). Each quasi phi-function has the form

      ' ,, max , , , 1, ,s ij i j ij i j ij u u u u u u s         .

Then we select one of the functions

  , , ij a ij i j u u u  ,   1, , ij ij a    , i j I   , such that   ' , , ij i j u u u        , , ij a ij i j ij u u u        .

Similarly we choose   , 0,

a ij i j u u  for 1 0 , i I   2 0 j I   .

Then we calculate the values of the functions at the point 0* X . Let   ' 0 0 0 0 0 , ( , ) ,

с i j i j i j i j i j u u u u          1 0 , i I   2 0 j I   . If 0 0, ij   1 0 , i I   2 0 j I  

then replace subsystems ( , ) 0

a ij i j u u   by systems ( , ) 0 с ij i j u u   , 1 0 , i I   2 0 j I   . Thus a new subsystem of inequalities defining a new subregion 1 W W  is generated. Obviously, 0 1 . X W  

Taking the starting point 0 X  , we solve the problem

    1 1* = min , m X W R F u F u    

and search for a local minimum point 1* X .

The computational process is repeated until

    ( 1)* * F u 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 0 i  of objects ,

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.

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 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.