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
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
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 |