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

摘要：

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

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

所属期刊栏目：28

分类号：TP301(计算技术、计算机技术)

资助基金：国家科技支撑计划2012BAF12B10;广东省产学研项目2012B091100025;广东省科技计划2015B010128007,2016A010106006;国家自然科学基金51675108National Key Technologies R&D Program of China2012BAF12B10;Special Project on the Integration of Industry,Education and Research of Guangdong Province of China2012B091100025;Science and Technology Planning Project of Guangdong Province of China2015B010128007,2016A010106006;National Natural Science Foundation of China51675108

在线出版日期：2017-07-31（万方平台首次上网日期，不代表论文的发表时间）

页数：共15页

页码：1640-1654