Article:

Mhand Hifi. The DH/KD Algorithm: A Hybrid Approach for Unconstrained Two-Dimensional Cutting Problems. European Journal of Operational Research, 97:41-52, 1997

Instances defined:

U1-U3
W1-W3

Instances used:

CGCUT1-CGCUT3
GCUT13
Herz
M1-M5

Results:

2-staged guillotine cutting, executed on Data General AV8000 (Quadri-Processor Motorola 88100), DH/KD algorithm

Problem Container Size Box Types # Boxes Optimal Value Time
CGCUT1
( 40, 70)
7
16
249
0.17 s
CGCUT2
( 40, 70)
10
23
3076
0.51 s
CGCUT3
( 40, 70)
20
62
2240
0.63 s
GCUT13
( 3000, 3000)
32
8997780
10.01 s
H
( 127, 98)
5
12348
0.06 s
M1
( 100, 156)
10
15024
0.10 s
M2
( 253, 294)
10
73176
0.18 s
M3
( 318, 473)
10
142817
0.28 s
M4
( 501, 556)
10
265768
0.35 s
M5
( 750, 806)
10
577882
0.47 s
U1
( 4500, 5000)
10
22370130
27.05 s
U2
( 5050, 4070)
10
20168944
29.31 s
U3
( 7350, 6579)
20
48074745
63.41 s
W1
( 5000, 5000)
20
35728
21.80 s
W2
( 3427, 2769)
20
161424
257.51 s
W3
( 7500, 7381)
40
234108
657.43 s