An integrated approach on cut planning and nesting for metal structures manufacturing

Abstract

An integrated approach is put forward to solve the combined cut planning and nesting problem for metal structures manufacturing. In this article, a three-stage solution procedure is framed, which involves dividing the cutting parts into several groups by rules, generating different layouts or patterns in different strategy, and selecting apt cutting patterns. As some layouts with less trim-loss may lead to high setup cost and high stock level, a multiobjective mathematical model, which takes into account the trim-loss, setup cost, labor cost, and their tradeoffs, is developed. Furthermore, a method with ant colony optimization for solving the mathematical model is proposed. The key research of this article is to focus on the nesting problem by using parallel optimization on a variety of steel plates and choosing an apt cutting pattern by weighing the trim-loss, setup cost, and labor cost. The computational results and comparison prove that the presented approach is quite effective for solving the problem.

Introduction

The metal structures are widely used in engineering machinery, mining machinery, port machinery, and other industry machinery. The production process of metal structures starts at the cutting department where steel plates are cut into different shapes and sizes, and some parts may need to be machined, bended, and welded afterward (i.e. the process of some metal structures contains cutting, drilling, bending, and welding). The production process of metal structures is shown in Figure 1.

Figure 1.

The production process of metal structures.

The goal of the metal structures manufacturing system is to improve the utilization of steel plates and reduce setup cost and hold cost, meanwhile increasing productivity. To achieve the target, the combined cut planning and nesting problem (CPNP) should be considered. In this article, two-dimensional irregular shape cutting is applied, where a steel plate should be nested as many parts as possible with less scrap. The problem formulation belongs to the wide area of cutting-stock problem. ¹ The cutting-stock problem (or trim-loss problem) is addressed such that a given order for smaller pieces has to be cut from larger stock material with some constraints. There has been lots of work concerning the cutting-stock problem. For instance, Blazewicz et al., ² Gomes and Oliveira, ³ Umetani et al., ⁴ Bennell et al., ⁵ Yaodong et al., ⁶ Cui and Chen, ⁷ Han and Na, ⁸ Xie et al., ⁹ and others proposed some nesting algorithms and gave some suggestions on the two-dimensional cutting-stock problem. In addition, some good nesting algorithms have been implemented in commercial software tools to assist the designer in the industry. However, only the ways of improving the material utilization are involved in these works. Obviously, many other factors, such as setup cost, work-in-process (WIP), and labor cost, are also very important in cutting process for metal structures manufacturing. Solving the combined cutting planning and nesting problem can weigh those factors.

The literature for the combined cutting planning and nesting problem is not vast. Hendry et al. ¹⁰ considered both the scheduling and cutting-stock problems for the copper industry. A two-stage solution procedure was proposed, where best cutting patterns to minimize the waste were generated at the first stage and a daily production planning was created at the second stage. Xie and Xu ¹¹ developed a prototype STEP-compliant process-planning system on the basis of computer-aided design (CAD), computer-aided process planning (CAPP)/ computer-aided manufacturing (CAM), and computer numerical control (CNC). Wang and Xie ¹² and Xie et al. ¹³ considered the optimal process planning for a combined punch and laser cutting machine using ant colony optimization (ACO) and genetic algorithms, respectively. Those works focused on the process-planning problem for the combined punch-and-laser machine in order to improve the efficiency of the machine and fully automate the process from layout nesting to machining. Haessler ¹⁴ considered the setup cost and the cost of trim-loss in roll paper industry. Generally, the high-quality cutting patterns were difficultly created by linear programming or simple heuristic. He proposed a formulation of the one-dimensional cutting-stock problem where a setup cost for pattern changes was incurred. ¹⁵ Verlinden et al. ¹⁶ analyzed the use of operations research (OR) techniques for integrated production planning for sheet metal operations. It aimed at creating feasible part groupings while minimizing the number of time-consuming setups at the pressbrake. Vanderbeck ¹⁷ also considered the setup cost about cutting rectangular order pieces into stock pieces in specified width and length. Niemi ¹⁸ proposed a nesting strategy and method for selecting the candidate parts to be included in each nesting layout and for choosing a combination of layouts to be cut. Nonäs and Thorstenson ¹⁹ formulated a combined cutting-stock and lot-sizing problem with a joint setup cost under static and deterministic conditions. They also suggested some different solution algorithms for the combined problem. In general, those approaches in the references are still to be improved with respect to their application in metal structures manufacturing. Considering the characteristics of metal structures production and the practical requirement, some further work on the CPNP needs to be done.

As the complexity of optimal nesting, the optimization results on steel plates in different sizes are quite different. A good nesting result will be gained on a certain type of steel plate for a group of cutting data, while the optimization result is not satisfactory on the same type of steel plate for another group of cutting data. Therefore, the nesting results are improved by using parallel optimization on a variety of steel plates. Different from the existing literature, the important research of this article is to focus on the nesting problem by using parallel optimization on a variety of steel plates and choosing apt cutting pattern by weighing the trim-loss, setup cost, and labor cost.

In this article, the CPNP for metal structures industry is concerned, and an integrated three-stage solution approach on solving the combined problem is presented. First, the parts are divided into several groups by clustering algorithm. Second, the parts of each group are nested on steel plates in different sizes and the cutting patterns are designed. Third, an apt cut planning is created by using those cutting patterns. A multiobjective mathematical model which takes into account the trim-loss, setup cost, labor cost, and their tradeoffs is proposed at the third stage. And some apt cutting patterns with low total manufacturing cost are selected by solving the mathematical model with an ACO algorithm.

The rest of the article is organized as follows. In section “The three-stage programming,” a detailed description of the three-stage solution procedure for CPNP is illustrated. A mathematical model for the CPNP is presented in section “Mathematical modeling.” Here the multiobjective mathematical model which takes into account the trim-loss, setup cost, labor cost, and their tradeoffs is illustrated in this section. In section “The solution approach,” a process for solving the combined CPNP with ACO is demonstrated. Then the results of computational experiment are described in section “Computational experiments.” Finally, conclusions and discussion are given in section “Conclusion and discussion.”

The three-stage programming

Three-stage procedure is composed of the following steps.

STAGE I: Dividing the parts into several groups by clustering algorithm:

Step 1: Grouping based on the similarity of processing procedure. The parts with similar processing procedure are divided into the same group at first.

Step 2: Grouping based on the material specifications. The parts with similar process are grouped according to their materials and thickness of sheet metal in this step.

Step 3: Grouping based on the shape features. The parts which have the same material and similar production process can be grouped according to their shape features by clustering algorithm in this step.

STAGE II: Designing the cutting patterns:

Step 4: The parts in each group are nested on the varisized steel plates by using special nesting software.

STAGE III: Modeling and proposing an optimizing algorithm for the CPNP:

Step 5: Framing a multiobjective model concerned trim-loss, setup cost, labor cost, and their tradeoffs for CPNP.

Step 6: Proposing an ACO for solving the model to obtain an optimal cut planning.

The flowchart of the integrated approach is shown in Figure 2, and a detailed description is provided in the following subsections.

Figure 2.

Flowchart of the three-stage programming.

Part grouping

The parts with the similar processing procedure are divided into a group and then cut according to its reasonable sequence (a group of parts which has long processing procedure routes will be cut in first, and the group of parts which has short processing procedure route will be cut next). As a result of such part grouping, the number of WIP is expected to be reduced in the workshop. The parts are further grouped by clustering shape feature, and the layouts are optimized after grouping. The utilization of the sheet metal and the computing complexity of the nesting software are expected to be improved.

As mentioned earlier, the first step of STAGE I is to divide those parts into several groups according to the similar processing procedure. The next step is to group those parts by their material and thickness. The parts are grouped by their shape features in the final step.

Grouping based on the similar processing procedure

We can construct a model which describes the structural relationship among product components and the process information by analyzing the metal structures products.

As shown in Figure 3, the metal structures P is composed of subparts P₁, P₂, P₃, and P₄, and the subpart P₁ is composed of parts P₁₁, P₁₂, and P₁₃. The manufacturing process of the part P₁₁ contains cutting process (W₁), milling process (W₂), welding process (W₃), and so on.

Figure 3.

An information model for the metal structures.

The parts with the similar processing procedure are grouped together according to the information model. The specific grouping steps are described as follows. The parts which need welding are grouped at first (parts P₁₂, P₁₃, P₂₁, and P₂₂ are grouped by this rule). Then, the parts which need one or two processing procedure without welding are grouped (parts P₃₂, P₃₃, and P₄ are grouped by this rule). At last, the residual parts are grouped (parts P₁₁ and P₃₁ are grouped by this rule). The cutting sequence of each group is determined by the length of process route. The number of WIP can be reduced in the workshop in this way. It is an important basis for scheduling the cutting pattern.

Grouping based on the material and thickness

The parts with the same or similar processing procedure are divided into several groups according to the materials and thickness at this step. After being grouped, parts having the same material components and thickness are in one group. By this way, the same group of parts can be ensured to be nested on a steel plate.

Grouping based on the shape features

The main purpose of grouping according to the similar processing procedure is to reduce the number of WIP. Grouping by the shape features can improve the utilization of material and the computing complexity of nesting. A detailed description of this step is present in Dezhong et al. ²⁰

The parts of the metal structures are divided into some groups by using clustering algorithm at this stage. ²¹ By using this method, the utilization of material and the computing power of nesting can be improved, meanwhile the number of WIP can be reduced. This is what the enterprises of metal structures are always seeking for.

Designing the cutting pattern

The parts are divided into some groups with the similar processing procedure, the similar shape feature, and the same material and thickness in the STAGE I. The parts of each group are nested on varisized steel plates in this stage. For example, a group of 240 cutting parts provided by the metal forming factory are nested on varisized steel plates by the Smart-Nest software (a nesting software developed by our research group). The details of tests are shown in Table 1.

Table 1.

The cutting patterns on steel plates in different specification.

Test No.	Size of sheet length × width (mm)	Utilization without surplus (%)	Utilization with surplus (%)	Area of surplus (m 2 )	Quantity of steel plates
1	3500 × 2000	71.69	71.69	0	17
2	3500 × 2200	73.86	77.75	4.49	15
3	3500 × 2500	81.25	81.25	0	12
4	4000 × 2000	76.17	78.27	2.35	14
5	4000 × 2200	74.57	76.42	2.12	13
6	4000 × 2500	77.55	82.07	4.97	11
7	4500 × 2000	72.91	76.13	3.77	13
8	4500 × 2200	71.81	74.96	3.74	12
9	4500 × 2500	75.83	81.95	6.89	10
10	5000 × 2000	77.55	77.55	0	11
11	5000 × 2200	70.50	76.89	7.03	11
12	5000 × 2500	75.83	81.32	6.18	9

In Table 1, the second column presents the size of steel plate. The third column presents the utilization without surplus. Those parts are nested on many steel plates and the last steel plates may be used only a little. The surplus steel could be stocked and used the next time. For example, 10 steel plates were used in test 9, and the tenth layout is as shown in Figure 4. We can see that the region (1120 mm × 2500 mm) is used in the last plate and the surplus steel (3380 mm × 2500 mm) is not used. The surplus would be put in storage again. The forth column presents the utilization of steel plates with deducting the surplus. The fifth column presents the area of surplus steel plate which is stored, and the last column presents the used quantity of steel plates.

Figure 4.

The example of the layout with surplus.

Different cutting patterns of the same group parts are designed in this stage. The parameters of those cutting patterns are also provided in this stage. And those parameters will be used as the input in the next stage.

Model and algorithm for the CPNP

A multiobjective mathematical model for the CPNP is presented at this stage. The trim-loss, setup cost, labor cost, and their tradeoffs are taken into account in this model. The detailed description is given in the next section. Then an approach with ACO for solving the combined problem is proposed. The feasibility of solving the CPNP with the ACO is verified by some tests. The detailed procedure of this approach is illustrated in section “The solution approach.”

Mathematical modeling

In this section, a model for the combined CPNP is illustrated. The model is based on the formulation of an optimization problem, where there are three components for the objective function (trim-loss, setup cost, and labor cost).

The combined CPNP considered can be summarized by the following three points.

The demanded parts are to be cut from varisized steel plates.

A setup cost is incurred when the cutting pattern is used. (It contains the cost of putting the steel plate on the cutting machine, the cost of gas and electricity power which the cutting machine uses, and other costs.)

Surplus is permitted to generate on the cutting patterns. It will be stocked and used the next time. The cutting patterns with surplus would incur the additional setup cost.

The problem parameters and variables are defined in Appendix 1. The combined CPNP is described as the following mathematical model

$$\begin{array}{ll}Z& =\min {\displaystyle \sum _{m=1}^M{\displaystyle \sum _{j=1}^J(c_{mj}{s}_{mj}{q}_{mj}{y}_{mj}-c_{mj}{s}_{smj}{z}_{mj})}}\\ & +{\displaystyle \sum _{m=1}^M{\displaystyle \sum _{j=1}^J(s{c}_{mj}{q}_{mj}{y}_{mj}+scs\times z_{mj})}}\\ & +{\displaystyle \sum _{m=1}^M{\displaystyle \sum _{j=1}^{J}l{c}_{mj}{q}_{mj}{y}_{mj}}}\end{array}$$

(1)

$$\text{s}.\text{t}.x_i\ge d_{i}i=1,\dots ,I$$

(2)

$${\displaystyle \sum _{m=1}^M{\displaystyle \sum _j^J{a}_{pmj}{y}_{mj}}}\ge {\displaystyle \sum _{i=1}^I{\displaystyle \sum _{p=1}^P{x}_i}}{r}_{ip}$$

(3)

$$z_{mj}=\{\begin{array}{cc}1& \text{if length of surplus}\ge L_{j,min}\&\text{width of surplus}\ge W_{j,min}\\ 0& \text{otherwise}\end{array}$$

(4)

$$y_{mj}=\{\begin{array}{cc}1& \text{if the cutting pattern of part group}m\text{with uing the steel plate}j\text{is activated}.\\ 0& \text{otherwise}\end{array}$$

(5)

$$\mu \ge U$$

(6)

$${\displaystyle \sum _{m=1}^M{q}_{mj}{y}_{mj}}\le N_{mj}$$

(7)

$${\displaystyle \sum _{j=1}^J{y}_{mj}}=1$$

(8)

There are three components in the objective function (1). The first component is driven by the need for the minimal trim-loss or maximal utilization of the raw material. The second component involves the setup cost of cutting. The last component relates to the labor cost. Equation (2) considers the balance of production demand. This constraint regards the number of final production to meet the order demand. Equation (3) considers the constraint of part demand. The left-hand side of equation (3) represents the whole parts on the cutting pattern, and the right-hand side represents the demand of cutting parts. Equation (4) considers the condition of generating surplus of the steel plate j which the part group m used. The surplus of the steel plate j which the part group m used is generated when it meets the follow conditions: (1) the length of surplus is greater than or equal to the specified minimum length and (2) the width of surplus is greater than or equal to the specified minimum width. Equation (5) represents the result being intended to gain. It considers the cutting pattern of part group m which nested on the steel plate j is opted. Equation (6) considers the constraint of material utilization. U represents the lower limit of material utilization. It means that the cutting pattern is feasible when its material utilization is greater than U. Otherwise, the cutting pattern is unfeasible. Equation (7) considers the steel plate constraint. The left-hand side of equation (7) represents the quantity of steel plates j which would be used. It has to be less than or equal to the number of steel plates j in the stock. Equation (8) considers the selected cutting pattern for part group m which used only one specification steel plate.

In fact, the material utilization, the number of steel plate, setup cost, and labor cost are different with using different cutting pattern. The total cost can be minimized by selecting apt cutting pattern. It will be realized by solving the mathematical model which contains the tradeoff of trim-loss, setup cost, and labor cost. An approach to solve this mathematic model will be introduced in the next section.

The solution approach

To solve the model for CPNP from equations (1) to (8), ACO algorithm is applied. ACO is a swarm intelligence technique inspired from the foraging behavior of real ant colonies. The ants deposit pheromone on the path in order to mark the route from the nest to food. The marked routes should be followed by other members of the colony. ²² ACO has some merits, such as it is simple, universal, and robust. ²³ Therefore, ACO exploits an optimization mechanism for solving discrete optimization problems in various engineering domain. ²⁴

Framing the diagram for CPNP

According to the target and the constraint conditions, the graphical representation for CPNP is as shown in Figure 5. As M part groups with different material and thickness need to be cut, the CPNP can be transformed into the M-levels decision problem.^25,26 Each note $\left\{y_{jm}|j=1,2,\dots ,J;m=1,2,\dots ,M\right\}$ represents the cutting pattern of part group m nested on steel plate j.

Figure 5.

The graphical representation for CPNP.

Outlining of ACO

Selecting the ants’ path

The ants move between nodes (cutting patterns) and leave different amounts of pheromone on the nodes at the same time. The pheromone impacts the next lot of ants moving. ²⁷ ${\tau }_{y_{jm}}\left(t\right)$ represents the pheromone values at t (t = 0,1,2,…) moment on the different nodes. The initial of the pheromone value ${\tau }_{y_{jm}}\left(0\right)=\epsilon$ ( $\epsilon$ is a minimal number). There are N_ant ants distributed on the nodes at the first level. Then each ant according to the pheromone value of next nodes and the heuristic factor chooses path where it will go to. The $p_{y_{jm}{y}_{z\left(m+1\right)}}^k\left(t\right)$ represents the transition probability of ant k moving from the node $y_{jm}$ to the next node $y_{z\left(m+1\right)}$ at time t. The formulation of $p_{y_{jm}{y}_{z\left(m+1\right)}}^k\left(t\right)$ is described as follows

$$p_{y_{jm}{y}_{z\left(m+1\right)}}^k\left(t\right)=\{\begin{array}{cc}\frac{{[{\tau }_{{\left[y_{jm}\right]}_{\left[y_{z(m+1)}\right]}}(t)]}^{\alpha }{[{\eta }_{{\left[y_{jm}\right]}_{\left[y_{z(m+1)}\right]}}(t)]}^{\beta }}{{\displaystyle \sum _{r\in {\text{allowed}}_k}{\left[{\tau }_{r\left(m+1\right)}\left(t\right)\right]}^{\alpha }{\left[{\eta }_{r\left(m+1\right)}\left(t\right)\right]}^{\beta }}}& y_{z\left(m+1\right)}\notin tab{u}_k\\ 0& \text{otherwise}\end{array}.$$

(9)

where tabu_k represents the next node set which ant k cannot go to. α is a positive parameter, whose value represents the relative influence of pheromone trail. It shows the relative importance of ant track. The bigger the value of α, the ant inclines more to choose the path which others have passed. β is a positive parameter, whose value represents the relative influence of heuristic information. If the value of β is bigger, the state transition probability will be close to the greed rules. ${\eta }_{{\left[y_{jm}\right]}_{\left[y_{z(m+1)}\right]}}\left(t\right)$ represents the expectation of ant k choosing next node. The bigger the value, the bigger the probability of choosing the next node (y_z(m+1)). The formulation of ${\eta }_{{\left[y_{jm}\right]}_{\left[y_{z(m+1)}\right]}}\left(t\right)$ is described as follows

$${\eta }_{{\left[y_{jm}\right]}_{\left[y_{z\left(m+1\right)}\right]}}\left(t\right)=\frac{1}{\sqrt{{\left(100{\mu }_{jm}-100{\mu }_{z\left(m+1\right)}\right)}^2+{\left(q_{jm}-q_{z\left(m+1\right)}\right)}^2}}$$

(10)

where ${\mu }_{jm}$ means the material utilization of the cutting pattern which this node represents, ${\mu }_{z\left(m+1\right)}$ means the material utilization of the cutting pattern which the next node represents, $q_{jm}$ means the quantity of the steel plates for the cutting pattern that this node represents, and $q_{z\left(m+1\right)}$ means the quantity of the steel plates for the cutting pattern that the next node represents.

Pheromone updating

Pheromone evaporation is inevitable, meanwhile the ants deposit pheromone in each iteration. The pheromone value ${\tau }_{y_{jm}}\left(t\right)$ is changing in each iteration. The pheromone value ${\tau }_{y_{jm}}\left(t\right)$ is updated as the following equations

$$\begin{array}{l}{\tau }_{{\left[y_{jm}\right]}_{\left[y_{z(m+1)}\right]}}\left(t+1\right)=\left(1-\rho \right){\tau }_{{\left[y_{jm}\right]}_{\left[y_{z(m+1)}\right]}}\left(t\right)\\ +\Delta {\tau }_{{\left[y_{jm}\right]}_{\left[y_{z(m+1)}\right]}}\left(t\right)\end{array}$$

(11)

$$\Delta {\tau }_{{\left[y_{jm}\right]}_{\left[y_{z(m+1)}\right]}}\left(t\right)={\displaystyle \sum _{k=1}^{N_{\text{ant}}}\Delta {{\tau }^k}_{{\left[y_{jm}\right]}_{\left[y_{z(m+1)}\right]}}}$$

(12)

$$\begin{array}{l}\Delta {{\tau }^k}_{{\left[y_{jm}\right]}_{\left[y_{z(m+1)}\right]}}\\ =\{\begin{array}{cc}\frac{Q}{Z_K}& \text{if ant k travels on edge}\left(y_{jm},y_{z\left(m+1\right)}\right)\\ 0& \text{otherwise}\end{array}\end{array}$$

(13)

where ρ (0 < ρ < 1) is the rate of pheromone evaporation, and 1 −ρ is the rate of pheromone retention. Reducing the pheromone values enables the algorithm to forget bad decisions made in previous iterations. ²⁸ Thus, pheromone updating can help ants to explore new area in the search space. $\Delta {{\tau }^k}_{\left[jm\right]}\left[z\left(m+1\right)\right]$ represents the pheromone value deposited on node $\left(y_{z\left(m+1\right)}\right)$ by ant k at t iteration. $\Delta {\tau }_{{\left[y_{jm}\right]}_{\left[z\right(m+1\left)\right]}}\left(t\right)$ is the sum of the pheromone value deposited on node $\left(y_{z(m+1)}\right)$ by all the ants. Q represents pheromone strength that affects the convergence speed of the algorithm. $Z_K$ represents the objective function value of ant k in this iteration.

Procedure of ACO

In this part, we give an ACO procedure for optimizing the CPNP with the rule and concepts described above. The flowchart is given in Figure 6. The step-by-step details are as follows.

• Step 1: Initialization:

  Set ACO parameters: α, β, ρ, ${\tau }_{y_{jm}}\left(0\right)$ , NC_max (maximum iterations), Q, N_ant (number of ant), U; input the parameters derived from the second stage: c_mj, s_mj, ss_mj, q_mj, N_mj, z_mj, sc_mj, scs, lc_mj, µ_mj.

• Step 2: Generate N_ant ants and place it on the nodes of first level ( $y_{mj}$ , m = 1, j = 1, 2, …, J)

• Step 3: for NC = 1: NC_max

  for k =1: N_ant

  for m = 2: M

  If the number of steel plate of the node (cutting pattern) needed is less than the surplus of the steel plate stocking or the material utilization is less than U, the node is placed in the tabu list.

  Cumulate the transition probability of each ant according to equations (9) and (10). Then, the ants select the next node of max transition probability.

  End;

  End;

• Step 4: Cumulate the solution for the objective function (1) in this iteration. If the current solution is better than the former best solution, then update the best solution.

• Step 5: Update the pheromone value according to equations (11), (12), and (13).

• Step 6: if NC < NC_max

  NC = NC + 1;

  Go to Step 2;

  Else

  Output the optimal solution;

  End;

  End;

Figure 6.

Flowchart of ACO.

Computational experiments

In this section, the proposed mathematical model is verified to be effective. The performance of the solution strategy is evaluated by an experimental demonstration. First, an ordinary metal structures production order (30 sets of excavators—175), given by the metal forming factory, is tested by the three-stage programming (Table 2). Later, the test results are reported and analyzed.

Table 2.

The information of the production order (the quantity of parts = the number of parts per set × the number of sets).

No.	Terms	Quantity
1	Quantity of all parts	256 × 30
2	Quantity of needing cutting parts	256 × 30
3	Quantity of needing bending parts	98 × 30
4	Quantity of needing machining parts	186 × 30
5	Quantity of needing welding parts	126 × 30
6	Quantity of material types	12

In the first stage, all parts are divided into two groups based on their similarity of processing procedure. Furthermore, these parts in the two groups are divided into 24 groups based on their material specifications. At last, the parts in the 24 groups are divided into 30 groups based on their shape features. Finally, 30 part groups are obtained in the first stage.

Second, the parts in each group are nested on varisized steel plates by the Smart-Nest software. The result is shown in Table 3. The detailed layouts of a cutting pattern are demonstrated in Figure 7. Different cutting patterns are obtained in the second stage, and these results will be the parameters for the third stage.

Table 3.

The cutting patterns are obtained in the second stage.

No.	Groups
		m = 1 Q235B (δ4.5)	m = 2 Q235B (δ8)	m = 3 Q235B (δ12)	m = 4 Q235B (δ30)	m = 5 Q235B (δ30)	m = 6 Q235B (δ32)	m = 7 Q235B (δ36)	m = 8 Q345B (δ8)	m = 9 Q345B (δ10)	m = 10 Q345B (δ10)	m = 11 Q345B (δ16)	m = 12 Q345B (δ16)	m = 13 Q345B (δ20)	m = 14 Q345B (δ20)	m = 15 Q345B (δ28)	m = 16 Q345B (δ32)	m = 17 Q345B (δ32)	m = 18 Q235B (δ4.5)	m = 19 Q235B (δ8)	m = 20 Q235B (δ12)	m = 21 Q235B (δ30)	m = 22 Q235B (δ32)	m = 23 Q345B (δ8)	m = 24 Q345B (δ10)	m = 25 Q345B (δ10)	m = 26 Q345B (δ16)	m = 27 Q345B (δ20)	m = 28 Q345B (δ28)	m = 29 Q345B (δ28)	m = 30 Q345B (δ32)
Pattern a 1800 × 5000 j = 1	qmj	12	11	17	13	14	17	12	7	13	14	12	15	14	11	16	15	14	8	12	14	7	12	10	12	10	15	12	7	12	13
	µmj	79.4	74.1	78.6	77.8	76.2	77.2	78.9	74.8	79.3	80	77.4	78.7	74.2	80.3	79.1	78.5	74.5	74.1	78.6	78.5	74	74.4	78.7	79.9	74.1	78.3	80.8	74.1	80.5	77.2
	ssmj	4.7	1.9	5.4	9	5.2	4.7	0	5.9	6.6	3.4	6.3	5.4	7.4	8.6	4.9	2.5	7.9	7.2	6.2	3.7	4.2	6.6	0	2.1	7.8	7.3	2.8	2.3	2.5	5.2
Pattern b 2000 × 5000 j = 2	qmj	11	10	16	11	12	15	12	6	12	13	10	13	12	10	15	14	12	6	10	13	6	10	10	11	8	13	11	6	11	12
	µmj	78.7	79.7	75.5	78.4	80.5	78.9	76.2	79.7	78.6	76.4	80.9	80.7	77.6	80.6	76.8	75.6	80	80	80	78.7	79.5	80.6	76.9	79.6	76.1	78.6	79.8	77.9	77.9	75.4
	ssmj	5.8	9.7	6.4	2.8	5.7	4.9	8.2	6.4	8.7	1.7	2.8	3.6	6.7	9.9	6.8	2.5	10	0	0	8	5.3	6.4	7.9	3.8	0	2.8	3.4	2.3	1.1	5.5
Pattern c 2200 × 5000 j = 3	qmj	10	9	14	10	11	14	10	5	10	12	10	13	11	9	14	13	11	6	10	11	6	10	9	10	7	12	11	6	10	10
	µmj	74.5	78.3	78.2	78.8	78.8	78.1	78.5	80.4	79.5	77.3	76.6	75.3	75.3	76.3	76.5	78.8	75.3	80.1	78	79.3	77.6	75	76.8	78.9	79.1	78.3	76.2	77.2	78.6	79.5
	ssmj	0	7.1	5.7	3.4	4.2	7.4	1.4	1.9	0	5.2	7.3	7.6	4.2	3.9	10.2	11	4.1	6	7.4	0	9.9	9.5	6.8	2.8	0	4.3	9.5	7.7	1.9	1.5
Pattern d 2000 × 6000 j = 4	qmj	10	8	13	9	11	13	9	5	10	11	9	12	10	8	13	12	10	6	9	11	5	9	8	10	7	11	10	5	9	10
	µmj	74.7	77.9	78.2	78.7	74.5	77.6	80.9	75.1	75.9	80.4	77.7	74.8	79	77.1	76	78.7	74.2	75.8	80.9	76.7	75.5	76.7	77.5	77.2	79.8	78.8	78.1	80.3	79.4	78.3
	ssmj	10.2	3.6	7.7	1.3	8.5	8.4	2.7	3.1	4.7	10.1	6.7	7.6	8.6	1.8	11.2	11.8	1.4	8.7	9.1	6.8	2.4	9.7	4.7	10.5	7.7	5.1	11.2	4	1.1	9.8
Pattern e 2200 × 6000 j = 5	qmj	9	8	12	8	10	12	9	5	9	10	8	10	9	8	11	11	9	5	8	10	5	8	8	9	7	10	9	5	9	9
	µmj	74.1	75.7	78.6	79.5	74.5	74.5	77.5	74.9	76.9	75.6	75.3	78	75.8	77.3	80.1	74.9	79.1	78	79.5	77.1	74.7	76.2	75.2	74.6	76.3	77.6	74.9	76	74.7	74.1
	ssmj	8.1	10.5	10.9	0	8.5	4.8	8.9	9	5.1	2.4	1	1.2	2.6	11.7	7.8	6.4	7.6	4.4	5	7.5	7.8	6.6	11.4	5.4	13	3.1	5.3	6.8	5.2	2.3
Pattern f 2500 × 6000 j = 6	qmj	8	7	11	8	9	11	8	4	8	9	7	9	8	7	10	10	8	5	8	9	4	7	7	8	6	9	8	5	8	8
	µmj	76	79.8	75.3	74.1	74.1	75.4	80.6	79.3	75.5	80	77.5	80.8	80.5	75	78.4	74.2	77.8	75.1	75.1	77.4	75.1	75.2	77.7	79.7	80.2	79	75.8	74.5	74	80.2
	ssmj	12.2	14.7	10.9	6.6	10.8	13	14.3	6.2	4.1	12.5	3.5	8.7	10.7	8.3	9.7	9.8	6.8	11.1	13.5	10.9	2.1	4.7	13.8	13.9	14	8.4	7.8	14.6	5.3	12.4
Pattern g 2000 × 7000 j = 7	qmj	8	7	11	8	9	11	8	4	9	9	8	10	9	7	11	10	9	5	8	9	5	7	7	9	6	10	8	5	8	8
	µmj	79.7	75.8	78.5	76.2	75.6	76.7	79.8	79.1	74.2	78.6	77	74.2	75	75	75.7	75.8	75.9	78.2	79.8	78.3	76.9	80.3	78.5	75.4	77.4	77.6	79.6	77.3	77.8	79.3
	ssmj	9.1	3.1	6.1	1.7	4.3	4.6	5.2	2	8.2	1.3	9.7	2.5	8.6	1.1	8.7	2.9	10.1	8.6	11.8	3.3	13.4	4.1	7.8	13.7	5.3	11.1	5.2	11.8	2.9	3.2
Pattern h 2200 × 7000 j = 8	qmj	7	6	11	7	8	10	7	4	8	8	7	9	8	7	9	10	8	5	7	9	4	7	7	8	6	9	8	4	8	7
	µmj	80.9	79.3	75.2	79.5	77.6	75.9	80.4	78.6	74.6	80.2	78.6	80.1	77.7	77.7	80.8	74.8	76.6	76.3	75.3	75.2	76.9	76.3	74.1	77.1	77.9	78.2	78.7	80.9	74	80.1
	ssmj	6.4	1.6	15	2.1	4.7	3.2	1.9	7.2	5.9	1.1	7.7	11.2	9.9	14.4	2.5	15	8.3	14.1	1.6	11	5	8.9	12.3	13.5	14.2	10.8	15.1	6	8.5	0

Figure 7.

The detailed layouts of cutting pattern f for Group 24.

Third, some optimal cutting patterns are chosen by using the multiobjective mathematical model for the CPNP. In this process, an ACO algorithm is applied. The other parameters are shown in Tables 4 and 5.

Table 4.

The parameters of c, N, sc, lc.

Materials (thickness)	Price of unit steel (yuan/m2)/quantity of steels in the inventory/setup cost of per steel/labor cost of per steel
	Pattern a 1800 × 5000				Pattern b 2000 × 5000				Pattern c 2200 × 5000				Pattern d 2000 × 6000				Pattern e 2200 × 6000				Pattern f 2500 × 6000			Pattern g 2000 × 7000					Pattern h 2200 × 7000
Q235B (δ4.5)	106	30	100	20	105	30	102	21	104	30	104	22	103	25	106	23	102	25	108	24	101	25	110	25	100	20	112	26	99	20	114	27
Q235B (δ8)	180	30	102	21	179	30	104	22	178	30	106	23	177	25	108	24	176	25	110	25	175	25	112	26	174	20	114	27	173	20	116	28
Q235B (δ12)	258	30	104	22	257	30	106	23	256	30	108	24	255	25	110	25	254	25	112	26	253	25	114	27	252	20	116	28	251	20	118	29
Q235B (δ30)	616	30	106	23	615	30	108	24	614	30	110	25	613	25	112	26	612	25	114	27	611	25	116	28	610	20	118	29	609	20	120	30
Q235B (δ32)	632	30	108	24	631	30	110	25	630	30	112	26	629	25	114	27	628	25	116	28	627	25	118	29	626	20	120	30	625	20	122	31
Q235B (δ36)	682	30	110	25	681	30	112	26	680	30	114	27	679	25	116	28	678	25	118	29	677	25	120	30	676	20	122	31	675	20	124	32
Q345B (δ8)	305	30	112	26	304	30	114	27	303	30	116	28	302	25	118	29	301	25	120	30	300	25	122	31	299	20	124	32	298	20	126	33
Q345B (δ10)	373	30	114	27	372	30	116	28	371	30	118	29	370	25	120	30	369	25	122	31	368	25	124	32	367	20	126	33	366	20	128	34
Q345B (δ16)	581	30	116	28	580	30	118	29	579	30	120	30	578	25	122	31	577	25	124	32	576	25	126	33	575	20	128	34	574	20	130	35
Q345B (δ20)	710	30	118	29	709	30	120	30	708	30	122	31	707	25	124	32	706	25	126	33	705	25	128	34	704	20	130	35	703	20	132	36
Q345B (δ28)	971	30	120	30	970	30	122	31	969	30	124	32	968	25	126	33	967	25	128	34	966	25	130	35	965	20	132	36	964	20	134	37
Q345B (δ32)	1084	30	122	31	1083	30	124	32	1082	30	126	33	1081	25	128	34	1080	25	130	35	1079	25	132	36	1078	20	134	37	1077	20	136	38

Table 5.

The parameter of ACO.

α	B	ρ	τymj(0)	U	NCmax	N ant	Q
0.3	10	0.5	0.01	75%	100	16	1000

This algorithm has been implemented in MATLAB7.0. The optimal result of the third stage by ACO is shown in Table 6. By analyzing the data of Table 6, some cutting patterns with less trim-loss may not be the best in the whole product process. The results with different ways are given in Table 7. The result of ACO in Table 7 is obtained by solving the CPNP model with the ACO. The result of U_high in Table 7 is obtained by selecting the cutting pattern of the highest material utilization. The remainder results in Table 7 are obtained by selecting the cutting pattern of pattern_a, pattern_b, … , pattern_h. The comparison of these results acquired with different ways is described in Figure 8. The total cost of production using our algorithm (ACO) is obviously less than other methods. Compared to pattern_e, it reduces the total cost by 4.7% approximately.

Table 6.

The optimal result of the third stage with ACO.

No.	Materials	Cutting pattern	No.	Materials	Cutting pattern	No.	Materials	Cutting pattern
1	Q235B (δ4.5)	Pattern h 2200 × 7000	11	Q345B (δ16)	Pattern b 2000 × 5000	21	Q235B (δ30)	Pattern b 2000 × 5000
2	Q235B (δ8)	Pattern h 2200 × 7000	12	Q345B (δ16)	Pattern f 2500 × 6000	22	Q235B (δ32)	Pattern h 2200 × 7000
3	Q235B (δ12)	Pattern g 2000 × 7000	13	Q345B (δ20)	Pattern f 2500 × 6000	23	Q345B (δ8)	Pattern h 2200 × 7000
4	Q235B (δ30)	Pattern h 2200 × 7000	14	Q345B (δ20)	Pattern b 2000 × 5000	24	Q345B (δ10)	Pattern f 2500 × 6000
5	Q235B (δ30)	Pattern b 2000 × 5000	15	Q345B (δ28)	Pattern h 2200 × 7000	25	Q345B (δ10)	Pattern f 2500 × 6000
6	Q235B (δ32)	Pattern b 2000 × 5000	16	Q345B (δ32)	Pattern d 2000 × 6000	26	Q345B (δ16)	Pattern f 2500 × 6000
7	Q235B (δ36)	Pattern h 2200 × 7000	17	Q345B (δ32)	Pattern b 2000 × 5000	27	Q345B (δ20)	Pattern a 1800 × 5000
8	Q345B (δ8)	Pattern f 2500 × 6000	18	Q235B (δ4.5)	Pattern g 2000 × 7000	28	Q345B (δ28)	Pattern h 2200 × 7000
9	Q345B (δ10)	Pattern c 2200 × 5000	19	Q235B (δ8)	Pattern g 2000 × 7000	29	Q345B (δ28)	Pattern a 1800 × 5000
10	Q345B (δ10)	Pattern h 2200 × 7000	20	Q235B (δ12)	Pattern g 2000 × 7000	30	Q345B (δ32)	Pattern h 2200 × 7000

Table 7.

The total cost of the whole product process with different methods (unit: million yuan).

ACO	U_high	Pattern_a	Pattern_b	Pattern_c	Pattern_d	Pattern_e	Pattern_f	Pattern_g	Pattern_h
1.8251	1.8296	1.9062	1.8842	1.8947	1.8881	1.9103	1.8893	1.8891	1.8664

Figure 8.

The comparison of the results of different methods.

Conclusion and discussion

In this article, the combined CPNP for metal structures manufacturing is illustrated and solved. In particular, a three-stage solution procedure is demonstrated, involving dividing the cutting parts into several groups by using clustering algorithm, generating deferent cutting patterns in deferent strategy, and selecting apt cutting patterns. Moreover, a new model for CPNP, based on the formulation as a combinatorial optimization problem, is presented. There are three components for the objective function (i.e. trim-loss, setup cost, and labor cost). Then an ACO is proposed to solve the CPNP mathematical model. The apt cutting patterns are acquired by solving the model. Computational experiment is performed to evaluate the performance of the proposed algorithm. It is verified that the proposed integrated approach on cutting planning and nesting for metal structures manufacturing is effective. In addition, as shown in Figure 8, there reaches a conclusion that the proposed method overweighs other methods.

Nonäs and Thorstenson ¹⁹ proposed some specialized heuristics on the combine cutting-stock and lot-sizing problem for dump truck manufacturing. In that article, they assumed that the steel plates are one standard dimension only and all the different cutting-stocking patterns are generated at the outset. In this article, before cutting patterns were generated, we divided the parts into many groups according to the similar processing procedure, materials and thickness, and shape features. By using part grouping, the number of WIP is reduced in the workshop; the utilization of the sheet metal and the computing complexity of the nesting software are improved. In addition, each group parts are allowed to be nested on a variety of steel plates in this article.

To differ in the other existing literature, we focus on the nesting problem by using parallel optimization on a variety of steel plates and choosing apt cutting pattern by weighing the trim-loss, setup cost, and labor cost. Some good cutting patterns with lower production cost are generated by using this approach. Our approach has been applied in practical production process and has been accepted by metal structures manufacturers of china. This approach is novel and gives a different perspective for solving the combined nesting and cut planning problem.

In this article, the trim-loss, setup cost, and labor cost in metal structures manufacturing are considered. Since the holding cost of the parts is also of great importance, an improving method to reduce the total cost of metal structures manufacturing with holding cost will be investigated in the future.