采用分层搜索填充策略的启发式带排样算法

Heuristics for rectangular strip packing problem based on hierarchical search filled strategy

要解决的矩形件带排样问题是指在宽度固定高度无限的二维板材上,排放给定的矩形件集合,矩形件的边必须与板材的边平行或垂直,且不允许重叠,排放最终目标是使所消耗的板材高度最小.针对此问题,采用启发式的分层搜索填充策略进行排样,先根据矩形件最长边的长度值降序排序,然后按照下-左优先原则依序填充或搜索现有的闲置空间进行填充,闲置空间包括已填充矩形件顶部空间和层末空间,空间不够时则建立新层.该启发式算法可采用成本较低的剪切方式进行切割,具有材料利用率较高、切割工艺简单、余料价值高等特点,且算法复杂度低,具有广泛的应用场合.

This paper focuses on the rectangular strip packing problem,where a set of rectangular items are packed without overlap and orthogonally into a strip of definite width and infinite height such that the required height is minimized.The proposed algorithm is based on a heuristic hierarchical search filled strategy.It contains several stages：firstly,it arranges the rectangular pieces according to the descending order of their longer sides,and then fills or searches existing idle space with the principle of the priority of bottom-left,in which the idle space includes the space above rectangular pieces filled and the space of layer end,and at last creates a new layer once the space is too small.This heuristic algorithm can generate patterns of lower cutting cost and higher material utilization,simplify the cutting process and yield leftovers of higher value.It has low complexity.So it can be widely utilized in many fields.