基于混合顺序启发式算法的一维下料问题-论文.pdf

《基于混合顺序启发式算法的一维下料问题-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、基于混合顺序启发式算法的一维下料问题——程浩刘心报方昶基于混合顺序启发式算法的一维下料问题程浩刘心报方昶合肥工业大学，合肥，230009摘要：针对一维下料问题，提出一种改进的混合顺序启发式算法。该算法修正了传统顺序启发式算法的待切子集选择策略，采用广度搜索算法在有限时间内解决终止条件问题，根据用户最大时间容忍度动态地改变参数。最后采用C#进行编程，实现了该算法，通过对比证明算法的有效性。该算法在马鞍山钢铁公司车轮分公司正式使用了两年多，使切割率提高4。关键词：下料问题；动态规划；顺序启发式算法；背包问题中图分类号：N945．15DOI：10．3969／．．issn．1004

2、—132X．2014．16．01lAHybridSequentialHeuristicProceduretoOne—dimensionalCSPChengHaoLiuXinbaoFangChangHefeiUniversityofTechnology，Heifei，230009Abstract：Thispaperproposedanimprovedhybridsequentialheuristicprocedureforone—dimen—sionCSP．Thealgorithmmodifiedthesubsetselectionstrategyoforiginalsequ

3、entialheuristicproce—dureandavoidedtheendingconditioninthelimitedtimewithwidthsearchalgorithm，andcouldchangetheparametersaccordingtotheusers’maximumtimepatiencedynamically．FinallyC#wasusedtorealizethealgorithm．theresultsshowthealgorithmiseffective．ThisalgorithmwereusedinMa’anshanSteelCorp，

4、wheelcompanyofficialformorethantwoyears，andincreasesthecuttingrate4％．Keywords：cuttingstockproblem(CSP)；dynamicprogramming；sequentialheuristicprocedure；knapsackproblem0引言标多约束的模型，并采用不完全枚举法求解问题。一维下料问题是完全NP问题，复杂度随着文献[-73提出了一种既要切割又要焊接的一维下问题规模的增大呈指数增长。因此传统的整数规料方法，以切割率最大和焊接点个数最少为目标，划法、列生成法l_】等精确算

5、法，只能求解中小规在使用启发式算法求解过程中，把产生局部可行模的下料问题，而对于实际应用经常出现的中大解和优化可行解的过程放到矩阵上进行，使算法规模问题往往无法在有限时间内得出结果。更为简洁和适于编程。文献E83提出了一种基于文献[3]最早把顺序启发式方法(sequentialASP模式的协同优化下料思想，将传统向企业提heuristicprocedure，SHP)用于解决一维下料问供下料软件的模式，改为向企业提供下料服务，充题。该算法每次从所有产品中选择一个待切子分利用中心服务器的软硬件资源，进行多软件协集，在待切子集上进行切割，不断重复，直到切完同工作，提高切割率。文献

6、[9]进一步对SHP进所有产品。但该算法中待切子集的选择对结果影行改进，当产品较少时，采用精确算法求最优解，响很大。另外，随着产品的减少，每一步切割率不从而避免了终止条件问题，但算法的时间复杂度断下降(称为终止条件)，因而也影响最终的切割较高。文献[10]提出了一套非支配切割方案，使率。文献[4—5]改进了SHP算法，选择待切子集得不同情况下好的结果能被选中，在选择子集时时考虑了产品的种数、长度等因素，生成多个备选把产品按长度分成三组，每组设置不同的优先级子集，并从中选择一个最好的。改进的算法把较函数，采用背包问题求解局部问题的解，并对求得短的、相对切割率高的产品留到最后切

7、割，以减小的解进行调整，以使得切割方案数最少。文献终止条件的影响。文献[6]将SHP算法用于解决[11]改进了待切子集中的切割方案处理算法，保1．5维下料问题，算法考虑了许多实际中遇到的约留多个最优方案以供选择，综合考虑材料利用率束，如刀具变换、机器限制、交货期等，建立了多目和重复次数，结合多线程技术简化切割方式，以提收稿日期：2013一O4—1O高算法效率。另外，考虑余料的下料问题_1。、多基金项目：国家自然科学基金资助重点项目(71231004)目标下料问题_1。等实际中常见的下料问题越来·2191·中国机械工