An evolutionary algorithm for the rectangular cutting stock problem

The cutting stock problem is a well-known NP-hard combinatorial optimization problem. The scope of this paper is to provide a basis for exploring the integration of the evolutionary algorithm technique in artificial intelligence with classic two-dimensional cutting stock problems, with minimum trim loss. The algorithm we have developed can be used to solve non-guillotine, two-dimensional cutting stock problems. This algorithm addresses the problem of placing differently-sized small rectangle on a larger rectangle or box, in order to minimize the trim loss. The algorithm is programmed in C/C++ and runs a personal computer with an Intel 486-based CPU. The algorithm is tested using randomly generated test cases. The program was also formulated as an integer programming problem. Computational experience is discussed.