资源描述:
《热轧批量计划问题的分枝定界算法研究》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、热轧批量计划问题的分枝定界算法研究摘要生产调度是生产管理的核心内容和关键技术,其任务是在企业车间有限的资源约束下,确定工件在相关设备上的加工顺序和加工时间,以保证所选定的生产目标最优。科学地制定生产调度方案,对于提高企业资源利用率、提高产品质量、缩短交货期、降低生产成本从而提高企业在市场经济中的竞争力具有重要的意义。本文以钢铁生产中的热轧带钢过程的实际调度问题为背景,对热轧带钢生产流程工艺、热轧计划的编制依据和工艺约束进行了阐述。本文在分析了热轧生产批量的通用模型的基础上,选择适用于热轧带钢轧制批量计划问题的多旅
2、行商问题模型。该模型考虑轧制计划类型、轧件的宽度、厚度和硬度的限制,目标是追求总的相邻的带钢的宽度、厚度和硬度的限制惩罚最小,带钢的排序最优。针对该模型,提出了一种基于深度和广度方向混合搜索的启发式策略的分枝定界算法,该算法采取有阈值的深度优先加广度方向加权随机搜索的策略确定分枝节点,运用模拟退火的思想确定中断深度优先搜索的阈值,通过求解附加弧段约束的分配问题来定下界,通过消除子环的修补算法来确定上界,从而有效综合了确定性方法的准确性和启发式方法的快速性。将该算法用于宝钢热轧生产过程数据进行调度的仿真,表现出较高
3、的效率。此外将该算法用于求解TSPLib中的所有ATSP问题,其结果表明了其对于求解一般大规模非对称TSP问题的可行性和高效性。由于TSP是很多调度问题的基本模型,该算法在调度优化领域有广泛的应用前景。关键词:热轧带钢,轧制计划,旅行商问题,分枝定界算法,修补算法,阈值BRANCH-BOUNDALGORIHMFORHOTSTRIPROLLINGBATCHPLANNINGPROBLEMABSTRACTProductionscheduling,aimsatreachingtheoptimizationofthesel
4、ectedproductiontargetsunderallkindsofrestrictionssuchaslimitedresource,strictdeliverydate,unchangeableprocessingsequenceetc.,playsakeyroleinproductionmanagement.Goodschedulingwillbringaboutmoreefficientemployofresource,improvedproductquality,reducedcost,short
5、erdeliveringperiodandsoon,whichsignificantlycontributetoraisingtheenterprisecompetitivenessinmarketeconomy.TheHotStripMillProductionSchedulingProblem,whicharisesinthesteelindustrywhenschedulingsteelcoilproduction,isstudiedinthethesis.Theproductionprocessisfir
6、stlyspecified.ItcanbemodeledasageneralizationoftheMultipleTravelingSalesmanProblem.Rollplantype,thelargestlengthofwarmstripsandstaplestrips,width,thicknessandrigidityofhotstripareconsideredintheMTSPmodel,withtheobjectivetominimizethepunishmentvalueofwidth,thi
7、cknessandrigidityofadjacenthotrollingstripandmakesureoptimalprocessorderofhotrollingstripsonthefinishrollingmill.AnintegrationapproachbasedonheuristicstrategiesandBranch-BoundalgorithmisproposedforsolvingMTSP.Inthismethod,associatedwitheachnodeofthebranch-dec
8、isiontree,aparametricsolutionoftherelaxedassignmentproblemandafeasiblesolutionobtainedbypatchingalgorithmareusedtotightenthelowerandupperbound;Ahueristicstrategythatmixthresholdconstraint