资源描述：
《一种有效的求解一维下料问题的启发式算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、第29卷第4期计算机应用Vol.29No.42009年4月JournalofComputerApplicationsApr.2009文章编号:1001-9081(2009)04-1180-02一种有效的求解一维下料问题的启发式算法1121刘睿,严玄,许道云,崔耀东(1.广西师范大学计算机科学与信息工程学院,广西桂林541004;2.贵州大学计算机科学与技术学院,贵阳550025)(only4891@sina.com)摘要:使用了一种改进的顺序启发式算法,在排样方式的生成过程中不断修正当前排入毛坯的价值,使之趋于合理,依次选取求解背包函数获得的最大单位价
2、值的排样方式组成当前排样方案,迭代调用该过程多次,最终选取最优的排样方案。在保证较高材料利用率的同时考虑减少排样方式,增加最后一根材料余料长度等多个优化目标。通过多组实验结果比较,证实了算法的有效性。关键词:切割下料;一维下料;启发式算法中图分类号:TP391.72文献标志码:AEfficientheuristicalgorithmforone2dimensionalcuttingstockproblem1121LIURui,YANXuan,XUDao2yun,CUIYao2dong(1.CollegeofComputerScienceandInfor
3、mationEngineering,GuangxiNormalUniversity,GuilinGuangxi541004,China;2.CollegeofComputerScienceandTechnology,GuizhouUniversity,GuiyangGuizhou550025,China)Abstract:ThispaperpresentedanimprovedsequentialheuristicalgorithmtosolvetheclassicalOne2DimensionalCuttingStockProblem(1D2CSP)
4、.Thepricesoftheitemsassignedtothecurrentpatternwereadjustedsoastomakethemmorereasonable.Thepattern,whoseunitvaluewasthemaximumamongthoseofthepatternsgeneratedfromsolvingaboundedknapsackproblem,wasaddedtothecuttingplan.Severalsolutionswereconstructediterativelyandatlastthebestone
5、wasselected.Theheuristicalgorithmcangeneratecuttingplansofhighermaterialutilizationlevel,andatthesametime,canconsidermultipleobjectivessuchaspatternreductionandresiduallengthincrement.Thecomputationalresultsshowtheeffectivenessofthepresentedalgorithm.Keywords:cuttingstock;one2di
6、mensionalcuttingstock;heuristicalgorithm一维下料问题的解是一个排样方案,它包括多个排样方0引言式,并指出每个排样方式对应的原材料及其重复次数。采用[1][4]在国民经济生产中,存在着大量的切割下料问题。一顺序启发式算法(SequentialHeuristicProcedure,SHP)生成维下料问题是指原材料和所需坯料维数都为一维时,在供应排样方案的基本思想如下:每次用尚未分配的坯料生成当前条件已知的情况下考虑如何优化切割下料,使得坯料需求满排样方式,在不产生多余坯料的前提下,尽可能多地重复当前足。一个好的下料方
7、案应考虑到材料利用率高,排样方式数排样方式;重复上述过程直到满足全部坯料的需求。少,最后一根材料余料长等多个优化目标的实现。目前国内为了得到好的排样方式,采用修正毛坯价值的方法[2,5]外对于一维下料问题的研究主要围绕提高材料利用率,使用(SequentialValueCorrection),每次选取单位价值高的排的算法包括精确算法、启发式算法和各种智能算法等。文献样方式。令毛坯的初始价值等于其长度(vi=li),生成当前排[2]使用一种基于顺序价值修正的启发式算法,在提高材料样方式前,利用以前的信息修正各种毛坯i(i=1,2,⋯,m)的利用率上取得了
8、较好的效果,但是算法设计只考虑一种长度价值vi,通过多次重复该过程,使得毛坯的价值系数达到较为
