Article:

Ramón Alvarez-Valdés and Antonio Parajón José Manuel Tamarit. A tabu search algorithm for large-scale guillotine (un)constrained two-dimensional cutting problems. Computers and Operations Research, 29:925-947, 2002

Instances defined:

APT10-APT49

Instances used:

Taken from [Fayard, 1998]:
CGCUT2 and CGCUT3
CU1-CU11
CW1-CW11
GCUT13
H
HZ1
HZ2
M1-M5
OF1-OF2
TH
UU1-UU11
UW1-UW11
W

Taken from [Hifi, 1997]:
CGCUT1-CGCUT3
GCUT13
H
M1-M5 U1-U3
W1-W3

Taken from [Cung, 2000]:
A1-A5
CHL1-CHL7
HCHL1-HCHL9
H
CGCUT2 and CGCUT3
TH

Results:

Alvarez-Valdés et al. developed four heuristic algrorithms and tested them on the problems used by [Fayard, 1998], [Hifi, 1997] and [Cung, 2000]. They also created 40 new instances. The algortihms were coded in C++ and executed on a Pentium II PC with 350 MHz. The results were not presented for single problems but for all instances taken from one single paper.

The table shows the results on [Fayard, 1998] instances, compared with the algorithm developed by Fayard et al., FHZ.
All problem instances Unconstrained instances Constrained instances
Optima (of 60) Average ratio Minimum ratio Optima (of 31) Average ratio Minimum ratio Optima (of 29) Average ratio Minimum ratio
CONS
15
0.9719
0.8658
10
0.9796
0.8995
5
0.9637
0.8658
GRASP
32
0.9951
0.9346
18
0.9969
0.9806
14
0.9932
0.9346
GRASP/PR
39
0.9977
0.9787
22
0.9982
0.9871
17
0.9972
0.9787
TS500
49
0.9994
0.9879
27
0.9993
0.9879
22
0.9996
0.9973
FHZ
30
0.9895
0.9049
23
0.9979
0.9781
7
0.9806
0.9049

The table shows the results on [Hifi, 1997] unconstrained instances, compared with the algorithm developed by Hifi, DH/KD.
Results Times
Optima (of 16) Average ratio Minimum ratio Average Maximum
CONS
4
0.9755
0.9395
0.05
0.29
GRASP
9
0.9937
0.9740
3.29
15.81
GRASP/PR
10
0.9964
0.9852
9.95
47.89
TS500
12
0.9988
0.9911
26.19
120.34
DH/KD
14
0.9999
0.9980

The table shows the results on [Cung, 2000] instances.
Results Times
Optima (of 16) Average ratio Minimum ratio Average Maximum
CONS
6
0.9507
0.8590
0.05
0.17
GRASP
13
0.9871
0.9406
2.66
10.27
GRASP/PR
15
0.9927
0.9721
6.09
21.81
TS500
23
0.9980
0.9800
45.04
172.47

The table shows the results on the by Alvarez-Valdés et al. randomly generated instances.
Results Times
Optima (of 16) Average ratio Minimum ratio Average Maximum
CONS
0
0.9589
0.9322
0.4
0.7
GRASP
0
0.9820
0.9703
23.7
50.6
GRASP/PR
1
0.9883
0.9795
63.7
131.8
TS500
4
0.9953
0.9863
210.9
450.4