矩形件三阶段带排样问题的遗传算法

《矩形件三阶段带排样问题的遗传算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、ComputerEngineeringandApplications计算机工程与应用2010，46（33）221矩形件三阶段带排样问题的遗传算法122刘睿，严玄，崔耀东122LIURui，YANXuan，CUIYao-dong1.聊城大学计算机学院，山东聊城2520002.广西师范大学计算机科学与信息工程学院，广西桂林5410041.SchoolofComputerScience，LiaochengUniversity，Liaocheng，Shandong252000，China2.CollegeofComputerSc

2、ience&InformationTechnology，GuangxiNormalUniversity，Guilin，Guangxi541004，ChinaLIURui，YANXuan，CUIYao-dong.Geneticalgorithmforrectangularthree-stagestrippackingproblem.ComputerEngi-neeringandApplications，2010，46（33）：221-224.Abstract：Ahybridgeneticalgorithmtosolveth

3、erectangularstrippackingproblemisproposed.Consideringsomespecialconstraintsandsimplifyingthecuttingprocess，theideaofthree-stageisadoptedtodesigntheimprovedalgorithm.Thegenet-icoperationisimprovedandanadjustmentoperationisusedtooptimizethecuttingplanafterthemutati

4、onoperation.Inini-tialpopulationconstructionsomesimplemethodsareusedtomaketheresultsconvergemorequickly.Theexperimentresultsindicatethevalidityofthepresentedalgorithm.Keywords：geneticalgorithm；three-stage；rectangularstrippackingproblem摘要：采用混合遗传算法求解矩形件带排样问题，采用三阶段排

5、样方式以满足特定的约束或简化切割工艺。改进遗传算子，在变异操作之后使用调整操作，以进一步简化得到的排样方案。在初始种群构造时，根据矩形件的特性采用一些简单有效的方法，使结果更好更快地收敛。实验结果表明方法对解决这类问题是有效的。关键词：遗传算法；三阶段；矩形件带排样问题DOI：10.3778/j.issn.1002-8331.2010.33.063文章编号：1002-8331（2010）33-0221-04文献标识码：Ａ中图分类号：TP391.721引言果按如下方式叙述，则可称为带切割问题（RectangularStri

6、p矩形件排样问题广泛存在于汽车、机械、家电和家具等制CuttingProblem，RSCP）：将条带切成上述n个矩形，使占用的造行业，解决好该问题可以节省原材料，简化生产工艺，降低条带总长度最小。生产成本，增加企业效益。在生产实践中，往往会碰到矩形件全部小矩形在条带上的一种排列方式称为排样方案。在带填充问题（RectangularStripPackingProblem，RSPP）[1]：把实际应用中，往往会对排样方案提出一些约束条件和目标。一些给定尺寸和需求的小矩形件摆放在一个定宽无限长的大例如，物品在货架上的摆放是RS

7、PP的一个典型应用。通常要矩形带上，在满足需求的同时要求占用长度最小。求分层摆放，且各层中物品的高度不大于相应层高度，小物品RSPP是NP难问题[1]，至今人们仍没有找到一种多项式算应当放在大物品上等。又例如，用剪床将条带切成小矩形零法来精确求解。如果用穷举法求解，随着问题规模的增大，计件是RSCP的一个典型应用，为简化下料过程，通常需要采用算量将爆炸性增长。为了避免这种在时间和空间上的巨大开较为简单的排样方案。采用的3阶段（排样）方案可以满足这销，许多学者模拟生物的进化规律引入遗传算法求解这类问两类典型应用的要求。题，

8、以得到近似最优解。在3个阶段内将排样方案切成毛坯[1]。同一阶段的剪切线相互平行，相邻两个阶段的剪切线相互垂直。例如，对于图12矩形件带排样问题的描述及三阶段排样方案所示3阶段方案，第一阶段用竖直剪切线将矩形带分成多个RSPP问题可定义为：有n个不同尺寸的矩形毛坯，其长和段（图1（a）中箭头指示），第二阶段用水平剪切