A Hybrid Algorithm for the Non-Guillotine Cutting Problem |
| |
Authors: | Víctor Parada Lorena Pradenas Muricio Solar Rodrigo Palma |
| |
Institution: | (1) Departamento de Ingeniería Informática, Universidad de Santiago de Chile, Av. Ecuador 3659, Santiago, Chile;(2) Departamento de Ingeniería Industrial, Universidad de Concepción, Casilla 160-C, Correo 3, Concepción, Chile;(3) Departamento de Ingeniería Informática, Universidad de Santiago de Chile, Av. Ecuador 3659, Santiago, Chile |
| |
Abstract: | In this article, a meta-heuristic method to solve the non-guillotine cutting stock problem is proposed. The method is based on a combination between the basic principles of the constructive and evolutive methods. With an adequate management of the parameters involved, the method allows regulation of the solution quality to computational effort relationship. This method is applied to a particular case of cutting problems, with which the computational behaviors is evaluated. In fact, 1000 instances of the problem have been classified according to their combinatorial degree and then the efficiency and robustness of the method have been tested. The final results conclude that the proposed method generates an average error close to 2.18% with respect to optimal solutions. It has also been verified that the method yields solutions for all of the instances examined; something that has not been achieved with an exact constructive method, which was also implemented. Comparison of the running times demonstrates the superiority of the proposed method as compared with the exact method. |
| |
Keywords: | cutting stock heuristic methods trim loss |
本文献已被 SpringerLink 等数据库收录! |
|