一种针对绝缘纸板排样的混合算法.pdf

第3期
机槭设计与制造
2013年3月
Machinery Design Manufacture
种针对绝缘纸板排样的混合算法
邓应波,祝胜兰,饶运清
(华中科技大学机械科学与工程学院,湖北武汉430074)
摘要:绝缘纸板排样属于“一刀切”的二维矩形排样问题,是一个NP难问题,在造纸、变压器制造等领域有着广泛的应
用。提出了一种改进的剩余矩形填充算法和遗传算法相结合的混合算法,建立绝缘纸板排样的数学模型,在满足“一刀
切”エ艺的同时,能使同种类零件尽量排放在一起,方便加エ。算法解决了多种类零件、多种美板材排样的组合优化问題,
并结合エ厂下料实例,得到了更优的排样方案,大大提高板材利用率。最后总结并分析了二维排样问题的前景。
关键词:矩形排样;一刀切;改进的剩余矩形填充算法;遗传算法
中阳分类号:TH16;1TB484.1文献标识码:A文章编号:1001-3997(2013)03-0023-03
A Hybrid Algorithm for Fullerboard Packing Problem
DENG Ying-ho, ZHU Sheng-lan, RAO Yun-qing
( School of Mechanical Science and Engineering, Huazhong University of Science and Technology, Hubei Wuhan 430074
China
Abstract: Fullerboard packing problem is one of 2D guillotine rectangle packing problems and has shown to be NP hard It
has been widely applied in the fields of papermaking, transformer manufacturing and so on. t proposes a hybrid algorithm of
combining improved filing gor t hm of su lus ectangle with enetic ad ohms and then establishes the mathematical model
of fullerboard packing. This hybrid algorithm can arrange the same kind of rectangles close to each other with guillotine
constraint, which is conenient for processing. It soles the combinatorial optimzation of multiple kinds of parts and boards
According to an example from factory, algorithm performs better and greatly improes its utilization At Last a summary is
made and analyzed about the prospect of 2D rectangle packing problems
Key ords: Rectangle Packing; Guillotine; Improved Fillin A orithm of Surplus Rectangle; Genetic Algorithms
1引言
对“一刀切”这种特殊的二维矩形排样问题,国内外学者提出了多种
矩形件优化排样问题长久以来都是金属切割、船舶制造、玻启发式排样规则,如FDH、NDH、 BFDHY等,蚁群、网络算法P吗
璃切割以及造纸业等制造业领域中所面临的一个重大问题。由于也被应用到矩形排样的研究中。
制造业原材料消耗巨大,一种优秀的矩形排样方案能提升原材料12研究问题描述
利用率、缩短排样时间、节约成本,进而提升企业的竞争力。
绝缘纸板是大型变压器制造过程中必不可少的一种材料,
1.1排样问题理论研究
多用于纸筒、墊块条料、装撑、外皮角环等零部件,起着变压器内
维矩形件优化排样主要是指在给定的矩形板材上排放多种部绝缘、防止内部放电、保证线圈有稳定的轴向尺寸等作用。在加
不同规格、不同数量的矩形零件,研究如何在这些矩形零件既不相工过程中,多采用锯床或剪板机对绝缘纸板板材进行下料,得到
互重。也不超出板材边界的情形下,尽可能多地排放这些矩形件
生产过程中所需要的不同尺寸、数量的绝缘纸板零件。绝缘纸板
以便最大限度地利用板材使材料的利用率达到最高。经学者研究、排样属于二维矩形优化排样问题,具有以下工艺要求:(1)任意两
维矩形件优化排样向题是典型的组合优化问题具有很高的计算复个矩形零件不重叠,各零件均不能超出矩形板材的边界且被排放
杂性,属于NPC问题。文献啊详细比较了一维矩形排样问题的启发矩形零件的边要平行于矩形板材的边;2)绝缘纸板材具有纤
式算法和元启发式算法之间的优劣性:文献堤出了一种新颖的启维方向,而待排样零件中的部分零件存在纤维方向要求,部分零
发式算法,提出了 Corner- occupying action, Cave-occupying action,件不存在纤维方向要求,故单种零件能否进行90旋转需要根据
Cave degree, Corner degree以及 Edge degree等一系列概念来评零件自身属性而定;(3)由于绝缘纸板一般采用锯床、剪板机加
估每一个矩形零件所排放的位置对最终解的影响;文献提出了エ,故零件排样后要满足”“一刀切”的下料工艺,切割过程中不考
背包算法来解决矩形件优化排样问题,文献合遗传算法和模虑刀缝宽度;(4)绝缐纸板板材规格多种多样,因此属于多零件多
拟退火算法来解决矩形件优化排样问题,得到了近似最优解。针板材排样,需要解决如何选择零件和板材进行组合下料的问题
来稿日期:2012-05-27
基金项目:江苏省科技支撑计划项目(BE2010170)
作者简介:邓应波,(1989-),男,湖北荆州人,硕士研究生,主要研究方向:优化排样及智能算法