Article:

Van-Dat Cung and Mhand Hifi and Bertrand Le Cun. Constrained two-dimensional cutting stock problems a best-first branch-and-bound algorithm. International Transactions in Operational Research, 7:185-210, 2000

Instances defined:

CHL1-CHL7
HCHL1-HCHL9

Instances used:

A1-A5
HH
CGCUT2 and CGCUT3
STS

Results:

While the Hchl Problems are tested on DEC Alpha (processor 21164, 500 Mhz and 1 Gbytes of RAM) the others are tested on a UltraSparc1 (145 Mhz, 64 Mbytes of RAM, under Solaris 2.5 with CPU time limited to 2 hours and virtual memory limited to 300 Mbytes). All approaches were coded in C .The presented results generated with the NVMB-BOB* algorithm.

Problem Container Size Box Types # Boxes Value Time
CHL1
( 132, 100)
30
63
8671
39.66 s
CHL2
( 62, 55)
10
19
2326
0.63 s
CHL3
( 157, 121)
15
35
5283
6.76 s
CHL4
( 207, 231)
15
27
8998
15.96 s
CHL5
( 30, 20)
10
18
390
0.16 s
CHL6
( 130, 130)
30
65
16896
19.73 s
CHL7
( 130, 130)
35
75
16881
25.04 s
A1
( 50, 60)
20
61
2020
1.73 s
A2
( 60, 60)
20
53
2505
2.59 s
A3
( 70, 80)
20
47
5451
3.36 s
A4
( 90, 70)
20
35
6179
4.20 s
A5
( 132, 100)
20
45
12985
7.61 s
HH
( 127, 98)
5
18
11586
1.01 s
CGCUT2
( 40, 70)
10
23
2892
0.66 s
CGCUT3
( 40, 70)
20
62
1860
1.61 s
STS2
( 55, 85)
30
78
4620
8.91 s
STS4
( 99, 99)
20
50
9700
8.51 s
Hchl1
( 130, 130)
30
65
11303
32383.95 s
Hchl2
( 130, 130)
35
75
9954
1204.61 s
Hchl3s
( 127, 98)
10
51
12215
16.40 s
Hchl4s
( 127, 98)
10
32
11994
634.95 s
Hchl5s
( 205, 223)
25
60
45361
69.03 s
Hchl6s
( 253, 244)
22
60
61040
8.03 s
Hchl7s
( 263, 241)
40
90
63112
22.30 s
Hchl8s
( 49, 20)
10
18
911
104.97 s
Hchl9
( 65, 76)
35
76
5240
1115.05 s