# An Improved Computer-Aided Process Planning Method Considering Production Scheduling

Eiji Morinaga, Nattapoom Charoenlarpkul, Hidefumi Wakamatsu, Eiji Arai

► To cite this version:

Eiji Morinaga, Nattapoom Charoenlarpkul, Hidefumi Wakamatsu, Eiji Arai. An Improved Computer-Aided Process Planning Method Considering Production Scheduling. IFIP International Conference on Advances in Production Management Systems (APMS), Sep 2016, Iguassu Falls, Brazil. pp.178-186, 10.1007/978-3-319-51133-7_22. hal-01615705

HAL Id: hal-01615705

https://inria.hal.science/hal-01615705

Submitted on 12 Oct 2017

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>
# An Improved Computer-Aided Process Planning Method Considering Production Scheduling

Eiji Morinaga¹, Nattapoom Charoenlarpkul¹, Hidefumi Wakamatsu¹, Eiji Arai¹

¹ Graduate School of Engineering, Osaka University
{morinaga,c.nattapoom,wakamatu,arai}@mapse.eng.osaka-u.ac.jp

**Abstract.** Process planning is essential for achieving a sophisticated manufacturing system, and computer-aided process planning (CAPP) have been discussed. Considering recent requirements for realizing agile manufacturing, a set of flexible CAPP methods have been developed, in which process planning for one product using one machine is dealt with. In actual manufacturing, multiple workpieces are usually machined with multiple machine tools in the same period, and pursuing optimality for each product independently may result in poor productivity. For this reason, integration of process planning and production scheduling was performed by formulating the integrated problem as a 0-1 integer programming problem. However, this formulation involves huge computational load. This paper provides an improved method where the integrated problem is formulated as a mixed integer programming problem.

## 1 Introduction

In order to convert product design data into a real product, it is necessary to perform process planning, that is, to select manufacturing processes and determine the sequence in which they are carried out. Because it plays an important role as a bridge between product design and manufacturing, numerous works on computer-aided process planning (CAPP) have been actively conducted [1].

Recent diversified and changeable customers' needs have increased a need to realize agile manufacturing [2] that is capable of immediately adapting to changes in the manufacturing situation, and flexibility has been a keyword in recent manufacturing. This need is also being addressed in research related to CAPP [3]. This research aimed at developing autonomous machine tools that require no NC programming and can flexibly adapt to changes in the manufacturing situation, and a flexible process planning method for rough milling was proposed. This method consists of four main steps—(i) decomposing the total removal volume (TRV) through the application of decomposition rules to transform it into sets of machining primitive shapes (MPSs), (ii) converting each of the MPS sets to a set of machining features (MFs) by determining a machining sequence for each set of MPSs and recognizing each MPS as an MF, (iii) executing rough operation planning by applying a tool selection rule and a case-based reasoning system for cutting condition decisions, and (iv) extracting the optimal set of MFs to achieve the shortest machining time with information on the machining
sequence and the utilized tools as the optimal process plan. With this method, process plans are generated and then the optimal plan is selected. Therefore, when the manufacturing situation changes, it is possible to quickly provide a new optimal plan by executing steps (iii) and (iv). Several enhancements have been made to this method for enabling extraction of a better set of MFs [4], for taking multi-axis milling into account and reducing computational complexity [5], and for improving computational efficiency [6].

These methods deal with process planning to create one product using one milling machine. In actual manufacturing, multiple workpieces are usually machined with multiple machine tools in the same period, and pursuing the optimal plan without consideration of total production may result in poor productivity. Considering this point, selection of the optimal process plan in the flexible CAPP methods and production scheduling (PS) were integrated, and selection of a set of the optimal process plans for multiple workpieces from the point of view of total productivity was formulated as a 0-1 integer programming problem [7]. However, this formulation needs a huge number of 0-1 variables, since it is necessary to define the variables for each sub-period defined by dividing the whole period, and therefore this method involves large computational load.

In this paper, this method is improved by formulating the integrated problem as a mixed integer programming (MIP) problem. In the next section, the flexible CAPP method [6] is outlined, and then the problem of the conventional integrated method [7] based on this CAPP method is explained. Section 3 provides formulation of the integrated problem of selection of the optimal process plans for multiple products and PS as an MIP problem. This improved method is applied to an example in Section 4, and Section 5 presents our conclusion.

## 2 Overview of Conventional Method

This section provides an outline of the conventional CAPP method [5,6], which was improved considering integration with PS [7] and will be also improved further in Section 3. In this method, which is for rough milling, it is assumed all surfaces of the workpiece and the product are parallel to the *xy*, *yz* or *zx* plane of an orthogonal coordinate system and the tool approaches the workpiece along one of these axes (Fig. 1). Process planning is performed by the following steps:

1. TRV extraction

The total removal volume (TRV), which is the volume to be eliminated from a workpiece to obtain the product shape, is calculated by subtracting the product shape from the workpiece shape (Fig. 2).

2. Concavity-based division

A cutting plane is generated at a concave part of the TRV contour by extending a surface, and then the TRV is divided by it. This process is repeated until the division has been executed at all concave parts, and the TRV is converted into a set of machining primitive shapes (MPSs). Since type of the MPS set depends on the generation direction and sequence of the cutting planes, multiple MPS sets can be produced from one TRV (Fig. 3).
3. Machining sequence and direction assignment

For each MPS set, the machining direction (Fig. 1) for each MPS and the
machining sequence for those MPSs are considered.

4. MF recognition

The machining directions and sequence assignment enables recognizing an
MPS as a machining feature (MF) based on the number of its “open faces”
and the relationship among its vertices and edges. For each MPS set, multiple
MF sets are generated depending on the direction and sequence (Fig. 4).

5. Process plan generation

For each MF set, a tool used for each MF is chosen from available tools by
applying a given rule, and the machining condition for the MF is decided by a
case-based reasoning system [8]. This operation generates, for each MPS set,
MF sets including information about the machining sequence, the machining
directions, and the tools to be used—that is, a process plans is generated.

6. Evaluation

For each process plan of each MPS set, the total machining time is estimated.
The plan that achieves the shortest total machining time is selected as the
optimal process plan for the MPS set by the full search [5] or mathematical
optimization framework [6]. After performing this operation for all MPS sets,
the estimated total machining times for the optimal plans are compared with
each other. The optimal plan for which the estimated total machining time
is the shortest is ultimately output as the optimal process plan for the TRV.

In actual manufacturing, multiple workpieces are usually machined by us-
ing multiple machines in the same period. If this method is applied to those
workpieces, the optimal plan is generated for each of them independently. Those
plans would not be optimal from the point of view of manufacturing systems,
since a machine tool can machine only one workpiece at a time. It is desirable
to integrate process planning by this method with PS, and the integrated prob-
lem was formulated as a 0-1 integer programming problem where 0-1 variables
are defined for each sub-period defined by dividing the whole period [7]. Since
machining requires long time generally, the number of those variables are huge
and therefore the integrated method involves a very large computational load.

3 Improved Integrated Method of CAPP and PS

This section provides formulation of the integrated problem of the optimal plan
selection and PS as an MIP. Two kinds of 0-1 variables $x_{avS_1...S_N dt}$, $y_{a,i,b,j}$ and
three kinds of real variables $s_{a,i}^m$, $f_{a,i}^m$, $C_{max}$ are introduced, where $a, b \in \mathcal{R} :=$
$\{1, ..., R\}$ and $v \in \mathcal{V} := \{1, ..., V\}$ stand for the ID number of product and its
MPS set, respectively, and $N$ is the total number of the MPSs. (It is assumed
that the total numbers of MPS sets and MPSs in the set are same for any
product and any MPS set.) $S_k$ is the ID number of the MPS that is machined
after machining other $k-1$ MPSs. $S_1$ takes a value in $\mathcal{N} := \{1, ..., N\}$, and
$S_k$, $k \ge 2$ takes a value in $\{0\} \cup \mathcal{N}$, $k \ge 2$. $S_{\tilde{k}} = 0, \forall \tilde{k} > k$ means only the
<figure><img src="image_2.png" /></figure>

<figure><img src="image_3.png" /><figcaption>Fig. 2. TRV Extraction. [7]</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>Fig. 3. Sets of MPSs extracted from the TRV. The numbers in each set are the identification numbers for the MPSs. [7]</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Fig. 4. MF recognition for an MPS set. Strings in each set stand for feature types ("CS", "OS", "OP", and "ST" stand for "closed slot", "open slot", "open pocket", and "step", respectively). [7]</figcaption></figure>
first k MPSs has been machined. $d \in \mathcal{D} := \{1, \dots, 6\}$ is machining direction ($1 : +x$; $2 : -x$; $\cdots 6 : -z$). $t \in \mathcal{T} := \{1, \dots, T\}$ and $m \in \mathcal{M} := \{1, \dots, M\}$ are the ID number of the utilized tool and machine. $i, j \in \mathcal{N}$ are the operation number. $x_{avS_1 \cdots S_{k-1}S_k 0 \cdots 0dt} = 1$ means that the MPS $S_k$ of the MPS set $v$ for the product $a$ is machined in the direction $d$ with the tool $t$ after machining MPS $S_1, S_2, \dots, S_{k-1}$ in this order, and the time required for this machining is $P_{avS_1 \cdots S_{k-1}S_k 0 \cdots 0dt}$, which has been calculated in advance and set to an negative value for unfeasible machining. $y_{a,i,b,j} = 1$ means the $i$-th operation of product $a$ is executed after the $j$-th operation of product $b$. $s_{a,i}^m$ and $f_{a,i}^m$ stand for the starting and finishing times of the $i$-th operation of product $a$. $C_{max}$ is the time at which all operations are completed. Let $\tau_{a,i}^m$ is the required time for the $i$-th operation of product $a$ by machine $m$, $T_m$ is the set of tools implemented on machine $m$ and $\bar{M}$ is a positive value that is large enough, then the problem of finding the optimal plans for the products which achieve the smallest makespan $C_{max}$ is described as an MIP by the following equations and inequalities. (1–(12)) are same as those in the conventional method, (14–(20)) are for formulation of PS problem as an MIP, and equation (13) integrates CAPP and PS.

$$ \text{minimize: } C_{max} \tag{1} $$

subject to:

$$ P_{avS_1 \cdots S_i 0 \cdots 0dt} \cdot x_{avS_1 \cdots S_i 0 \cdots 0dt} \ge 0, \quad \forall a \in \mathcal{R}, \forall v \in \mathcal{V}, \forall S_1, \dots, S_i \in \mathcal{N}, i \in \mathcal{N}, d \in \mathcal{D}, \forall t \in \mathcal{T} \tag{2} $$

$$ \sum_{v=1}^{V} \sum_{S_1=1}^{N} \sum_{d=1}^{6} \sum_{t=1}^{T} x_{avS_1 0 \cdots 0dt} = 1, \quad \forall a \in \mathcal{R} \tag{3} $$

$\vdots$

$$ \sum_{v=1}^{V} \sum_{S_N=1}^{N} \cdots \sum_{S_2=1}^{N} \sum_{S_1=1}^{N} \sum_{d=1}^{6} \sum_{t=1}^{T} x_{avS_1 S_2 \cdots S_N dt} = 1, \quad \forall a \in \mathcal{R} \tag{4} $$

$$ \sum_{v=1}^{V} \sum_{S_1=1}^{N} \sum_{d=1}^{6} \sum_{t=1}^{T} x_{avS_1 0 \cdots 0dt} \le 1, \quad \forall a \in \mathcal{R} \tag{5} $$

$\vdots$

$$ \sum_{v=1}^{V} \sum_{S_N=1}^{N} \cdots \sum_{S_2=1}^{N} \sum_{S_1=1}^{N} \sum_{d=1}^{6} \sum_{t=1}^{T} x_{avS_1 S_2 \cdots S_N dt} \le 1, \quad \forall a \in \mathcal{R} \tag{6} $$

$$ \sum_{d=1}^{6} \sum_{t=1}^{T} \left( x_{avS_1 0 \cdots 0dt} + \sum_{S_k=1}^{N} \cdots \sum_{\substack{\tilde{S}_1=1 \\ \tilde{S}_1 \neq S_1}}^{N} x_{av\tilde{S}_1 \cdots S_k 0 \cdots 0dt} \right) \le 1, \quad \forall k \in \mathcal{N} \setminus \{1\}, \forall a \in \mathcal{R}, \forall v \in \mathcal{V}, \forall S_1 \in \mathcal{N} \tag{7} $$
$$
\sum_{S_1=1}^{N} \sum_{d=1}^{6} \sum_{t=1}^{T} \left( x_{avS_1S_20\dots0dt} + \sum_{S_k=1}^{N} \dots \sum_{\substack{\tilde{S}_2=1 \\ \tilde{S}_2 \neq S_2}}^{N} x_{avS_1\tilde{S}_2\dots S_k0\dots0dt} \right) \le 1,
$$
$$
\forall k \in \mathcal{N} \setminus \{1,2\}, \forall a \in \mathcal{R}, \forall v \in \mathcal{V}, \forall S_2 \in \mathcal{N} \tag{8}
$$

$$
\vdots
$$
$$
\sum_{S_{N-2}=1}^{N} \cdots \sum_{S_1=1}^{N} \sum_{d=1}^{6} \sum_{t=1}^{T} \left( x_{avS_1 \cdots S_{N-1} 0 dt} + \sum_{S_N=1}^{N} \sum_{\substack{\tilde{S}_{N-1}=1 \\ \tilde{S}_{N-1} \neq S_{N-1}}}^{N} x_{avS_1 \cdots \tilde{S}_{N-1} S_N dt} \right) \le 1, \forall a \in \mathcal{R}, \forall v \in \mathcal{V}, \forall S_{N-1} \in \mathcal{N} \quad (9)
$$

$$
\sum_{S_1=1}^{N} \sum_{d=1}^{6} \sum_{t=1}^{T} \left( x_{avS_10\dots0dt} + \sum_{\substack{\tilde{v}=1 \\ \tilde{v} \neq v}}^{V} \sum_{S_2=1}^{N} x_{a\tilde{v}S_1S_20\dots0dt} \right) \le 1, \forall a \in \mathcal{R}, \forall v \in \mathcal{V} \quad (10)
$$

$$
\sum_{S_1=1}^{N} \sum_{d=1}^{6} \sum_{t=1}^{T} \left( x_{avS_10\dots0dt} + \sum_{\substack{\tilde{v}=1 \\ \tilde{v} \neq v}}^{V} \sum_{S_3=1}^{N} \sum_{S_2=1}^{N} x_{a\tilde{v}S_1S_2S_30\dots0dt} \right) \le 1,
$$
$$
\forall a \in \mathcal{R}, \forall v \in \mathcal{V} \quad (11)
$$

$$
\vdots
$$
$$
\sum_{S_1=1}^{N} \sum_{d=1}^{6} \sum_{t=1}^{T} \left( x_{avS_10\dots0dt} + \sum_{\substack{\tilde{v}=1 \\ \tilde{v} \neq v}}^{V} \sum_{S_N=1}^{N} \cdots \sum_{S_2=1}^{N} x_{a\tilde{v}S_1S_2\dots S_Ndt} \right) \le 1,
$$
$$
\forall a \in \mathcal{R}, \forall v \in \mathcal{V} \quad (12)
$$

$$
\tau_{a,i}^{m} = \sum_{v=1}^{V} \sum_{S_i=1}^{N} \cdots \sum_{S_1=1}^{N} \sum_{d=1}^{6} \sum_{t \in T_m} P_{avS_1 \cdots S_i 0 \cdots 0dt} \cdot x_{avS_1 \cdots S_i 0 \cdots 0dt},
$$
$$
\forall a \in \mathcal{R}, \forall i \in \mathcal{N}, \forall m \in \mathcal{M} \tag{13}
$$

$$
C_{\max} \ge f_{a,i}^m, \quad \forall a \in \mathcal{R}, \forall m \in \mathcal{M}, \forall i \in \mathcal{N} \qquad (14)
$$

$$
f_{a,i}^{m} = \tau_{a,i}^{m} + s_{a,i}^{m}, \quad \forall a \in \mathcal{R}, \forall m \in \mathcal{M}, \forall i \in \mathcal{N} \qquad (15)
$$

$$
s_{a,i}^m \ge -1 \cdot \left( 1 - \sum_{v=1}^V \sum_{S_i=1}^N \cdots \sum_{S_1=1}^N \sum_{d=1}^6 \sum_{t \in T_m} x_{avS_1 \cdots S_i 0 \cdots 0dt} \right),
$$
$$
\forall a \in \mathcal{R}, \forall m \in \mathcal{M}, \forall i \in \mathcal{N} \tag{16}
$$

$$
s_{a,i}^{m} - \bar{M} \cdot \sum_{v=1}^{V} \sum_{S_i=1}^{N} \cdots \sum_{S_1=1}^{N} \sum_{d=1}^{6} \sum_{t \in T_m} x_{avS_1 \cdots S_i 0 \cdots 0dt} \le -1,
$$
$$
\forall a \in \mathcal{R}, \forall m \in \mathcal{M}, \forall i \in \mathcal{N} \qquad (17)
$$
$$s_{a,i+1}^{\tilde{m}} + \overline{M} \cdot \left( 1 - \sum_{v=1}^{V} \sum_{S_{i+1}=1}^{N} \cdots \sum_{S_1=1}^{N} \sum_{d=1}^{6} \sum_{t \in T_m} x_{avS_1 \cdots S_{i+1} 0 \cdots 0dt} \right) > f_{a,i}^{m}, \\ \forall a \in \mathcal{R}, \forall m, \tilde{m} \in \mathcal{M}, \forall i \in \mathcal{N} \setminus \{N\} \quad (18)$$

$$s_{a,i}^{m} + \overline{M} \cdot \left( 1 - \sum_{v=1}^{V} \sum_{S_i=1}^{N} \cdots \sum_{S_1=1}^{N} \sum_{d=1}^{6} \sum_{t \in T_m} x_{avS_1 \cdots S_i 0 \cdots 0dt} \right) \\ \geq f_{b,j}^{m} - \overline{M} \cdot y_{a,i,b,j} - \overline{M} \cdot \left( 1 - \sum_{v=1}^{V} \sum_{S_j=1}^{N} \cdots \sum_{S_1=1}^{N} \sum_{d=1}^{6} \sum_{t \in T_m} x_{bvS_1 \cdots S_j 0 \cdots 0dt} \right), \\ \forall a, b \in \mathcal{R}, a \neq b, \forall m \in \mathcal{M}, \forall i, j \in \mathcal{N} \quad (19)$$

$$s_{b,j}^{m} + \overline{M} \cdot \left( 1 - \sum_{v=1}^{V} \sum_{S_j=1}^{N} \cdots \sum_{S_1=1}^{N} \sum_{d=1}^{6} \sum_{t \in T_m} x_{bvS_1 \cdots S_j 0 \cdots 0dt} \right) \\ \geq f_{a,i}^{m} - \overline{M} \cdot (1 - y_{a,i,b,j}) - \overline{M} \cdot \left( 1 - \sum_{v=1}^{V} \sum_{S_i=1}^{N} \cdots \sum_{S_1=1}^{N} \sum_{d=1}^{6} \sum_{t \in T_m} x_{avS_1 \cdots S_i 0 \cdots 0dt} \right), \\ \forall a, b \in \mathcal{R}, a \neq b, \forall m \in \mathcal{M}, \forall i, j \in \mathcal{N} \quad (20)$$

# 4 Case Study

The proposed method was applied to an example of $R = 3$, $V = 4$, $N = 4$, $M = 2$, $T = 8$, $T_1 = T_2 = 4$ (Fig. 5 and Table 1). The calculation was performed with a workstation (Intel Core i7-6700K 4.00GHz, 8GB RAM) and a commercial solver (IBM ILOG CPLEX Optimization Studio 12.6.2). The result shown in Table 2 and Figs. 6-7 was obtained after computing about 8 hours, though it was impossible to solve the problem by the conventional method.

# 5 Conclusion

The integrated method of flexible CAPP and PS has been improved by formulating the integrated problem as an MIP. It has become possible to obtain solutions for larger problems. Further improvement is still required for actual machining.

# Acknowledgement

We thank MAZAK Foundation for its support and Prof. Rei Hino, Nagoya University, Japan, for his advice.

# References

1. Isnaini, M.M. and Shirase, K.: Review of Computer-Aided Process Planning Systems for Machining Operation — Future Development of a Computer-Aided Process Planning System —, Int. J. Auto. Tech., 8, 317-332 (2014)
<figure><img src="image_6.png" /><figcaption>Fig. 5. TRVs (the blue/brown/green volumes) and their dimensions (in mm).</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Fig. 6. MPS set of the optimal plans.</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>Fig. 7. Gantt chart.</figcaption></figure>

<table><caption>**Table 1.** Available tools. "F" and "E" stand for facemill and endmill.

**Table 2.** Machining sequence in the optimal process plan. "X,Y,Z" stands for MPS ID, Direction and Tool ID.</caption><tr><td>Tool ID</td><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>6</td><td>7</td><td>8</td></tr><tr><td>Tool Type</td><td>F</td><td>F</td><td>E</td><td>E</td><td>F</td><td>F</td><td>E</td><td>E</td></tr><tr><td>Diameter [mm]</td><td>3</td><td>8</td><td>4</td><td>6</td><td>4</td><td>7</td><td>5</td><td>9</td></tr><tr><td>The number of teeth</td><td>4</td><td>4</td><td>4</td><td>4</td><td>4</td><td>4</td><td>4</td><td>4</td></tr><tr><td>Machine ID</td><td>1</td><td>1</td><td>1</td><td>1</td><td>2</td><td>2</td><td>2</td><td>2</td></tr></table>

<table><tr><td>Product</td><td>1</td><td>2</td><td>3</td></tr><tr><td>1st</td><td>4,3,2</td><td>3,6,2</td><td>3,3,8</td></tr><tr><td>2nd</td><td>3,1,8</td><td>2,1,2</td><td>4,2,8</td></tr><tr><td>3rd</td><td>1,5,2</td><td>1,1,8</td><td>2,1,8</td></tr><tr><td>4th</td><td>2,5,2</td><td>4,2,8</td><td>1,1,8</td></tr></table>

2. Sanchez, L.M. and Nagi, R.: A Review of Agile Manufacturing Systems, Int. J. Prod. Res., 39, 3561-3600 (2001)

3. Nakamoto, K., Shirase, K., et al.: Automatic Production Planning System to Achieve Flexible Direct Machining, JSME Int. J., Series C, 47, 136-143 (2004)

4. Hang, G., Koike, M., et al.: Flexible Process Planning System Considering Design Intentions and Disturbance in Production Process, Mechatronics for Safety, Security and Dependability in a New Era, 113-118, Elsevier (2007)

5. Morinaga, E., Yamada, M., et al.: Flexible Process Planning for Milling, Int. J. Auto. Tech., 5, 700-707 (2011)

6. Morinaga, E., Hara, T., et al.: Improvement of Computational Efficiency in Flexible Computer-Aided Process Planning, Int. J. Auto. Tech., 8, 396-405 (2011)

7. Morinaga, E., Joko, H., et al.: A Computer-Aided Process Planning Method Considering Production Scheduling, Advances in Production Management Systems: Innovative Management Towards Sustainable Growth, 348-355 (2015)

8. Nagano, T., Shirase, K., et al.: Expert System Based on Case-Based Reasoning to Select Cutting Conditions (in Japanese), J. JSPE, 67, 1485-1489 (2001)