Heuristic for the rectangular two-dimensional single stock size cutting stock problem with two-staged patterns |
| |
Authors: | Yaodong Cui Zhigang Zhao |
| |
Affiliation: | School of Computer, Electronics and Information, Guangxi University, Nanning 530004, China |
| |
Abstract: | Two-staged patterns are often used in manufacturing industries to divide stock plates into rectangular items. A heuristic algorithm is presented to solve the rectangular two-dimensional single stock size cutting stock problem with two-staged patterns. It uses the column-generation method to solve the residual problems repeatedly, until the demands of all items are satisfied. Each pattern is generated using a procedure for the constrained single large object placement problem to guarantee the convergence of the algorithm. The computational results of benchmark and practical instances indicate the following: (1) the algorithm can solve most instances to optimality, with the gap to optimality being at most one plate for those solutions whose optimality is not proven and (2) for the instances tested, the algorithm is more efficient (on average) in reducing the number of plates used than a published algorithm and a commercial stock cutting software package. |
| |
Keywords: | Cutting Two-dimensional cutting stock Two-staged patterns Column generation |
本文献已被 ScienceDirect 等数据库收录! |
|