论文部分内容阅读
开放式矩形布置问题是典型的NP-hard问题之一,其各子型在工业设计和生产管理中有广泛的实际应用。针对带截切约束的开放式矩形布置问题,指出并证明了其解空间存在组合冗余性质,得出了最大非冗余系数,提出了一组包括避开冗余解空间、利用最小浪费面积和动态隐性空间约束的剪枝策略,给出了一种整合以上剪枝策略并在整体架构上采用相近排序规则和带广度探索的深度优先混合搜索策略的新精确算法。算例实验表明本文算法在求解效率及可求解问题规模上优于现有文献中领先的精确算法,冗余解空间剪枝策略对本文算法的整体性能起到关键作用。
Open rectangle layout is one of the typical NP-hard problems. Its sub-types have a wide range of practical applications in industrial design and production management. Aiming at the problem of open rectangular layout with cut-off constraints, the paper presents and proves that there exists a combination of redundant properties in the solution space and obtains the maximum non-redundant coefficients. A set of problems including avoiding redundant redundant solution space, And the dynamic implicit space constrained pruning strategy, a new accurate algorithm is proposed, which integrates the above pruning strategies and adopts the similar ranking rules and the depth-first hybrid search strategy with breadth-exploring in the overall architecture. The example experiment shows that the algorithm in this paper is better than the leading precision algorithm in the existing literature in terms of solving efficiency and solving the problem scale. The redundant solution space pruning strategy plays a key role in the overall performance of this algorithm.