生成圆形片最优四块排样方式的确定性算法

作     者：王岩 潘卫平 胡钢 WANG Yan;PAN Wei-ping;HU Gang

作者机构：南通理工学院软件工程系江苏南通226002 广西大学计算机与电子信息学院广西南宁530004 四川信息职业技术学院四川广元628017 

出 版 物：《机械设计与制造》 (Machinery Design & Manufacture)

年 卷 期：2015年第9期

页      面：152-155页

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081203[工学-计算机应用技术] 08[工学] 0835[工学-软件工程] 0802[工学-机械工程] 080201[工学-机械制造及其自动化] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家自然科学基金资助项目(11461038) 

主　　题：圆形片 剪冲排样 四块排样方式 背包问题 最优布局 

摘      要：为解决圆形片无约束剪冲排样问题,提出一个生成圆形片最优四块排样方式的确定性算法。四块排样方式首先用一条父分界线将板材分为两块,然后用两条与父分界线垂直的子分界线将两块分为四块;每个块里面只包含方向和长度均相同的圆形片条带。该算法首先求解一维背包问题生成块里面的条带最优布局;然后隐式枚举三条分界线位置得到所有可能的四块组合,选择排样价值最大的四块组合生成最优的四块排样方式。实验结果表明,该算法在计算时间和板材利用率两方面都有效。