基于改进蚁群算法的钢铁企业合同计划方法.doc

基于改进蚁群算法的钢铁企业合同计划方法 第17卷第4期xx年8月系Journal ofSystems&Management统管理学报Vol.17No.4Aug.xx:100522542 (xx)0420433206基于改进蚁群算法的钢铁企业合同计划方法张涛1,魏星1,张杰2,宋健海3(1.上海财经大学信息管理与工程学院,上海xx33;2.复旦大学计算机科学与工程系,上海市智能信息处理重点实验室,上海xx33;3.上海宝信软件股份有限公司,上海201900)【摘要】基于钢铁企业的合同计划管理要求,建立了以产能平衡和最小化拖期提前总惩罚为目标的多目标数学规划模型,综合考虑了工序的前序关系、工序的产能和库存的约束。 将生产合同与生产工序转换为节点图,从而将合同计划问题抽象成一种改进的旅行商问题。 根据模型和问题的特点设计了带交货期启发信息的蚁群算法,并以钢厂实际合同数据为例进行实验。 结果表明,改进蚁群算法获得的最好解和计算成本都比较令人满意,模型和算法是有效的。 关键词:钢铁企业;合同计划;蚁群算法;混合整数规划:C935:AOrder PlanningMethod Based on ImprovedAntColony Algorithm for theIron2steel PlantZ HA N G Tao1,W EIXing1,ZHANGYue2jie2,SON GJian2hai3(1.School ofInformation Managementand Engineering,Shanghai Universityof FinanceandEconomics,Shanghaixx33,China;2.Department ofComputer Scienceand Engineering,Shanghai KeyLaboratory ofIntelligent InformationProcessing,Fudan University,Shanghaixx33,China;3.Shanghai BaosightSoftware Co.Ltd,Shanghai201900,China)【Abstract】Basedonthe managementgoals of order planningof theiron2steel plants,a mixed integer pro2gramming modelfor theorder planning is constructed.The goalsinclude balancingproduction capacityandminimizing thetotal costof infringingcontracts.The constraintsinclude relationshipbetween differentprocesses,production capacityof machinesand inventorylevel.As thedata oforders andprocesses areputtogether to make apoint graph,the problemoforder planningistransferred intoan improvedTravelingSalesman Problem.An improvedant colonyalgorithm ispresented tosolve thismodel.The putationalresultsshow thatthe modeles upto theproduction processes,the satisfyingsolutions canbe obtainedwithinaeptable time.Key words:iron2steel plant;orderplanning;ant colonyalgorithm;mixedinteger programming:xx210205修订日期:xx203214基金项目:国家自然科学基金资助项目(70501018,60773124,70771020);国家重点社会科学基金资助项目(07AJ Y024);上海财经大学211项目作者简介:张涛 (19702),男,博士,副教授。 研究方向为生产计划与调度,智能优化方法,物流优化等。 E2mail:taozhangmail.shufe.在当今动态多变的市场环境和竞争压力下,钢铁企业既要满足外部起伏波动的客户需求,又要平衡企业内部的生产,高质量的生产计划成为生产管理中的迫切要求,而合同计划作为钢铁企业生产计划体系中的一个关键环节,更是吸引了众多学者的关注。 合同计划的研究历程可简单地分为2个阶段。 第1阶段,合同计划研究的重点是提高钢铁产量,降低生产成本。 Bowers等提出一个两阶段模型对合同在模铸工序进行排产,目标是减少模铸机的变动及库存量从而降低成本1。 Jayant结合合同计划和库存匹配,建立了最大化库存匹配重量和最小化余材的订单处理模型,将其抽象成具有指派约束和工艺约束的多背包问题,设计了基于网络流的启发式算法求解模型,并将结果与精确算法所得的结果进行了比较2。 随着按合同组织生产及准时制等管理模式的出现,合同计划的研究重点逐渐转移到合同的准时交货上,追求拖期惩罚或拖期提前总惩罚最小。 Redwine应用混合整数规划模型解决轧钢厂合同计划问题3,目标是最小化合同总拖期。 文献4中建立了钢厂合同计划编制的单目标整数规划模型,目标是合同拖期提前总惩罚最小,针对模型特点设计了基于可重复自然数编码和三变异算子的遗传算法。 文献5在合同计划研究的基础上综合考虑了拖期惩罚费用、设备能力均衡利用和库存成本等优化目标,建立多目标模型,并设计了求解模型的PSO算法。 Hwang研究了固定产能条件下炉次计划,提出树群算法进行求解6。 文献7中针对轧钢厂生产情况,提出了以天为单位的合同计划模型,并设计改进遗传算法求解模型。 本文通过对钢铁企业生产过程及市场环境的分析,在保证充分利用生产能力及按时交货的基础上,同时考虑物流平衡及降低中间库存成本,建立了合同计划的数学规划模型。 在合同计划建模的过程中,许多研究者将炼钢流程抽象成若干道工序,加工顺序确定,这样的合同计划问题是一般的FlowShop(FS)问题。 而在另一些文献中则考虑了工序中存在并行机的情况,这就变成更复杂的柔性FlowShop(FFS)问题。 对于这类复杂的组合优化问题,一般的精确算法难以对其进行求解,而元启发式算法在求解这类问题中表现出其优越性。 蚁群算法作为一种群体智能仿生优化算法,具有较强的鲁棒性和优良的分布式计算机制8,在求解车间作业调度问题(J SP)、二次分配问题(QAP)、车辆路径问题(VRP)等组合优化问题中9211,取得了一系列较好的实验结果,研究表明蚁群算法在求解复杂组合优化问题方面具有一定的优势。 因此,本文根据问题和模型的特点设计了改进的蚁群算法对模型进行求解。 1数学模型合同计划的目标是确保合同按时交货、生产线物流平衡、在制品或成品库存合理。 基本合同计划问题可概述如下:假设有N个合同,J道工序,每个合同的重量、交货期和加工路径已知,每个合同通过的工序相同,每道工序的产能一定,合同计划是在满足能力约束和工序前序关系的前提下,安排每个合同在每道工序的加工时间,使所有合同的提前和拖期总惩罚最小,每道工序的产能充分利用。 合同计划的编制是一项复杂的工程,在合同计划编制过程中要考虑以下因素: (1)物流平衡。 指在满足库存要求的前提下,尽可能大地发挥机组产能,满足合同交货。 (2)库存控制。 为了降低成本,需在保证后道工序能连续生产的条件下尽可能地降低库存。 (3)合同交货期。 若交货期提前或延后,都认为是没有按时交货,交货期没被满足。 (4)各工序在单位时间段内的生产能力及能力平衡。 剩余能力=生产总能力-已占用能力。 (5)合同生产中的时间单位。 本文中时间单位为半旬。 (6)生产目标。 满足交期,成本最小化或总完成时间最小。 在实际生产中,根据企业的战略目标及市场变化对不同的目标赋予不同的权重值。 本文考虑的目标为产能平衡和最小化合同的拖期和提前总惩罚值。 为了在满足客户需求的情况下尽可能地提高机组的产出量,本文建立了以产能平衡和提前/拖期总惩罚最小为目标的组合优化模型。 为了简化问题,本文作如下假设: (1)编制计划时将整个生产流程分成J道工序,每个订单通过的工序路径相同,在实际生产中,炼钢2连铸2热轧2冷轧为炼钢的主要工序,文中所提到的生产能力是面向每个工序而言。 (2)由于制造周期较短,目前从炼钢到冷轧的生产周期基本上是3周左右,而计划期的单位时间(半旬)相对较长,所以假定每个工序的生产时间不跨越阶段,即如果合同i在工序j的完成时间为t,则认为合同i在工序j的加工过程都落在阶段t内。 (3)每道工序计划期内单位时间的剩余生产能力已知。 由如上假设,建立模型如下:TJmin f1=t=1Nj=1Ejt-Ni=1w ijx ijt (1)min f2=i=1ei(i max(0,Ri-di-vi)+i max(0,di-ui-Ri) (2)s.t.Tt=1xijt=1 (3)434系统管理学报第17卷Ni=1xijtw ijEjt (4)S jo+MS jtij=t|xijt=1,t=1,2,TRi=tiJti(j-1)tijxijt0,1式中:i=1,2,N;j=1,2,J;t=1,2,T;N为合同总数;J为生产工序数;T为计划周期;di-ui,di+vi为合同交货期(以半旬为单位);i为合同i的拖期惩罚系数;i为合同i的提前惩罚系数;ei为合同i的实际合同量;Ejt为工序j在时段t内的剩余最大生产能力;Ejt为工序j在时段t内生产能力目标消耗;w ij为合同i在工序j的计划产出量;Ni=1(tq=1w ijx ijq-tq=1w i(j+1)xi(j+1)q (5) (6) (7) (8) (9)S j0为工序j在某时间段的期初库存;MS j为工序j中间库的最大限制库存;tij为第i个合同在第j道工序的加工半旬;Ri为合同i的完工半旬,即最后一道工序的通过时间(半旬);1,合同i在t时间段在工序j上加工0,否则其中:xijt为决策变量,i代表合同号,j代表工序号,txijt=代表时间段。 目标函数 (1)表示产能尽量平衡;目标函数 (2)表示所有合同的拖期和提前总惩罚值最小;约束 (3)表示每个合同必须通过每个工序且在每个工序的加工时间落在一个时段内;约束 (4)表示每个时间段内每个工序的合同生产量不能超过该工序的剩余生产能力;约束 (5)表示中间库存保持一个合适的水平,以尽可能低的成本保证生产的顺利进行;约束 (6)确定合同i在工序j的加工时间;约束 (7)确定合同i的完工半旬R i的值;约束 (8)表示合同i在工序j的加工半旬不小于在工序j-1的加工半旬;约束 (9)表示决策变量的取值范围。 2合同计划问题的求解策略2.1蚁群算法与ACO gb,min算法蚁群算法是从蚂蚁觅食行为中得到启发而构造出的一种模拟进化算法。 在觅食过程中,蚂蚁在所经过的路径上留下浓度与食物源质量成比例的信息素,并能够感知信息素的存在及其浓度,以此指导自己的运动方向,倾向于朝着信息素浓度高的方向移动。 蚂蚁个体之间通过这种信息的交流达到寻找食物和蚁穴之间最短路径的目的8。 Dorigo等基于蚁群觅食活动,首先提出了ACO的最早形式蚂蚁系统(Ant System,AS)于n个城市的TSP问题。 针对具有组合优化性质的极小化问题,Stuezle等提出了一种改进的蚁群算法ACO gb,min算法,12,13,它被成功地运用并从理论上证明了该算法具有收敛性对信息量设置了下界min,可有效地改善蚁群算法的全局收敛性能。 本文针对问题特点,对ACO gb,min算法做了进一步改进,加入合同交货期作为启发式信息,对模型进行求解。 2.2算法设计针对本文模型和问题的特点,将合同计划问题转化为一种特殊的具有路径选择的TSP问题,并设14。 该算法计了改进的蚁群算法。 首先,当生产合同进入生产系统后,每个合同对应的工序是固定的,如对于合同i,将它与所经过的工序组合,从而形成节点(i,1),(i,2),(i,J),将这些点看成有向图上蚂蚁要选择的节点。 同时,在蚂蚁选择节点时,通过候选表的控制可保证约束 (8)的满足,即工序加工顺序满足。 其次,将合同与工序的组合看作虚拟节点,蚂蚁移动时,根据工序的加工顺序及可选组情况,按启发式信息和信息素以轮盘赌方式依次选择节点。 蚂蚁从一个节点转移到另一个节点的转移可能性与工序的工艺路线、合同的交货期长短有关,约束 (3)得到满足。 在形成可行解后,根据各时间段(半旬)内每道工序的产能约束和剩余产能情况对解序列进行均衡分段(满足约束 (4),求出时间,再根据评价函数求出评价值,作为信息素更新的判断条件,促进下一次的迭代趋向最优解。 基于以上分析,本文采取如下策略处理目标 (1)和目标 (2),将其转换成如下评价函数:Nf(x)=1i=1ei(i max(0,Ri-di-vi)+i max(0,di-ui-Ri)+2Tt=1Jj=1Ejt-Ni=1w ijx ijt (10)式 (10)为提前及拖期总惩罚与产能平衡控制的加权函数,其中,1和2为常数。 2.2.1启发式信息的设计ACO gb,min算法中蚁群的转移完全依赖信息素,但考虑到初始解的生成及模型的目标,本文对算法进行改进,路径选择时加入交货期的启发式信息,使得蚂蚁转移时不仅仅依赖于信息素。 令(r,s)=1/ds,为启发式信息,ds为节点s对应合同距离交货期的剩余时间(转化为半534第4期张涛,等:基于改进蚁群算法的钢铁企业合同计划方法旬数)。 总信息的计算公式为total(r,s)=(r,s)(r,s)其中:(r,s)表示边(r,s)上的信息素浓度;表示信息素因子的权重;(r,s)为启发式信息;表示启发式信息因子的权重。 2.2.2伪随机概率选择规则采用伪随机概率选择规则,蚂蚁k在节点r选择节点s的规则由下式决定:arg max(r,s)(r,s)qq0j=Jelse (11)式中,q0(0q01)为参数;q为随机生成的概率值,q0,1;J k表示节点r的可选集,即所有未被访问的且满足工序加工顺序的点;J为根据概率转移式 (12)的选择规则。 在选择下一节点前随机生成q,如果qq0,则从点r到所有可选节点中找出(r,s)(r,s)值最大的点,作为下一个要选择的节点;如果qq0,则依据下式按概率来选择下一个节点:(r,s)(r,s)(r,s)0elsePk(r,s)=(r,s)sJ k(r) (12)式中,Pk(r,s)为蚂蚁k选择从节点r转移到节点s的概率。 当构造图上某一点的可选集J k(r)为空时,终止解的构造过程。 2.2.3信息素的更新当所有蚂蚁完成解的构造之后,对信息素进行更新。 更新规则如下:令xbest为算法到目前为止所发现的最好可行解,而x TR为算法在第TR次迭代所发现的最好可行解,f(xbest)和f(x TR分别表示与其相对应的目标函数。 当所有蚂蚁完成解的构造后,所有弧段的信息量将以的倍数挥发一部分,而算法到目前为止所发现的最好可行解xbest上的信息素得以增强。 信息素的更新过程可描述如下: (1)完成解的构造后,所有路径上的信息素以(0,0 (15)2.2.4初始解的构造根据合同交货期紧急优先的原则快速产生初始解,从第一道工序的节点开始,选择所有未被访问、交货期较短、产量满足工序要求的组合节点,直到访问完所有节点。 2.3算法流程 (1)初始化。 生成初始可行解,设置最大循环次数TRmax,设置初始信息素0和min、max,当前迭代次数TR=0(TR为循环次数计数)。 (2)蚂蚁开始巡游。 For k=1tomWhile(蚂蚁k的解的构造尚未完成)对每个蚂蚁k判断下一个要达到的节点s是否满足可行的约束条件:未被访问过。 节点s不属于蚂蚁k的禁忌表Mk;工序顺序满足,满足蚂蚁k的候选表;If(条件与满足)按照概率转移式 (11)和 (12)选择下一节点,并将该节点移动到蚂蚁个体的禁忌表中。 ElseEnd IfEnd WhileEndFor (3)寻找优解。 根据评价函数f(x)计算并记录本次迭代中产生优解的蚂蚁及其对应的路径; (4)信息素更新。 按照式 (13) (15)进行信息素的全局更新,迭代次数TRTR+1; (5)判断终止条件。 若TRTRmax,则转 (2); (6)输出最优解。 3计算结果为了测试模型和算法的优化效果及时间效率,本文以某著名钢铁公司两组合同为例,应用本文模型和算法对合同进行计划编制。 用C语言编程,在Pentium IVPC机上运行。 3.1参数分析设置蚂蚁个数m=15,=3,q0=0.75,在相邻两次循环搜索中最优解差别小于0.001条件下,对启式发因子进行实验。 反映蚂蚁在运动过程中所积累的信息量在指导蚁群搜索中的重要程度。 从图1可以看出,算法中对算法性能有较大的影响,634系统管理学报第17卷当过小时,算法收敛性差,且收敛的速度较慢;当过大时,相当于强化对启发式信息素在蚂蚁搜索过程中的重要性的重视度,全局性变弱,将导致局部最优路径上的正反馈作用很强,算法也会出现过早收敛现象。 实验结果表明,当1,4时,蚁群算法的求解性能较好。 图1与优化目标的关系本文设置m=15,=1,q0=0.75,在相邻两次循环搜索中最优解差别小于0.001条件下,对启发式因子进行了实验(见图2)。 图2与优化目标的关系期望启发式因子反映了启发式信息在指导蚁群搜索过程中的相对重要程度。 由图2可以看出,蚁群算法中对算法性能影响较大。 过小,将导致蚂蚁群体收敛性差,在这种情况下一般很难找到最优解;过大时,算法的收敛速度增快,但其全局性能有变差的趋势。 本算例中,当2.5,4.5时,蚁群算法的求解性能较好。 3.2实验分析设置参数如下:信息素因子=1,启发式因子=3,伪随机选择概率q0=0.75,信息素的挥发系数=0.2,信息素更新增加系数g(s)=3。 拖期惩罚系数i=3,提前惩罚系数i=1,评价函数加权系数1=2,2=1。 实验取钢铁企业主要加工工序:炼钢、连铸、热轧和冷轧,即J=4。 在蚂蚁个数的每种取值下算法运行20次,实验结果如表1所示。 由表1可见,当人工蚂蚁数较少,如m=5时,虽然算法运行速度比较快,但求解效果并不令人满意;当m=10或15时,算法所得的平均值和最小解相差较小,说明算法运行性能稳定,算法求解效果明表1实验测试结果m最好解最差解平均值所需时间/s52250503605202522912.43102151403313102399853.54152025302653402291694.22202161102867302329966.42显优于m=5时的求解效果;当m=20时,算法运行性能稳定,但运行时间比蚂蚁个数为10和15时分别多出81.4%和52.1%,但优化效果并没有明显改进。 为了检验本文设计算法的有效性,在m=15的情况下,以两组合同数据为实验实例,将本文设计的带交货期启发信息的ACO gb,min算法与原ACO gb,min算法做了实验比较,结果如表2所示。 表2不同算法测试结果比较算法合同数最好解最差解平均值所需时间/s改进ACOgb,min302025302653402291694.22ACOgb,min302274102786702462644.42改进ACOgb,min503102103987203410215.34ACOgb,min503532604021303844156.21由表2可见,由于加入了交货期的启发式信息,使得蚂蚁在搜索时所依赖的信息量更多,优化的效果更好。 在30个合同的情况下,最好解提高了10.9%;在50个合同情况下,最好解提高了12.2%。 计算时间也明显减少。 为了更直观的表示算法的收敛寻优过程,以30个合同数据为例,在各种的取值下,算法在迭代150次内收敛。 图3显示了算法的一次典型计算过程,横坐标表示运行代数,纵坐标表示目标函数值。 图3算法优化收敛图由实验结果可见: (1)加入交货期启发因子的ACO gb,min算法在循环150次左右后,计算结果即基本收敛; (2)计算结果比较稳定,最差结果比最好结果的相对偏差为23%,平均结果比最好结果的相对偏差不超过15%;734第4期张涛,等:基于改进蚁群算法的钢铁企业合同计划方法 (3)在算法的设计过程中,将工序产能平衡作为目标函数之一,并加入库存约束,使得目标函数值偏大,但更接近实际应用; (4)计算速度较快,计算时间可以接受。 4结语本文对合同计划编制问题进行了研究,根据钢铁企业在生产过程的的特点,将整个生产过程抽象成4道典型工序,这样合同计划问题就转化为FlowShop问题。 建立了合同计划的多目标数学规划模型,即产能平衡与最小化合同拖期提前总惩罚值,并把该问题转化为一种TSP问题。 设计了求解该问题的改进蚁群算法加入交货期启发因子的ACO gb,min算法,并以实际数据为算例进行了测试,获得了满意的结果,表明模型和算法是有效的。 参考文献:1Bowers MR,Kaplan LA.A two2phase modelforPlanning theproduction ofaluminum ingotJ.Eu2ropean Journalof OperationalResearch,1995,81:105-114.2Kalagnanam JR,Milind WDawade.the surplusin2ventory matchingproblem inthe processindustryJ.Operations Research,2000,48 (4):505-516.3Redwine ,Wismer DA.A mixedintegerpro2gramming modelfor schedulingorders ina steelmillJ.J ofOptimization Theoryand Applications,1974,14 (3):305-318.4张涛,王梦光,唐立新,等.钢厂合同计划的模型与算法J.控制理论与应用,2000,17 (5):711-715.5Liu SX,Tang JF.Order2planning modeland algo2rithmformanufacturing steelsheetsJ.Int JPro2duction Economics,xx,51 (5):1-14.6Hwang HC.Order consolidationfor batchprocess2ingJ.Journal ofCombinatorialOptimization,xx,9:121-138.7李耀华,宁树实.基于准时制的轧钢厂生产计划模型和算法J.控制工程,xx,11 (4):321-324.8Dorigo M,Maniezzo V,Colorni A.The antsystem:optimization bya colonyof cooperatingagentsJ.IEEE Transactionson SystemsMan andCyberics,Part2B,1996,26 (1):29-41.9Colorni A,Dorigo M,Maniezzo V,et al.Ant sys2tem forjob2shop schedulingJ.Belgian JournalofOperations Research,Statistics andComputer Sci2ence,1994,34 (1):39-53.10Maniezzo V,Colorni A.The antsystem appliedto thequadraticassignment problemJ.IEEE TransKnowl2edge