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

• 作者: 孙林岩 董晓蕾
• 来源期刊: 系统工程
• 学科: 社会科学
• 关键词: 开放式矩形布置问题 截切约束 精确算法 解空间
• 年，卷（期）: 2013,（11）
• 页码范围: 1-7
• 页数: 7页
• 分类号: C931|F224
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	孙林岩		368	9952	51.0	85.0
2	董晓蕾		1	0	0.0	0.0