T-shape homogenous block patterns for the two-dimensional cutting problem |
| |
Authors: | Yaodong Cui Zhiyong Liu |
| |
Institution: | (1) Department of Computer Science, Guangxi Normal University, Guilin, 541004, China;(2) Institute of Computing Technology, Chinese Academy of Sciences, Beijing, China |
| |
Abstract: | This paper presents an algorithm for unconstrained T-shape homogenous block cutting patterns of rectangular pieces. A vertical
cut divides the stock sheet into two segments. Each segment consists of sections that have the same length and direction.
A section contains a row of homogenous blocks. A homogenous block consists of homogenous strips of the same piece type. Each
cut on the block produces just one strip. The directions of two strips cut successively from a block are either parallel or
orthogonal. The algorithm uses a dynamic programming recursion to generate optimal blocks, solves knapsack problems to obtain
the block layouts on the sections and the section layout on segments of various lengths, and optimally selects two segments
to compose the cutting pattern. The computational results indicate that the algorithm is efficient in improving material usage,
and the computation time is reasonable. |
| |
Keywords: | Cutting stock Unconstrained two-dimensional cutting Homogenous blocks |
本文献已被 SpringerLink 等数据库收录! |
|