J. E. Beasley. An Exact Two-Dimensional Non-Guillotine Cutting Tree Search Procedure. Operations Research, 33:49-64, 1985
-
In this paper Beasley introduces 12 instances of the two-dimensional non-guillotine cutting problem. By employing a branch-and-bound algorithm based on a lagrangean relaxation of a new mixed integer program he solves the instances to optimality.
Beasley states that "the algorithm was programmed in FORTRAN and run on a CDC 7600 using the FTN compiler with maximum optimization".
| Problem | Container Size | Box Types | # Boxes | Value | Time |
| NGCUT1 | ( 10, 10) |
5 |
10 |
164 |
0.9 s |
| NGCUT2 | ( 10, 10) |
7 |
17 |
230 |
4.0 s |
| NGCUT3 | ( 10, 10) |
10 |
21 |
247 |
10.5 s |
| NGCUT4 | ( 15, 10) |
5 |
7 |
268 |
0.1 s |
| NGCUT5 | ( 15, 10) |
7 |
14 |
358 |
0.4 s |
| NGCUT6 | ( 15, 10) |
10 |
15 |
289 |
55.2 s |
| NGCUT7 | ( 20, 20) |
5 |
8 |
430 |
0.5 s |
| NGCUT8 | ( 20, 20) |
7 |
13 |
834 |
218.6 s |
| NGCUT9 | ( 20, 20) |
10 |
18 |
924 |
18.3 s |
| NGCUT10 | ( 30, 30) |
5 |
13 |
1452 |
0.9 s |
| NGCUT11 | ( 30, 30) |
7 |
15 |
1688 |
79.1 s |
| NGCUT12 | ( 30,30) |
10 |
22 |
1865 |
229.0 s |