# Optimal Design of Rotary Transfer Machines with Turrets

Olga Battaïa, Alexandre Dolgui, Nikolay Guschinsky, Genrikh Levin

► To cite this version:

Olga Battaïa, Alexandre Dolgui, Nikolay Guschinsky, Genrikh Levin. Optimal Design of Rotary Transfer Machines with Turrets. 14th IFAC Symposium on Information Control Problems in Manufacturing (INCOM12), May 2012, Bucharest, Romania. pp.407-412, 10.3182/20120523-3-RO-2023.00416 . hal-00681257

HAL Id: hal-00681257

https://hal.science/hal-00681257v1

Submitted on 9 Jun 2021

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
Optimal Design of Rotary Transfer Machines
with Turrets

Olga Battaia *, Alexandre Dolgui *
Nikolai Guschinsky**, Genrikh Levin**

* LIMOS UMR CNRS 6158, Ecole des Mines de Saint Etienne
Saint Etienne, France (e-mail: { dolgui, battaia } @emse.fr)

** Operatoireal Research Laboratory, United Institute of Informatics Problems,
Belarus, Minsk (e-mail: {gyshin, levin}@newman.bas-net.by )

**Abstract:** A problem of design of rotary transfer machines with turrets is considered. Operations are partitioned into groups which are performed by spindle heads or by turrets. Constraints related to the design of spindle heads, turrets, and working positions, as well as precedence constraints related to operations, are given. The problem consists in minimizing the estimated cost of the transfer machine, while reaching a given cycle time and satisfying all constraints. The proposed method to solve the problem is based on its reduction to a constrained shortest path problem. An industrial example is presented.

**Keywords:** Computer-aided design, machining, optimization, graph theory.

# 1. INTRODUCTION

Transfer machines with rotary table are widely used in
mechanical industry (Dashenko et al., 2003; Hitomi, 1996).
Designing such machines is a very complex problem due to
manufacturing and design constraints and to the large number
of possible decisions.

This paper deals with a problem of the optimal design of a
transfer machine with rotary table (see Fig.1). In this type of
machine a part is machined sequentially on *m* working
positions by multi-spindle heads or turrets. At the *k*-th
working position, a subset *N*<sub>*k*</sub>, *k*=1,...,*m* of operations of the
given set *N* of all operations is performed. One additional
position is usually used for loading and unloading the parts.

Each set N_k is uniquely partitioned into n_k (n_k ≤ 2) subsets (N_{kj}, j=1,...,n_k) of operations which correspond to different sides of the part and are executed in parallel. In turn, a subset N_{kj} are divided into b_{kj} blocks (N_{kjl}, l=1,...,b_{kj}) of operations. Several blocks are executed sequentially by turret or one block is performed by spindle head. We consider the rotary transfer machine with vertical and horizontal spindle heads or turrets. In such a machine there is only one vertical spindle head common for all working positions or one turret mounted at one position. There are several horizontal spindle heads or turrets. However, there is only one horizontal spindle head or turret per position. The rotary transfer machine (Fig. 1) has one vertical spindle head common for position 1,3,4,5, two horizontal turrets on position 1 and 3, and one horizontal spindle head on position 4.

At the preliminary design stage, the following decisions must
be made: the partitioning of the given set of operations into
positions and blocks and the choice of cutting modes for each
spindle head and turret.

In this paper, we focus on mathematical aspects of the
preliminary design stage. Similar design problems for
transfer machines with spindle heads are considered in
(Dolgui et al., 2003; 2005; 2008, 2008a, 2008b, 2008c,
2009a, 2009b). Close problems of assembly line balancing
are discussed in (Baybars, 1986; Ghosh and Gadnon, 1989;
Erel and Sarin, 1998, Scholl and Klein, 1998; Scholl, 1999;
Rekiek et al., 2002; Dolgui and Proth, 2010). Problems of
designing assembly lines with equipment selection are
investigated in (Bard and Feo, 1991; Askin and Zhou, 1998;
Bukchin and Tzur, 2000). Process planning problems are
considered in (Halevi, 2003).

<figure><img src="image_2.png" /><figcaption>Fig. 1. A rotary transfer machine with turrets.</figcaption></figure>
The paper is organized as follows. Section 2 presents the statement of the problem. Section 3 deals with our optimization method. An industrial example is presented in Section 4, and concluding remarks are given in Section 5.

## 2. PROBLEM STATEMENT

It is assumed that cutting modes (the feed per revolution and the cutting speed) for each operation are uniquely defined by the accepted feed per minute of the corresponding spindle head or turret. On the other hand, the execution time of a block of operations is defined by the length of its working stroke and its feed per minute. Both parameters depend on executed operations and their feasible cutting modes.

If the ranges $[s_1(p), s_2(p)]$ and $[\delta_1(p), \delta_2(p)]$ of feasible values of feeds per revolution and spindle speeds are known, and if each operation $p \in \mathbb{N}$ is performed by a separate tool, then

$$X(\mathbb{N}) = [X(N), X(N)]$$

is the set of feasible values of feeds per minute for the block $\mathbb{N}$ of operations, where:

$$X(N) = \max \{ x_1(p) \mid p \in \mathbb{N} \},$$

$$X(N) = \min \{ x_2(p) \mid p \in \mathbb{N} \},$$

$$x_r(p) = s_r(p) \delta(p), r=1,2.$$

For a fixed value of the feed per minute $x \in X(N)$ and any $p \in \mathbb{N}$, the feed per revolution is equal to

$$s(p,x) = \min [s_2(p), x/\delta_1(p)]$$

and the spindle speed is equal to $\delta(p,x) = x/s(p,x)$.

Let $P=<P_1,...,P_k,...,P_m>$ is a design decision with $P_k=(P_{k1}, ..., P_{k1}b_{k1}, P_{k2}, ..., P_{k2}b_{k2})$ and $P_{kl} = (N_{kjl}, X_{kjl})$. The execution time $t^b(N_{kjl},X_{kjl})$ of the set $N_{kjl}$ of operations with the feed per minute $X_{kjl}$ is equal to

$$t^b(N_{kjl},X_{kjl})=L(N_{kjl})/X_{kjl} + \tau^b,$$

where $L(N_{kjl}) = \max\{\lambda(p) \mid p \in N_{kjl}\}$, $\lambda(p)$ is the given length of the working stroke for operation $p \in \mathbb{N}$, and $\tau^b$ is an additional time for advance and disengagement of tools.

The execution time of all the sets $N_{kjl}$ of operations, $l=1,2,...,b_{kj}$, at the k-th working position ($k=1,...,m$) is equal

$$\text{to} \quad t^p(P_k) = \tau^p + \max\{\tau^g(b_{kj}-1) + \sum_{l=1}^{b_{kj}} t^b(N_{kjl},X_{kjl}) \mid j=1,...,n_k\},$$

where $\tau^g$ and $\tau^p$ are additional times for turret rotation and table rotation.

Then the cycle time for design decision $P$ is defined as follows:

$$T(P) = \max \{t^p(P_k) \mid k=1,...,m\}.$$

We assume that the given productivity is provided, if the cycle time $T(P)$ does not exceed the maximum value $T_0$ of the cycle time.

A number of known technological factors (such as fixed sequences of operations for machining part elements, the presence of roughing, semi-finishing and finishing operations, etc.) determines an order relation on the set $\mathbb{N}$, which defines possible sequences of operations. These precedence constraints can be specified by a directed graph $G^{OR}=(\mathbb{N},D^{OR})$ where an arc $(p,q) \in D^{OR}$ if and only if the operation $p$ has to be executed before the operation $q$. Let $Pred(p)$ be the set of immediate predecessors of the operation $p$ in the graph $G^{OR}$.

The required precision (tolerance) of mutual disposition of machined part elements as well as a number of additional factors imply the necessity to perform some pairs of operations from $\mathbb{N}$ at the same working position, by the same turret or even by the same spindle head for each pair. Such inclusion constraints can be given by undirected graphs $G^{SB}=(\mathbb{N},E^{SB})$, $G^{ST}=(\mathbb{N},E^{ST})$, and $G^{SP}=(\mathbb{N},E^{SP})$ where the edge $(p,q) \in E^{SB}$, $(p,q) \in E^{ST}$, $(p,q) \in E^{SP}$ if and only if the operations $p$ and $q$ must be executed in the same block (turret, position).

At the same time, the possibility to perform operations from $\mathbb{N}$ at the same working position or by the same spindle head is also defined by a number of constructional and technological constraints, for instance, mutual influence of combining operations, possibility of tool location in spindle head, turret, etc. These exclusion constraints can also be defined by undirected graphs $G^{DB}=(\mathbb{N},E^{DB})$, $G^{DT}=(\mathbb{N},E^{DT})$, and $G^{DP}=(\mathbb{N},E^{DP})$ where the edge $(p,q) \in E^{DB}$, $(p,q) \in E^{DT}$, $(p,q) \in E^{DP}$) if and only if the operations $p$ and $q$ cannot be executed in the same block (turret, position).

The studied problem is to determine:

a) the number $m$ of working positions;

b) the partitioning of the given set $\mathbb{N}$ of operations into subsets $N_{kjl}, k=1,...,m, j=1,...,n_k, l=1,...,b_{kj}$;

c) the feed per minute $X_{kjl}$ for each block $N_{kjl}, l=1,...,n_k$.

Let $C_1, C_2, C_3$, and $C_4$ be the relative costs for one working position, one turret, one block of a turret, and one block of a spindle head, respectively. Then the cost of equipment $C(N_{kj})$ for execution of set of operations $N_{kj}$ can be estimated as

$$C(N_{kj}) = \text{sign}(b_{kj} - 1)(C_2 + C_3b_{kj}) + (1 - \text{sign}(b_{kj} - 1))C_4$$

where $\text{sign}(x)=1$ if $x > 0$ and 0 otherwise.

Later we assume also that subsets $N_{k1}$ and $N_{k2}$ correspond to operations for machining of horizontal and lateral sides of a part, respectively, and $\mathbb{N}^1$ is set of operations for machining of the horizontal side of a part.

Therefore, the mathematical model of the considered design problem can be formulated as follows:

$$\text{Min } Q(P) = C_1 m + \sum_{k=1}^{m} \sum_{j=1}^{n_k} C(N_{kj}) \quad (1)$$
subject to:

$$T(P) \leq T_0; \quad (2)$$

$$\bigcup_{k=1}^{m} \bigcup_{j=1}^{n_k} \bigcup_{l=1}^{b_{kj}} N_{kjl} = \mathbf{N} \quad (3)$$

$$\begin{gathered} N_{k'j'q'} \cap N_{k''j''q''} = \emptyset; k', k'' = 1, \dots, m; j', j'' = 1, \dots, n_k; \\ l', l'' = 1, \dots, b_{kj}; j' \neq j'' \end{gathered} \quad (4)$$

$$\bigcup_{l=1}^{b_{kj}} \bigcup_{p \in N_{kjl}} \mathrm{Pred}(p) \subseteq \bigcup_{k'=1}^{k-1} \bigcup_{j'=1}^{b_{k'j}} \bigcup_{l'=1}^{b_{kj'}} N_{k'j'l'} \cup \bigcup_{j'=1}^{j-1} \bigcup_{l'=1}^{b_{kj'}} N_{kj'l'}; \\ k=1, \dots, m; j=1, \dots, n_k \quad (5)$$

$$| \bigcup_{j=1}^{n_k} \bigcup_{l=1}^{b_{kj}} N_{kjl} \cap \{p,q\} | \neq 1, (p,q) \in E^{SP}; k=1, \dots, m; \quad (6)$$

$$| \bigcup_{l=1}^{b_{kj}} N_{kjl} \cap \{p,q\} | \neq 1, (p,q) \in E^{ST}, k=1, \dots, m, j=1, \dots, n_k \quad (7)$$

$$| \bigcup_{l=1}^{b_{kj}} N_{kjl} \cap \{p,q\} | \neq 1, (p,q) \in E^{ST}, k=1, \dots, m, j=1, \dots, n_k \quad (8)$$

$$\begin{gathered} |N_{kjl} \cap \{p,q\}| \neq 1, (p,q) \in E^{SB}; k=1, \dots, m; j=1, \dots, n_k; \\ l=1, \dots, b_{kj} \end{gathered} \quad (9)$$

$$| \bigcup_{j=1}^{n_k} \bigcup_{l=1}^{b_{kj}} N_{kjl} \cap \{p,q\} | \neq 2, (p,q) \in E^{DP}; k=1, \dots, m \quad (10)$$

$$\begin{gathered} | \bigcup_{l=1}^{b_{kj}} N_{kjl} \cap \{p,q\} | \neq 2, (p,q) \in E^{DT}; k=1, \dots, m; j=1, \dots, n_k \quad (11) \\ N_{kjl} \cap \{p,q\} | \neq 2, (p,q) \in E^{DB}; k=1, \dots, m; j=1, \dots, n_k; \\ l=1, \dots, b_{kj} \end{gathered}$$

$$\sum_{k=1}^{m} \mathrm{sign}(b_{k1} - 1) \leq 1; (b_{k1} \leq 1) \lor (\mathrm{sign}(b_{k1} - 1)b_{k2}); k=1, \dots, m \quad (13)$$

$$X_{kjl} \in \mathbf{X}(N_{kjl}); k=1, \dots, m; j=1, \dots, n_k; l=1, \dots, b_{kj} \quad (14)$$

$$n_k \leq 2; b_{kj} \leq b_0 \quad (15)$$

$$m \leq m_0. \quad (16)$$

The objective function (1) is the equipment cost; constraint (2) provides the required productivity rate; constraints (3-4) ensure the assignment of all the operations from N to one working position exactly; (5)-(12) provide precedence constraints, inclusion and exclusion constraints for blocks, turrets, and working positions; (13) ensure that at most one vertical turret will be designed; (14) choose feasible values of the feed per minute for each block of operations; (15-16) are the constraints on the number of turrets and spindle heads, on the number of blocks in one turret, and on the number of working positions; $m_0$ and $b_0$ are the maximal number of

working positions and the number of blocks in one turret, respectively.

### 3. SOLUTION METHOD

It is easy to see that $P = \langle (N_{111}, X_{111}), \dots, (N_{11b_{11}}, X_{11b_{11}}), (N_{121}, X_{121}), \dots, (N_{12b_{12}}, X_{12b_{12}}), \dots, (N_{m11}, X_{m11}), \dots, (N_{m1b_{m1}}, X_{m1b_{m1}}), (N_{m21}, X_{m21}), \dots, (N_{m2b_{m2}}, X_{m2b_{m2}}) \rangle$ is a solution of the problem (1) – (16) iff $P' = \langle (N_{111}, X(N_{111})), \dots, (N_{11b_{11}}, X(N_{11b_{11}})), \dots, (N_{121}, X(N_{121})), \dots, (N_{12b_{12}}, X(N_{12b_{12}})), \dots, (N_{m11}, X(N_{m11})), \dots, (N_{m1b_{m1}}, X(N_{m1b_{m1}})), \dots, (N_{m21}, X(N_{m21})), \dots, (N_{m2b_{m2}}, X(N_{m2b_{m2}})) \rangle$ satisfies (1)-(16).

Therefore, the optimization problem (1)-(16) may be reduced to a problem of finding a partition of N into subsets $N_{kjl}$, $k=1, \dots, m, j=1, \dots, n_k, l=1, \dots, b_{kj}$, such that

* $C_1 m + \sum_{k=1}^{m} \sum_{j=1}^{n_k} C(N_{kj})$ is small as possible,

* constraints (3) – (16) are not violated and

* $t(N_k) \leq T_0$

where $t(N_k) = \tau^p + \max\{(b_{kj} - 1) \tau^g + \sum_{l=1}^{b_{kj}} t^b(N_{kjl}, X(N_{kjl}))| j=1, \dots, n_k\}$.

In turn, such a problem may be transformed into the problem of finding a shortest constrained path in the following digraph.

Let **P** be a set of collections $P = \langle N_1, \dots, N_k, \dots, N_m \rangle$, satisfying the constraints (3)-(15). The set $v_k = \bigcup_{r=1}^{k} N_r$ can be considered as a state of the part after machining it at k-th working position. Let **V** be the set of all states of part for all $P \in \mathbf{P}$, including also the states $v_0 = \emptyset$ and $v_N = \mathbf{N}$.

An arc $(v', v'')$ is included into a digraph $G=(V, D)$ if $v' \subset v''$ and the set $N'' = v'' \setminus v'$ can be partitioned into subsets $(N''_{11}, \dots, N''_{1b_1}, N''_{12}, \dots, N''_{1b_2})$ such that precedence, inclusion, and exclusion constraints are not violated as well as $t(N'') \leq T_0$.

The arc $(v', v'')$ represents the set $v'' \setminus v'$ of operations that are performed at one working position. Each arc $(v', v'')$ is assigned the cost $c(v', v'') = C(v'' \setminus v')$.

Each design decision $P \in \mathbf{P}$ can be associated with a path $z(P) = (v_0=u_0, \dots, u_{k-1}, u_k, \dots, u_m=v_N)$ in the digraph $G$ from the vertex $v_0$ to the vertex $v_N$ where $u_k = \bigcup_{r=1}^{k} N_r$.
Let $\mathbf{Z}$ be the set of all paths in $\mathcal{G}$ from $v_0$ to $v_N$. Then the path $z \in \mathbf{Z}$ defines a decision $P(z)=(u_1\dots u_0, \dots, u_j\dots u_{j-1}, \dots, u_{m(z)}\dots u_{m(z)-1})$ satisfying constraints (2)-(15) but maybe does not respect constraint (16).

Let us consider the following constrained shortest path problem:

$$ \text{Min } Q(z) = \sum_{k=1}^{m(z)} C(u_k \setminus u_{k-1}); \qquad (17) $$

$$ z \in \mathbf{Z}; \qquad (18) $$

$$ m(z) \le m_0. \qquad (19) $$

The following algorithm simultaneously generates the digraph $\mathcal{G}$ and solves the problem (17)-(19). Vertices from $V$ can be easily enumerated in the non-decreasing order of their rank in $\mathcal{G}$. In order to do this, we simply partite $V$ into $V_i$ in such a way that $v \in V_i$ if $|V_i| = i$, $i=0, 1, \dots, |N|$.

In this algorithm, $Cost_j(v)$ corresponds to a path with the minimal cost in digraph $\mathcal{G}$ from the vertex $v_0$ to the vertex $v$, which consists exactly of $j$ arcs. Using $Pred_j(v)$, such a path can be easily found in digraph $\mathcal{G}$. Since only one vertical turret is allowable it can be designed beforehand. To partite the set $N^1$ we can use methods (Dolgui et al, 2008a).

**Algorithm 1.**

Step 0. Let $V_0 \leftarrow \{\emptyset\}$, $V_i \leftarrow \emptyset$, $i=1, \dots, N$, $Cost_1(v_0)=0$, $Cost_k(v_0) \leftarrow \infty$, $k=2, \dots, m_0$.

Step 1. For $i=0, \dots, |N|-1$ 
**For** each $v \in V_i$ such that 
$\min\{Cost_k(v)|k=1, \dots, m_0\} < \infty$ repeat Steps 2 and 3.

Step 2. By Algorithm 2 generate the set $D(v)$ of arcs whose origin is the vertex $v$. Include into $D(v)$ the arc $N^1$ if $c(N^1) < \infty$ and all the predecessors of $N^1$ are in $v \cup N^1$.

Step 3. **For** each arc $d \in D(v)$:

a) let $w \leftarrow v \cup d$;

b) **if** $w \notin V_{|w|}$ **then** add $w$ to $V_{|w|}$ and let $Cost_r(w) \leftarrow \infty$, $r=1, \dots, m_0$;

c) **if** $v = v_0$ **then** let $Cost_1(w) \leftarrow c(d)$, $Pred_1(w) \leftarrow v_0$,

**else**

for all $k=1, \dots, m_0-1$ such that $Cost_k(w) < \infty$, :

**if** $Cost_k(v)+C(d)<Cost_{k+1}(w)$ **then** let

$$ Cost_{k+1}(w) \leftarrow Cost_k(v)+c(d), $$

$$ Pred_{k+1}(w) \leftarrow v. $$

**endif**

**endfor**

**endif**

Step 4. **If** $V_N$ is empty **then** there is no a feasible solution **else** set $\min\{Q(z)|z \in \mathbf{Z}\} \leftarrow \min\{Cost_k(v_N)|k=1, \dots, m_0\}$.

Let $J(v)$ be the set of operations that can be performed at one working position after the state $v$ of the part taking into account the precedence constraints. The set $J(v)$ can be

partitioned into subsets $J_i(v)$, $i=1, \dots, I(v)$ of operations that must be executed in the same working position (subsets $J_i(v)$ can consist of one operation only). The following algorithm generates the set $D(v)$ of digraph $\mathcal{G}$. In this algorithm, $last(d)$ indicates the greatest index of subset $J_i(v)$ including in $d$.

**Algorithm 2.**

Step 1. Construct $J(v)$ and partite $J(v)$ into subsets $J_i(v)$, $i=1, \dots, I(v)$. Let $D(v) \leftarrow \emptyset$.

Step 2. **For** $i=1, \dots, I(v)$ let $d \leftarrow J_i(v)$, $last(d) \leftarrow i$, and compute $c(d)$ by Algorithm 3. Add $d$ to $D(v)$ if $c(d) < \infty$ and stop otherwise.

Step 3. **For** each $d \in D(v)$:

**For** $k=last(d)+1, \dots, I(v)$:

let $d' \leftarrow d \cup J_k(v)$, $last(d') \leftarrow k$ and compute $c(d)$

by Algorithm 3;

**if** $c(d') < \infty$ **then** add $d'$ to $D(v)$.

Step 4. Exclude dominated arcs from $D(v)$.

**Algorithm 3.**

Step 1. Let $c(d)=C_1$, $d^1=d \cap N^1$ and $d^2=d \setminus d^1$.

Step 2. **If** $d^1=\emptyset$ **then** go to Step 3. Let $c(d) = \infty$ **if** the set $d^1$ of operations cannot be performed in one block **else** let $c(d) = c(d)+C_4$.

Step 3. Using methods (Dolgui et al, 2008a) partite the set $d^2$ of operations in the minimal number $b_{k2}$ of blocks such that $t(d^2) \le T_0$. **If** $b_{k2}=1$ **then** let $c(d) = c(d) + C_4$ **else** **if** $b_{k2} \le b_0$ **then** let $c(d) = c(d) + C_2 + C_3$ **else** let $c(d) = \infty$.

Several dominance rules can be applied for elements from $D(v)$.

**Rule 1.** An arc $d'$ dominates an arc $d$ if $d \subset d'$ and $c(d') = c(d)$.

**Rule 2.** An arc $d'$ dominates an arc $d$ if $d \subset d'$, $c(d') = c(d)$, and $t(d') = t(d)$.

Using values $Cost_k(v)$, $k=1, \dots, m_0$, we can restore all the optimal paths in digraph $\mathcal{G}$ and evaluate them by means of other criteria.

Values of $X_{kjl}$ can be defined in such a way that

$$ \sum_{l=1}^{b_{kjl}} L(N_{kjl}) / X_{kjl} \le T_{kjl} $$

where $T_{kjl} = T_0 - \tau^p - (b_{kjl} - 1) \tau^g - b_{kjl} \tau^b$.

If „recommended“ values $x_0(p)$ of feed per minute are known for each operation $p \in N$ then $X_{kjl}$ may be chosen as

$$ \max \left\{ \sum_{l=1}^{b_{kjl}} \sum_{p \in N_{kjl}} x_0(p) / \sum_{l=1}^{b_{kjl}} | N_{kjl} |, \sum_{l=1}^{b_{kjl}} L(N_{kjl}) / T_{kjl} \right\} $$

for $k=1, \dots, m$; $j=1, \dots, n_k$.
## 4. AN INDUSTRIAL EXAMPLE

Eight holes are machined in the part (Fig. 2). Operations for machining the holes and their parameters are given in Table 1; $T_0=3$ min; $\tau^b=\tau^g=\tau^p=0.1$ min; $m_0=6$; $b_0=4$; $C_1=10$; $C_2=5$; $C_3=2$; $C_4=3$. Precedence constraints, exclusion constraints for blocks and positions are presented in Tables 2, 3 and 4, respectively. Inclusion constraints for blocks are given in Table 5. All the constraints were generated by decision support system (Dolgui et al, 2009a).

<figure><img src="image_3.png" /><figcaption>Fig.2. The part to be machined</figcaption></figure>

<table><caption>Table 1. Operations and their parameters</caption><thead><tr><th>p</th><th>λ(p)</th><th>x<sub>1</sub>(p)</th><th>x<sub>2</sub>(p)</th><th>x<sub>0</sub>(p)</th><th>p</th><th>λ(p)</th><th>x<sub>1</sub>(p)</th><th>x<sub>2</sub>(p)</th><th>x<sub>0</sub>(p)</th></tr></thead><tbody><tr><td>1</td><td>24</td><td>26.5</td><td>86.7</td><td>56.1</td><td>13</td><td>24</td><td>24.9</td><td>86.8</td><td>57.4</td></tr><tr><td>2</td><td>11</td><td>30.3</td><td>107</td><td>70</td><td>14</td><td>9</td><td>29.7</td><td>105.7</td><td>68.4</td></tr><tr><td>3</td><td>22</td><td>29.8</td><td>107.2</td><td>68.8</td><td>15</td><td>22</td><td>29.9</td><td>265.4</td><td>57.4</td></tr><tr><td>4</td><td>22</td><td>27.8</td><td>249.5</td><td>127.5</td><td>16</td><td>24</td><td>24.9</td><td>86.8</td><td>57.4</td></tr><tr><td>5</td><td>24</td><td>26.5</td><td>86.7</td><td>56.1</td><td>17</td><td>9</td><td>29.7</td><td>105.7</td><td>68.4</td></tr><tr><td>6</td><td>11</td><td>30.3</td><td>107</td><td>70</td><td>18</td><td>22</td><td>29.9</td><td>265.4</td><td>57.4</td></tr><tr><td>7</td><td>22</td><td>29.8</td><td>107.2</td><td>68.8</td><td>19</td><td>24</td><td>24.9</td><td>86.8</td><td>57.4</td></tr><tr><td>8</td><td>22</td><td>27.8</td><td>249.5</td><td>127.5</td><td>20</td><td>9</td><td>29.7</td><td>105.7</td><td>68.4</td></tr><tr><td>9</td><td>72</td><td>22.8</td><td>81.3</td><td>52.6</td><td>21</td><td>22</td><td>29.9</td><td>265.4</td><td>57.4</td></tr><tr><td>10</td><td>70</td><td>29.7</td><td>105.7</td><td>68.4</td><td>22</td><td>24</td><td>24.9</td><td>86.8</td><td>57.4</td></tr><tr><td>11</td><td>72</td><td>22.8</td><td>81.3</td><td>52.6</td><td>23</td><td>9</td><td>29.7</td><td>105.7</td><td>68.4</td></tr><tr><td>12</td><td>70</td><td>29.7</td><td>105.7</td><td>68.4</td><td>24</td><td>22</td><td>29.9</td><td>265.4</td><td>57.4</td></tr></tbody></table>

<table><caption>Table 2. Precedence constraints</caption><thead><tr><th>Operation number</th><th>Direct predecessors</th><th>Operation number</th><th>Direct predecessors</th></tr></thead><tbody><tr><td>2</td><td>1</td><td>14</td><td>13</td></tr><tr><td>3</td><td>2</td><td>15</td><td>14</td></tr><tr><td>4</td><td>3</td><td>17</td><td>16</td></tr><tr><td>6</td><td>5</td><td>18</td><td>17</td></tr><tr><td>7</td><td>6</td><td>20</td><td>19</td></tr><tr><td>8</td><td>7</td><td>21</td><td>20</td></tr><tr><td>10</td><td>9</td><td>23</td><td>22</td></tr><tr><td>12</td><td>11</td><td>24</td><td>23</td></tr></tbody></table>

<table><caption>Table 3. Incompatibility of operations in blocks</caption><thead><tr><th>Operation number</th><th>Operations to be not in the same block</th><th>Operation number</th><th>Operations to be not in the same block</th></tr></thead><tbody><tr><td>13</td><td>1 2 3 5 6 7 9 11</td><td>19</td><td>1 2 3 5 6 7 9 11</td></tr><tr><td>14</td><td>1 2 3 4 5 6 7 8 9</td><td>20</td><td>1 2 3 4 5 6 7 8</td></tr><tr><td></td><td>10 11 12</td><td></td><td>9 10 11 12</td></tr><tr><td>15</td><td>2 3 4 6 7 8 10</td><td>21</td><td>2 3 4 6 7 8 10</td></tr><tr><td></td><td>12</td><td></td><td>12</td></tr><tr><td>16</td><td>1 2 3 5 6 7 9 11</td><td>22</td><td>1 2 3 5 6 7 9 11</td></tr><tr><td>17</td><td>1 2 3 4 5 6 7 8 9</td><td>23</td><td>1 2 3 4 5 6 7 8</td></tr><tr><td></td><td>10 11 12</td><td></td><td>9 10 11 12</td></tr><tr><td>18</td><td>2 3 4 6 7 8 10</td><td>24</td><td>2 3 4 6 7 8 10</td></tr><tr><td></td><td>12</td><td></td><td>12</td></tr></tbody></table>

<table><caption>Table 4. Incompatibility of operations in positions</caption><thead><tr><th>Operation number</th><th>Operations to be not in the same position</th><th>Operation number</th><th>Operations to be not in the same position</th></tr></thead><tbody><tr><td>4</td><td>1</td><td>16</td><td>4 8 10 12 15</td></tr><tr><td>5</td><td>4</td><td>17</td><td>15</td></tr><tr><td>6</td><td>4</td><td>18</td><td>1 5 8 9 11 13 14</td></tr><tr><td></td><td></td><td></td><td>16</td></tr><tr><td>8</td><td>1 2 5</td><td>19</td><td>4 8 10 12 15 18</td></tr><tr><td>9</td><td>4 8</td><td>20</td><td>15 18</td></tr><tr><td>10</td><td>1 5 9</td><td>21</td><td>1 5 8 9 11 13 14</td></tr><tr><td></td><td></td><td></td><td>16 17 19</td></tr><tr><td>11</td><td>4 8 10</td><td>22</td><td>4 8 10 12 15 18 21</td></tr><tr><td>12</td><td>1 5 9 11</td><td>23</td><td>15 18 21</td></tr><tr><td>13</td><td>4 8 10 12</td><td>24</td><td>1 5 8 9 11 13 14</td></tr><tr><td></td><td></td><td></td><td>16 17 19 20 22</td></tr><tr><td>15</td><td>1 3 4 5 7 8 9 11</td><td></td><td></td></tr><tr><td></td><td>13</td><td></td><td></td></tr></tbody></table>

<table><caption>Table 5. Inclusion constraints for blocks</caption><thead><tr><th>Operation number</th><th>Operations to be in the same block</th><th>Operation number</th><th>Operations to be in the same block</th></tr></thead><tbody><tr><td>1</td><td>5</td><td>10</td><td>12</td></tr><tr><td>3</td><td>7</td><td>13</td><td>16 19 12</td></tr><tr><td>9</td><td>11</td><td></td><td></td></tr></tbody></table>

<table><caption>Table 6. An optimal solution</caption><thead><tr><th>Set N<sub>kjl</sub></th><th>Operations of N<sub>kjl</sub></th><th>L(N<sub>kjl</sub>)</th><th>X<sub>kjl</sub></th><th>t<sup>b</sup>(N<sub>kjl</sub>)</th></tr></thead><tbody><tr><td>N<sub>111</sub></td><td>13 16 19 22</td><td>24</td><td>57.4</td><td>0.54</td></tr><tr><td>N<sub>121</sub></td><td>1 5 9 11</td><td>72</td><td>52.6</td><td>1.6</td></tr><tr><td>N<sub>122</sub></td><td>2 6</td><td>11</td><td>52.6</td><td>0.33</td></tr><tr><td>N<sub>123</sub></td><td>3 7</td><td>22</td><td>52.6</td><td>0.56</td></tr><tr><td>N<sub>211</sub></td><td>14 17 20 22</td><td>24</td><td>57.4</td><td>0.54</td></tr><tr><td>N<sub>221</sub></td><td>4 8 10 12</td><td>70</td><td>68.4</td><td>1.17</td></tr><tr><td>N<sub>311</sub></td><td>15 18 21 24</td><td>24</td><td>57.4</td><td>0.54</td></tr></tbody></table>

An optimal solution is presented in Table 6. The designed transfer machine has one vertical spindle head common for
position 1, 2, 3 ($N_{111}$, $N_{211}$, $N_{311}$), one horizontal turret on position 1 ($N_{121}$, $N_{122}$, $N_{123}$), and one horizontal spindle head on position 2 ($N_{221}$). In Table 7 we show the results of application of different dominance rules.

<table><caption>Table 7. Size of graph G</caption><thead><tr><th>Rule</th><th>Number of vertices</th><th>Number of arcs</th><th>Running time, sec</th></tr></thead><tbody><tr><td>Rule 1</td><td>26</td><td>55</td><td>0.078</td></tr><tr><td>Rule 2</td><td>45</td><td>124</td><td>0.172</td></tr><tr><td>-</td><td>2214</td><td>47839</td><td>23.109</td></tr></tbody></table>

In Table 8 an optimal solution is depicted if turrets are not allowable. In this case the number of working positions is equal to 5, i.e. has increased in 2 working positions in comparison with the rotary table with turrets.

<table><caption>Table 8. An optimal solution without turrets</caption><thead><tr><th>Set N<sub>kjl</sub></th><th>Operations of N<sub>kjl</sub></th><th>L(N<sub>kjl</sub>)</th><th>X<sub>kjl</sub></th><th>l<sup>b</sup>(N<sub>kjl</sub>)</th></tr></thead><tbody><tr><td>N<sub>121</sub></td><td>1 5 9 11</td><td>72</td><td>52.6</td><td>1.47</td></tr><tr><td>N<sub>221</sub></td><td>2 6 10 12</td><td>70</td><td>68.4</td><td>1.12</td></tr><tr><td>N<sub>311</sub></td><td>13 16 19 22</td><td>24</td><td>57.4</td><td>0.54</td></tr><tr><td>N<sub>321</sub></td><td>3 7</td><td>22</td><td>68.4</td><td>0.42</td></tr><tr><td>N<sub>411</sub></td><td>14 17 20 23</td><td>24</td><td>57.4</td><td>0.54</td></tr><tr><td>N<sub>421</sub></td><td>4 8</td><td>22</td><td>127.5</td><td>0.27</td></tr><tr><td>N<sub>511</sub></td><td>15 18 21 24</td><td>24</td><td>57.4</td><td>0.54</td></tr></tbody></table>

## 5. CONCLUSION

A problem of design of rotary transfer machines has been studied. The problem is to assign the manufacturing operations to positions in order to minimize the equipment cost. The initial problem has been reduced to a constrained shortest path problem. The advantage of the graph approach is to easy introduce additional constraints to the problem (1) – (16), for instance, constraints on the number of operations in one block or constraints on the total power, the total feed force in one block. These characteristics can be calculated by user's procedures.

The further research will concern the design of reconfigurable rotary transfer machines for machining different types of parts in batches.

## 6. ACKNOWLEDGEMENTS

This research was partially supported by the Region Rhone-Alps government (Project EuroLean of cluster GOSPI).

## REFERENCES

* Askin, R. G., and Zhou, M. (1998). Formation of independent flow-line cells based on operation requirements and machine capabilities. *IIE Transactions*, **30**, 319-329.

* Bard, F. and Feo, T.A. (1991). An algorithm for the manufacturing equipment selection problem. *IIE Transactions*, **23**, 83-92.

* Baybars, I. (1986). A survey of exact algorithms for the

simple line balancing problem. *Management Science*, **32**, 909-932.

* Bukchin, J., and Tzur, M. (2000). Design of flexible assembly line to minimize equipment cost. *IIE Transactions*, **32**, 585-598.

* Dashchenko A. I. (Ed) (2003). *Manufacturing Technologies for Machines of the Future 21st Century Technologies*, Springer.

* Dolgui, A., Guschinsky, N., and Levin, G. (2003). Balancing production lines composed by series of workstations with parallel operations blocks. In: *Proceedings of the 2003 IEEE International Symposium on Assembly and Task Planning*, Besançon, 2003, pp. 122-127.

* Dolgui, A., Finel, B., Vernadat, F., Guschinsky, N., and Levin, G. (2005). A heuristic approach for transfer lines balancing. *Journal of Intelligent Manufacturing*, **16**(2), 159-172.

* Dolgui, A., Guschinsky, N., Levin, G., and Proth, J.-M. (2008a). Optimisation of multi-position machines and transfer lines. *European Journal of Operations Research*, **185**, 1375-1389.

* Guschinskaya, O., Dolgui, A., Guschinsky, N., and Levin, G. (2008b). A heuristic multi-start decomposition approach for optimal design of serial machining lines. *European Journal of Operations Research*, **189**, 902-913.

* Dolgui, A., Guschinsky, N., and Levin, G. (2008c). Exact and heuristic algorithms for balancing transfer lines when a set of available spindle heads is given. *International Transactions in Operational Research*, **15**(3), 339-357.

* Dolgui, A., Guschinsky, N., and Levin, G. (2009a). A Design of DSS for Mass Production Machining Systems, *The Bulletin of the Polish Academy of Sciences - Technical Sciences*, **57**(3), 265-271.

* Dolgui, A., Guschinsky, N., and Levin, G. (2009b). Graph approach for optimal design of transfer machine with rotary table. *International Journal of Production Research*, **47**(2), 321-341.

* Dolgui, A., Proth, J.-M. (2010). *Supply Chain Engineering*, Springer.

* Erel, E. and S.C. Sarin (1998). A survey of the assembly line balancing procedures. *Production Planning and Control*, **9**(5), 414-434.

* Ghosh, S. and Gadnon, R.J. (1989). A comprehensive literature review and analysis of the design, balancing and scheduling of assembly systems. *International Journal of Production Research*, **27**, 637-670.

* Halevi, G. (2003). *Process and Operation Planning*, Kluwer.

* Hitomi, K. (1996). *Manufacturing Systems Engineering*, Taylor & Francis.

* Rekiek, B., A. Dolgui, A. Delchambre and A. Bratcu (2002). State of art of assembly lines design optimisation. *Annual Reviews in Control*, **26**(2), 163-174.

* Scholl, A. and R. Klein (1998). Balancing assembly lines effectively: a computational comparison. *European Journal of Operational Research*, **114**, 51-60.

* Scholl, A. (1999). *Balancing and sequencing of assembly lines*. Physica-Verlag, Heidelber.