可截切开放式矩形布置问题的一种新精确算法

作者：董晓蕾; 孙林岩

来源：系统工程, 2013, (11): 1-7.

• 开放式矩形布置问题
• 截切约束
• 精确算法
• 解空间 Open Rectangular Packing Problem
• Guillotine Constraint
• Exact Algorithm
• Solution Space

开放式矩形布置问题是典型的NP-hard问题之一,其各子型在工业设计和生产管理中有广泛的实际应用。针对带截切约束的开放式矩形布置问题,指出并证明了其解空间存在组合冗余性质,得出了最大非冗余系数,提出了一组包括避开冗余解空间、利用最小浪费面积和动态隐性空间约束的剪枝策略,给出了一种整合以上剪枝策略并在整体架构上采用相近排序规则和带广度探索的深度优先混合搜索策略的新精确算法。算例实验表明本文算法在求解效率及可求解问题规模上优于现有文献中领先的精确算法,冗余解空间剪枝策略对本文算法的整体性能起到关键作用。

• 出版日期2013
• 单位西安交通大学; 西安交通大学机械制造系统工程国家重点实验室