An Innovative Genetic Algorithm for a Multi-Objective Optimization of Two-Dimensional Cutting-Stock Problem

Figures & data

Figure 1. Cutting process schematic representation.

Table

$⌊x⌋$	: Greatest integer lower than x
$⌈x⌉$	: Lowest integer greater than x
N	: Number of pieces orders to be fulfilled
K	: Number of available rolls widths in stock
wi	: Width of the i ^th pieces order (i =1,…, N), arranged in a decreasing width (w1 ≥ w2 ≥…≥wN)
li	: Length of the i ^th pieces order (i =1,…, N)
di	: Demand of the i ^th pieces order (i =1,…, N)
Wk	: Width of the k ^th width roll (k =1,…, K), arranged in a decreasing width (W1 > W2 >…>WK)
Vkji	: Number of units of width wi to be cut according to the j ^th pattern from the k ^th width roll
Vkj	: j ^th cutting pattern of the k ^th roll width (with independence of the length)
Lkj	: Length produced with the pattern Vkj.
Ykj	: Equal to 1, if the pattern Vkj is used (Lkj>0) and 0 otherwise (Lkj =0)
Xkji	: denotes the integer value$⌊L_{kj}/l_i⌋$ if Vkji >0 (hence, XkjiVkji is the number of pieces of width wi contained in pattern Vkj through the length Lkj.
Jk	: Number of patterns of Wk roll width
M	: Huge positive constant, which can be calculated as $M=\sum _{i=1}^N{l}_i{d}_i$

Table 1. Data example.

Item Number (It N)	Width wi	Length li	Demand di
1	1.3	2.2	650
2	1.2	2.3	600
3	1.2	2	200
4	0.5	1.4	380

Figure 2. Optimal Pareto front.

Figure 3. Optimal solution with two setups.

Figure 4. Optimal solution with three setups.

Figure 5. Optimal solution with four setups.

Figure 6. Flowchart of the proposed genetic algorithm.

Figure 7. First and second crossover operator.

Table 2. Feasible patterns with the associated roll widths.

Vkj	V11	V12	V13	V21	V14	V15	V16	V22	V17	V18	V23	V19	V24
	1(V111)	1	1	1	0	0	0	0	0	0	0	0	0
	1(V112)	0	0	0	2	1	1	1	0	0	0	0	0
	0(V113)	1	0	0	0	1	0	0	2	1	1	0	0
	0(V114)	0	2	1	0	0	2	1	0	2	1	5	4
Wk	2.5	2.5	2.5	2	2.5	2.5	2.5	2	2.5	2.5	2	2.5	2

Table 3. Experimental results.

Code	VRE (%)
	First run	Second run	Third run	Average
P1-A1	1.42	1.37	1.54	1.44
P1-A2	1.11	1.28	1.28	1.22
P1-A3	1.07	0.98	1.14	1.06
P1-B1	1.37	1.56	1.64	1.52
P1-B2	1.33	1.24	1.24	1.27
P1-B3	1.22	1.19	1.19	1.20
P2-A1	1.08	1.19	1.32	1.20
P2-A2	0.78	0.74	0.95	0.82
P2-A3	0.72	0.74	0.83	0.76
P2-B1	0.94	1.12	0.98	1.01
P2-B2	0.7	0.86	0.92	0.83
P2-B3	0.76	0.68	0.76	0.73
P3-B1	1.96	1.82	1.39	1.72
P3-B2	1.14	1.25	1.31	1.23
P3-B3	1.24	1.11	1.03	1.13
P3-C1	1.82	1.89	1.97	1.89
P3-C2	1.62	1.53	1.53	1.56
P3-C3	1.22	1.13	1.04	1.13

Figure 8. Evolution of VRE (%) for P1-A1, P2-A1 and P3-B1.

Table 4. Computing time with the elaborated genetic algorithm and CPLEX solver.

Problem Number	N	K	Average CT
			Genetic algorithm	CPLEX solver
1-2-3	10	1-2-3	2 min 11 sec	9min 1 sec
4-5-6	15	1-2-3	4 min 6 sec	307 min 10 sec
7-8-9	20	1-2-3	5 min 3 sec	1836 min 16 sec
10-11-12	30	1-2-3	15 min 12 sec	OM
13-14-15	40	1-2-3	31 min 19 sec	OM

OM: out of memory