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

机械设计 与制造 第9期 152 Machinery Design Manufacture 2014年9月 生成圆形片最优四块排样方式的确定性算法 王 岩 ，潘卫平 ，胡 钢 。 (1．南通理工学院 软件工程系，江苏 南通 226002； 2．广西大学 计算机与电子信息学院，广西 南宁 530004； 3．I~l／ll信息职业技术学院，四川 广元 628017) 摘 要：为解决圆形片无约束剪冲排样问题，提出一个生成圆形片最优四块排样方式的确定性算法。四块排样方式首先 用一条父分界线将板材分为两块，然后用两条与父分界线垂直的子分界线将两块分为四块；每个块里面只包含方向和长 度均相同的圆形片条带。该算法首先求解一维背包问题生成块里面的条带最优布局；然后隐式枚举三条分界线位置得到 所有可能的四块组合，选择排样价值最大的四块组合生成最优的四块排样方式。实验结果表明，该算法在计算时间和板 材利用率两方面都有效。 关键词：圆形片；剪冲排样；四块排样方式；背包问题；最优布局 中图分类号：TH16；TP391 文献标识码：A 文章编号：1001—3997(2015)09—0152—04 DeterministicAlgorithmforGeneratingFour-BlockCutting PatternsofCircularBlanks W ANG Yah，PAN Wei—ping~，HU Gang (1．SoftwareEngineeringDepartment，NantongPolytechnicCollege，JiangsuNantong 226002，China； 2．ComputerandElectronicInformationCollege，GuangxiUniversity，GuangxiNanning 530004，China； 3．SichuallInstituteofInformationTechnology，SichuanGuanyguan628017，China) Abstract：Inordertosolvetheunconstrainedcirclecuttingproblem．itpresents帆 optimalalgorithmofrgeneratingfour— blockcuttingpatternsofcircle．Itusesthreecuttingline todividethesheetintoofurblocks，eachofwhcihcontainscircle St Softhesamedirectionandlength．Thealgorithmfirstso~esone-dimensionalknapsackprobelmtogeneratesst却 layout inthisblock，andfinallyofurdffierentblockcombinatoinsobtainedbyimplicitenumerationthreecuttinglinepositoin， choosetheofurcompositewhcihcanmakethesheethaveamaximumvaluetogeneratetheoptimalofurblocklayout．The experimentalresultsshow that，thealgorithm si 眦 inboththe computatointime andthe materialutilizatointrite． KeyWords：CircularBlanks；ShearingandPun