生成矩形毛坯最优两段排样方式的确定型算法

《生成矩形毛坯最优两段排样方式的确定型算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第３５卷第１期计算机学报Ｖｏｌ．３５Ｎｏ．１２０１２年１月ＣＨＩＮＥＳＥＪＯＵＲＮＡＬＯＦＣＯＭＰＵＴＥＲＳＪａｎ．２０１２生成矩形毛坯最优两段排样方式的确定型算法季君１）陆一平１）查建中１）崔耀东２）王金敏３）１）（北京交通大学机械与电子控制工程学院北京１０００４４）２）（广西大学计算机与电子信息学院南宁５３０００４）３）（天津职业技术师范大学机械工程学院天津３００２２２）摘要排样价值、切割工艺和计算时间是排样问题主要考虑的３个因素．文中提出一个新的基于排样模式的确定型排样算法———同质块两段排样算法，此算法

2、适合剪冲下料工艺，在实现工艺简化的同时提高了排样价值时间比．首先通过动态规划算法生成最优同质块，然后求解一维背包问题生成块在级中的最优排样方式和级在段中的最优排样方式，最后选择两个段生成最优的两段排样方式．通过３组经典测题对该文算法进行了测试，将算法与４种著名算法进行了比较．实验结果表明，该文算法的优化结果好于以上４种著名算法，有效地提高了板材利用率，并且计算时间合理．关键词下料；二维无约束排样；同质块；背包问题；动态规划算法中图法分类号ＴＰ３９１犇犗犐号：１０．３７２４／ＳＰ．Ｊ．１０１６．２０１２．００１８

3、３犃犇犲狋犲狉犿犻狀犻狊狋犻犮犃犾犵狅狉犻狋犺犿犳狅狉犗狆狋犻犿犪犾犜狑狅犛犲犵犿犲狀狋犆狌狋狋犻狀犵犘犪狋狋犲狉狀狊狅犳犚犲犮狋犪狀犵狌犾犪狉犅犾犪狀犽狊ＪＩＪｕｎ１）ＬＵＹｉＰｉｎｇ１）ＣＨＡＪｉａｎＺｈｏｎｇ１）ＣＵＩＹａｏＤｏｎｇ２）ＷＡＮＧＪｉｎＭｉｎ３）１）（犛犮犺狅狅犾狅犳犕犲犮犺犪狀犻犮犪犾，犈犾犲犮狋狉狅狀犻犮犪狀犱犆狅狀狋狉狅犾犈狀犵犻狀犲犲狉犻狀犵，犅犲犻犼犻狀犵犑犻犪狅狋狅狀犵犝狀犻狏犲狉狊犻狋狔，犅犲犻犼犻狀犵１０００４４）２）（犛犮犺狅狅犾狅犳犆狅犿狆狌狋犲狉，犈犾犲犮狋狉

4、狅狀犻犮狊犪狀犱犐狀犳狅狉犿犪狋犻狅狀，犌狌犪狀犵狓犻犝狀犻狏犲狉狊犻狋狔，犖犪狀狀犻狀犵５３０００４）３）（犛犮犺狅狅犾狅犳犕犲犮犺犪狀犻犮犪犾犈狀犵犻狀犲犲狉犻狀犵，犜犻犪狀犼犻狀犝狀犻狏犲狉狊犻狋狔狅犳犜犲犮犺狀狅犾狅犵狔犪狀犱犈犱狌犮犪狋犻狅狀，犜犻犪狀犼犻狀３００２２２）犃犫狊狋狉犪犮狋Ｐａｃｋｉｎｇｐｒｏｂｌｅｍｓｈｏｕｌｄｃｏｎｓｉｄｅｒｔｈｒｅｅｆａｃｔｏｒｓｏｆｐａｔｔｅｒｎｖａｌｕｅ，ｃｕｔｔｉｎｇｔｅｃｈｎｉｑｕｅｓａｎｄｃｏｍｐｕｔａｔｉｏｎｔｉｍｅ．Ａｎｅｗｄｅｔｅｒｍｉｎｉｓｔｉｃａ

5、ｌｇｏｒｉｔｈｍｉｓｐｒｏｐｏｓｅｄｆｏｒｇｅｎｅｒａｔｉｎｇｔｈｅｏｐｔｉｍａｌｔｗｏｓｅｇｍｅｎｔｃｕｔｔｉｎｇｐａｔｔｅｒｎｓｆｏｒｒｅｃｔａｎｇｕｌａｒｂｌａｎｋｓｂａｓｅｄｏｎｔｈｅｈｏｍｏｇｅｎｏｕｓｂｌｏｃｋ．Ｔｈｉｓｐａｐｅｒ’ｓａｌｇｏｒｉｔｈｍｉｓａｐｐｒｏｐｒｉａｔｅｆｏｒｔｈｅｓｈｅａｒｉｎｇａｎｄｐｕｎｃｈｉｎｇｐｒｏｃｅｓｓ．Ｂｏｔｈｓｉｍｐｌｅｐａｔｔｅｒｎｓｃａｎｂｅｏｂｔａｉｎｅｄａｎｄｖａｌｕｅｔｏｔｉｍｅｃａｎｂｅｉｍｐｒｏｖｅｄ．Ｔｈｉｓａｌｇｏｒｉｔｈｍｕｓｅ

6、ｓａｄｙｎａｍｉｃｐｒｏｇｒａｍｍｉｎｇｔｏｇｅｎｅｒａｔｅｏｐｔｉｍａｌｈｏｍｏｇｅｎｏｕｓｂｌｏｃｋｓ，ｓｏｌｖｅｓｏｎｅｄｉｍｅｎｓｉｏｎａｌｋｎａｐｓａｃｋｐｒｏｂｌｅｍｓｔｏｏｂｔａｉｎｔｈｅｈｏｍｏｇｅｎｏｕｓｂｌｏｃｋｌａｙｏｕｔｓｏｎｔｈｅｓｅｃｔｉｏｎｓａｎｄｔｈｅｓｅｃｔｉｏｎｌａｙｏｕｔｏｎｓｅｇｍｅｎｔｓ，ａｎｄｏｐｔｉｍａｌｌｙｓｅｌｅｃｔｓｔｗｏｓｅｇｍｅｎｔｓｔｏｃｏｍｐｏｓｅｔｈｅｃｕｔｔｉｎｇｐａｔｔｅｒｎ．Ｔｈｅａｌｇｏｒｉｔｈｍｉｓｔｅｓｔｅｄｔｈｒｏｕｇｈｔｈｒｅｅ

7、ｇｒｏｕｐｃｌａｓｓｉｃｐｒｏｂｌｅｍｓ，ａｎｄｃｏｍｐａｒｅｓｗｉｔｈｔｈｒｅｅｆａｍｏｕｓａｌｇｏｒｉｔｈｍｓ．Ｔｈｅｃｏｍｐｕｔａｔｉｏｎａｌｒｅｓｕｌｔｓｉｎｄｉｃａｔｅｔｈａｔｔｈｉｓｐａｐｅｒ’ｓａｌｇｏｒｉｔｈｍｉｓｂｅｔｔｅｒｔｈａｎｔｈｅａｂｏｖｅｆｏｕｒａｌｇｏｒｉｔｈｍｓ．Ｔｈｅａｌｇｏｒｉｔｈｍｉｓｅｆｆｉｃｉｅｎｔｉｎｉｍｐｒｏｖｉｎｇｍａｔｅｒｉａｌｕｓａｇｅ，ａｎｄｔｈｅｃｏｍｐｕｔａｔｉｏｎｔｉｍｅｉｓｒｅａｓｏｎａｂｌｅ．犓犲狔狑狅狉犱狊ｃｕｔｔｉｎｇｓｔｏｃｋ；ｕｎｃｏｎ

8、ｓｔｒａｉｎｅｄｔｗｏｄｉｍｅｎｓｉｏｎａｌｃｕｔｔｉｎｇ；ｈｏｍｏｇｅｎｏｕｓｂｌｏｃｋｓ；ｋｎａｐｓａｃｋｐｒｏｂｌｅｍ；ｄｙｎａｍｉｃｐｒｏｇｒａｍｍｉｎｇｒｅｃｕｒｓｉｏｎ收稿日期：２０１００１０３；最终修改稿收到日期：２０１１１２２１．本课题得到国家自然科学基金（６１０６３０３１，６０９７５０４６）资助．季君，女，１９７９年生，博士研究生，主要研究方向为优化计算技术