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
A1-A5
HH
CGCUT2 and CGCUT3
STS
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 |