单规格一刀切矩形排样问题的启发式搜索算法

来源：软件学报杂志2017年第7期北京时间：

作者：王磊,刘强,陈新

单位：王磊，广东省计算机集成制造重点实验室 广东工业大学, 广东 广州 510006;广东科贸职业学院 信息工程系, 广东 广州 51043011,刘强，广东省计算机集成制造重点实验室 广东工业大学, 广东 广州 51000602,陈新，广东省计算机集成制造重点实验室 广东工业大学, 广东 广州 51000603

摘要：针对单规格一刀切二维矩形排样问题，提出了一种启发式搜索算法，称为大小工件分治择优匹配（bigitemsmallitem divide-and-conquer best-fit，简称BSDBF）启发式算法.该算法基于组化规则，提出了大小工件分治策略和组块快速举荐算法，是对组化策略的关键补充，这对优解获得至关重要.然后，择优选择适应度高的组块进行递归排样，贪心获得各块板材的排样方案.最后，基于设计的工件拆分方法，对初始解进行后处理小规模重排，进一步提升解的质量.因为没有随机因素，其获得的优解可复现，也是BSDBF算法区别于其他算法的典型特征.大量Benchmark案例的实验结果表明，BSDBF算法求解质量优于其他算法的报道结果.

关键词：固定尺寸;装箱问题;启发式;适应度;组化

基金资助：国家科技支撑计划（2012BAF12B10）；广东省产学研项目（2012B091100025）；广东省科技计划（2015B010128007，2016A010106006）；国家自然科学基金（51675108）