带批处理机的动态hfs调度模型及lr算法研究

《带批处理机的动态hfs调度模型及lr算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、郑州大学硕士学位论文带批处理机的动态HFS调度模型及LR算法研究姓名：曹颖申请学位级别：硕士专业：管理科学与工程指导教师：轩华201205摘要钢管是轧钢生产的一项重要产品，广泛用于制造构件和机械零件。无缝钢管的制造方法有很多，如热轧、冷轧、冷拔等。其中热轧工艺是无缝钢管的主要制造方法。因此研究热轧工艺的生产调度对于无缝钢管的生产具有重要的现实意义。由于钢管生产方式具有操作步骤复杂、约束条件多、随机性高等特点，使得组合优化成为一项非常繁琐且技术性较高的工作，单靠人工方法很难做到良好、合理的调度。本文从钢管生产工艺的过程和特点着手，进而对加工制作阶段的各种约束条件进行研究和分析。同时

2、，结合某大型无缝钢管厂的具体背景，提炼出第一阶段具有批处理特征的动态HFS调度问题，建立了带批处理机的动态HFS调度模型，目标是最小化所有工件的加权完成时间。本问题归结为经典的批处理机调度问题。本模型是大型的O．1混合整数规划，属于NP难问题。拉格朗日松弛算法是求解此类问题的有效算法。文中首先运用拉格朗日松弛算法进行了求解，通过引入两个拉格朗日乘子，将松弛问题分解为工件级子问题，采用动态规划方法进行求解；其次针对该模型，构造了改进的拉格朗日松弛算法的求解过程，将松弛问题分解为批级子问题，设计了求解批级子问题的动态规划算法和构造可行解的启发式算法。仿真实验结果表明随着问题规模的增大

3、，利用改进的拉格朗日算法得到解的对偶间隙比基于工件分解的拉格朗日算法所得的对偶间隙要小，计算机运行时间也相对较短。解的质量相对好一些，提出的此种算法更有竞争力。关键词：动态HFS调度；批处理；拉格朗日松弛；动态规划AbstractSteel-tubeisanimportantproductioninsteelrollingproduction．Studyofproductionschedulingforsteelpipeproductionhasanimportantpracticalsignificance．111eproductionofsteeltubehascomplic

4、atedtechnologicalrequirementsandtheproductismulti—variety．It’Sveryhardtodotheproductionarrangementwellandtoobtaingoodandreasonableplanfortheproduction．Basedonthebackgroundofsteel—tubeproduction,thispaperpresentsthedynamichybridflowshopscheduling谢tIlbatchingrequirementatthef'n-ststage，andestab

5、lishesanintegerprogrammingmodelforthisproblem．11坨objectiveistominimizethetotalweightedcompletiontime．ThisproblemCanberegardedasabatchingmachinesschedulingproblem．Thismodelisalargescale0—1mixedintegerprogramming，belongingtoNPhardproblem．tagrangi锄relaxationalgorithmisaneffectiveforsolvingsuchpr

6、oblems．Inthismethod,theprimalproblemwasdecomposedintosmallerjob—levelsubproblemsbyrelaxingprecedenceconstrainsandcapacityconstraints．AdynamicprogrammingWasdesignedtoprovidealleffectivesolutiontothesesubproblems．NumericalresultsforproblemswiⅡlupt060demonstratedthatthemethodgeneratesnearoptimal

7、solutionsinashortercomputationtime．Thentheprimalproblemwasdecomposedintosmallerbatch-levelsubproblemsbyrelaxingcapacityconstraints，dynamicprogrammingispresentedtosolvethem，andatwo—stageheuristicispresentedtoconstructafeasibleschedule．Testingr