基于mo-ms的炼钢合同计划模型

基于mo-ms的炼钢合同计划模型

1mto-mts现代钢铁市场的竞争加剧，产品需求呈多品种、小批量化。为了满足这一需求特点，提高了服务质量，降低了生产成本，工商企业需要采用mto（允许生产）管理模式和规划方法。mto管理的概念是根据合同组织生产，考虑到生产的经济性，及时交付。减少低生产成本，提高产品竞争力。钢钢产品的生产管理中最重要的环节之一是合同计划。由于钢钢工具庞大，运营成本高，运营成本高，为了提高设备利用率，降低低产量生产成本已成为提高钢钢工具竞争力的重要因素。合同计划根据合同的交叉期、规格和质量以及各生产过程的生产能力，以及各节段的生产能力，根据各批均计算成本，提前沟通能力和设备利用率。合同计划近几年来成为钢铁行业生产管理领域的研究热点,目前关于钢厂合同计划的研究大多是基于MTO管理下的计划.文献建立了基于MTO管理系统的钢铁企业合同计划编制的整数规划模型,以最小提前、拖期惩罚为目标,提出用基于可重复自然数编码的遗传算法对模型进行求解.钢厂在决策时除了保证按时交货以外,还要考虑库存、设备利用率等成本因素,文献建立了多目标的合同计划模型(包括最小拖期、产能有效发挥、最小库存费用).但是,由于需求的不均衡,为了保证设备利用率,当客户合同不足时,需要按一定规则产生预测合同.由预测合同所生产的成品要作为库存应对未来的需求,这是基于MTS(maketostock)的生产方式.库存匹配是MTS生产方式下必不可少的环节,库存匹配工作将上一期预测合同所产生的库存,以及由于合同取消、变更产生的意外库存同本期要交货的合同进行匹配,提高了及时交货能力,降低了因库存造成的资金和场地的占用.很多学者对库存匹配问题进行了研究.Kalagnanam分别研究了成品匹配和半成品匹配,将其归结为多维背包问题,目标是库存匹配的最大化和匹配余料损失的最小.实际上钢厂为了既提高市场服务水平,又保证内部生产的经济性,往往采用MTO-MTS相结合的生产方式.在MTO-MTS生产方式下,合同的处理过程为:当接到下一期客户合同时,首先对合同进行库存匹配,即从库存中选择满足合同要求的成品直接交货.对于不能匹配的合同,再做生产计划,确定合同在各工序的生产时间.但库存匹配和生产计划之间存在着相互影响,比如,如果匹配过多,可能造成生产的最小批量达不到,增大生产成本.实际上企业需要在二者之间反复协调,不仅效率低,而且很难得到更为优化的方案.文献把整个生产流程抽象成一道工序,假设合同从原料投入到成品产出均在一个时间单位内完成,将库存匹配和生产计划联合考虑,解决了钢厂在非均匀需求下的库存和产能利用问题.本文试图在文献的基础上,对基于MTO-MTS的钢厂合同计划方法进行研究.将库存匹配和生产计划同时纳入多工序合同计划的考虑范围,即合同计划既确定部分合同选择库存余材匹配,又同时确定需生产的合同在各个工序的生产时间,建立了合同计划的整数规划数学模型;提出了对非可行解具有启发式修复功能的改进PSO算法进行求解;最后通过实验仿真来验证本文模型和算法的有效性.2合同规划的数学模型2.1合同计划序合同合同a在钢铁企业中,库存匹配包括成品匹配和半成品匹配,本文只考虑成品匹配,根据客户合同的要求,从库存中选择特征值符合条件的成品余材直接交货,特征值主要指成品的钢级、规格和单重等,余材的钢级不能低于合同的质量要求,规格要限定在合同规定的范围内,单重不能小于合同的最小定货量(设每个合同最多只能和一种余材匹配).生产计划根据合同的交货期、设备的产能约束等安排每个要生产的合同在各道工序的生产时间段,提高按时交货能力,降低单位生产费用.本文基于MTO-MTS生产模式,按照一体化管理的要求,以半旬为单位,掌握2个月(8个半旬)的合同,同时考虑库存匹配和生产计划两项工作来编制合同计划.考虑钢厂在计划期[1,T]内有N个合同要交货,合同在做计划时面临三种选择:库存匹配、车间生产、合同取消.同一个合同不能既选择余材匹配,又选择车间生产.库存匹配/生产计划的编制可以概述如下:假设有N个合同、J道工序、K种余材,每个合同的重量、交货期及其生产路径(通过的工序和在每道工序可使用的机器)、材质规格已知,每个合同通过的工序相同,每道工序的能力一定,合同计划是在满足能力约束和前序关系的前提下,安排每个合同的库存匹配或生产(在每道工序通过的时间),使所有合同的总惩罚最小.(每个合同必须通过所有工序,假设每个合同在同一时间段最多只可完成两道工序.)变量说明:N——合同总数;K——库存余材种类数;J——工序总数;T——计划展望期;ωi——合同i的需求量;Qk——余材k的库存数量;Ejt——工序j在时段t的产能;[ai,bi]——合同i的交货期窗口;αi——单位重量合同提前惩罚系数;βi——时间窗内单位重量合同交期惩罚系数;γi——单位重量合同拖期惩罚系数;ηi——单位重量合同被取消的惩罚系数;λ——期望最低负荷率系数,为(0,1)之间的值;vj——产能未充分发挥的惩罚系数;Ijo——第j道工序的期初库存量;Ijmax——第j道工序的最大库存量;定义决策变量如下:Yik={1,合同i选择同第k种余材匹配0‚否则Xijt={1,合同i在第j道⌶序的时段t内生产0‚否则Yik={1,0‚合同i选择同第k种余材匹配否则Xijt={1,0‚合同i在第j道⌶序的时段t内生产否则其中,i表示合同号,j表示工序号,t表示时间段,k表示余材号;i=1,⋯,Ν；j=1,⋯,Μ；t=1,⋯,Τ；k=1,⋯,Κ.i=1,⋯,N；j=1,⋯,M；t=1,⋯,T；k=1,⋯,K.决策时考虑的因素主要包括:1)合同选择余材匹配所产生的匹配费用.设合同i所要求的钢级为k′,实际匹配的余材的钢级为k,合同i选择库存余材匹配时产生的费用为余材按照合同的规格尺寸进行切削造成的余料损失σik;如果匹配的余材和合同i属于同一钢种,但钢级比合同要求的高,则产生以好充次的损失;如果余材和合同不是一个钢种,则不能匹配.匹配费用定义如下:Cik={σikk,k′属于同一钢种序列‚且k与k′钢级相同σik+hikgkk′k,k′属于同一钢种序列‚但k与k′钢级高∞k,k′不属于同一钢种序列其中:gkk′表示以好充次的单位费用,hik表示合同i和钢级为k的余材的匹配量.2)合同选择生产而产生的费用.为了降低生产成本,设备利用率不能太低,为此考虑工序j在时间t内的合同生产量小于最小批量要求时的惩罚费用,用单位重量惩罚系数vj表示.3)关于交货期的惩罚.合同交货期多为时间窗,比如按月交货、按周交货,在时间窗内交货都属于按时交货,但是现实中为了加快资金周转,钢厂都希望在时间窗内的交货时间尽量提前,为此,设计一个惩罚函数,保证时间窗内的交货时间尽量提前.如果合同交货期超过了时间窗,但还在可接受的交货时间范围内,则属于拖期交货,单位惩罚因子为γi.如果交货期在时间窗之前,属于提前交货,单位惩罚因子为αi.4)合同取消的惩罚.由于计划期内库存余材量及产能的限制,合同很可能即使在可以接受的拖期时间内也不能交货,因此需考虑合同取消的惩罚.5)MTO-MTS生产方式中合同预测的准确性对合同计划的计算结果影响较大,如果预测准确性欠佳,则模型的计算结果不是最优化的.为了减小预测准确性对计算结果的影响,避免预测合同与客户合同争抢资源,确保客户合同按期交货,可对预测合同设置相对较小的交期惩罚系数.2.2库存匹配约束的计算为同时优化配置库存余材和生产能力两类资源,建立模型如下:企业对不同目标函数的重视程度是不同的,一般来说,对合同取消惩罚、拖期惩罚等目标更重视.为了便于模型求解,权衡不同的目标函数,选取π1,…,π5为权重系数,转化为如下单目标函数:minf=min(π1f1+π2f2+π3f3+π4f4+π5f5)(6)Subjectto:Ν∑i=1Yikhik≤Qk‚k=1,2,⋯,Κ(7)Τ∑t=1XiJt+Κ∑k=1Yik≤1‚i=1,2,⋯,Ν(8)Ν∑i=1Xijtωi≤Ejt‚j=1,2,⋯,J；t=1,⋯,Τ(9)Τ∑t=1tXijt≤Τ∑t-1tXi(j+1)t‚j=1,⋯,J-1；i=1,2,⋯,Ν(10)J∑j=1Xijt≤2‚i=1,2,⋯,Ν；t=1,⋯,Τ(11)Ιj0+Ν∑i=1(t∑q=1ωiXijq-t∑q=1ωiXi(j+1)q)≤Ιjmax‚j=1,2,⋯,J-1；t=1,⋯,Τ(12)其中目标(1)表示交货时间在时间窗内的惩罚,J表示合同经过的最后一道工序;目标(2)表示提前拖期惩罚;目标(3)表示合同被取消的惩罚;目标(4)代表库存匹配费用;目标(5)代表工序产能未充分发挥的惩罚;约束(7)表示库存余材的数量限制,hik表示合同i匹配余材k的量,由于匹配会有余料损失,所以hik一般要比合同量ωi大一些;约束(8)表示合同不能既匹配又生产,且每个合同最多只能匹配一种余材;约束(9)表示工序的产能约束,工序在单位时间内的产量不能大于其产能,同时为了保证设备利用率,产量必须大于产能的某一百分比;约束(10)表示如果合同i经过一道工序,则必须经过其后道工序且合同在后一道工序的生产时间不能大于前一道工序的生产时间;约束(11)表示每个合同在同一时间段最多只可完成两道工序;约束(12)表示各工序在各时间段内的在制品库存不能超过库存限制.3pso算法求解策略该模型的求解属于NP难题,用精确算法难以求解.由于PSO算法具有群体智能搜索能力,而且算法本身的实现相对容易,所以本文采用PSO算法求解模型,并设计了对非可行解具有启发式修复功能的求解策略.3.1粒子群算法的进化方程PSO算法最早在1995年由JamesKennedy和RussellEberhart提出,其基本思想是基于对鸟类群体觅食行为的研究.每个粒子是一个n维向量,代表一个在n维求解空间中的解,如Xr=(xr1,xr2,…,xrn)代表粒子r的一个解.Vr=(vr1,vr2,…,vrn)代表粒子r的飞行速度,Pr=(pr1,pr2,…,prn)代表粒子r所经历过的最好位置(最好解),而Pb代表所有粒子中所经历过的最好位置,b为具有最好位置的粒子的编号.粒子群算法的进化方程可描述为:Vs+1r=w(s)Vsr+ρ1rs1(Ρsr-Xsr)+ρ2rs2(Ρsg-Xsr)(13)Xs+1r=Xsr+Vs+1r(14)其中,r=1,2,…,R,R代表颗粒群的规模,s为迭代的次数,w(s)为第s次迭代的惯性系数,ρ1为加速常数1,ρ2为加速常数2,分别调节颗粒飞向自身最好位置和飞向全局最好位置的步长,通常在[0,2]之间取值,rs1和rs2为[0,1]区间均匀分布的随机数.研究表明,较大的惯性系数有利于全局搜索,较小的惯性系数有利于局部搜索,因此本文设置一个较大的初始惯性系数,然后线性衰减,逐步提高局部搜索能力,线性衰减公式为:w(s)=0.9-sΜaxStep×0.5(15)为了保证算法的全局搜索能力,采用多种群粒子并行独立飞行,各个种群间周期性交换优秀的个体.3.2算法的设计3.2.1自然数编码编码由于模型中维数较多,计算复杂度过高,为了降低求解规模,对决策变量Yik和Xijk分别做如下处理:ci=k=Κ∑k=1kYik‚i=1,2,⋯,Νpij=Τ∑t=1tXijt‚t=1,2,⋯,Τ经过上述转换,降低了模型求解的复杂度.本文采用分段自然数编码方案,Lr=[cr1,cr2,…,crN;pr11,pr12,…,pr1J,…,prN1,…,prNJ],其中向量Lr代表第r个粒子各个维度的值,[cr1,cr2,…,crN]代表编码的前半段,表示库存匹配,其中cri(0≤r≤M,1≤n≤N)代表第i个合同和第cri种余材匹配;[pr11,pr12,…,pr1J,…,prN1,…,prNJ]代表编码的后半段,其中[pri1,pri2,…,priJ]代表后半段中的一个小段,表示合同i在工序1,…,J的生产时间,要么全为0(表示合同不生产),要么全大于0(表示合同生产).小段中prij(1≤j≤J)代表第i个合同在第j道工序的生产时间,如果prij=0,表明合同i不在工序j生产.cri和prij不能同时大于零,即合同不能既匹配又生产.3.2.2合同的生产时间由于合同不能既匹配又生产,为了满足约束(8),先产生编码的后半段,在[-T,T]之间随机产生一个整数作为pr11的值,如果产生的值在[-T,0]之间,则令pr11=0,同时令pr12=0,…,pr1J=0,表示合同不生产;如果pr11>0,则在[pr11,T]之间随机产生一个整数做为pr12的值,依次类推,直到产生pr1J的值,这是第一个合同在各工序的生产时间安排,同理产生其它合同在各个工序的生产时间.下面产生前半段编码,如果第i个合同不生产,则在[1,K]之间产生一个随机整数作为cri的值,表示第i个合同和第cri种余材匹配(若该种余材不能和合同i匹配,则重新生成cri,直到满足匹配约束);如果第i个合同生产,则令cri=0.于是产生了一个粒子.用同样的方式生成R个粒子,作为一个种群,共产生L个种群.按上面方式产生的粒子,能够满足约束(8)、(10)和(11).下面通过启发式修复,保证约束(7)、(9)和(12)的满足.计算每种库存余材的剩余可用量ΔQk=Qk-Q′k,其中Q′k代表余材k被匹配的量,如果ΔQk小于0,则按单位匹配费用从大到小,依次取消合同i和余材k的匹配,直到满足约束(7)为止.计算每道工序在每个时间段(半旬)内的剩余产能ΔEjt=Ejt-E′jt,其中E′jt代表工序j在时间t内的实际生产量,如果ΔEjt小于0,则在保证约束(9)和(10)的情况下,将工序j在时间t内的某个生产合同在该工序的生产时间提前或拖后,否则,将该合同的排产计划取消,直到满足工序的产能约束.判断约束(12)是否满足,如果不满足,则在保证约束(7)、(9)和(10)的情况下,随机改变某合同在该工序的生产时间,否则取消该合同的排产,直到满足约束(12).按照此规则产生L×R个初始可行解.3.2.3所有的值相同通过进化方程(13)、(14)的更新后,可能会产生某个粒子的某一维的值小于0,以及不满足某个约束的情况,需要对该粒子(非可行解)进行启发式修复,步骤为:步骤1判断编码中是否有超出取值范围的值,前半段编码各维的取值范围为[0,K],后半段编码各维的取值范围为[0,T].如果粒子前半段编码中cin<0,则令cin=0;如果cin>K,则令cin=K.如果后半段编码中小段[pin1,pin2,…,pinJ]里面有较多的值小于0,则令该段中所有值等于0,即该合同不生产;如果仅有少量的值小于0,将小于0的值随机转化为[1,T]内的值;如果prij>T,令prij=T.步骤2判断解是否满足约束(8),若合同i既匹配又生产,则计算ΔQk=Qk-Q′k,当ΔQk≥hik时,合同i选择匹配,否则选择生产.步骤3判断解是否满足前后工序约束(10)和(11),若粒子r不满足,则产生一个距离当前位置最近的满足约束(10)和(11)的解.从而在保证满足约束(10)和(11)的前提下,尽量减少对颗粒搜索位置的破坏.公式为:mind=J∑j=1|p′rij-prij|2(16)其中p′rij表示颗粒编码中调整后各个维度的值,prij表示颗粒各个维度的原值.计算策略为,将[pri1,pri2,…,priJ]中满足前后工序生产时间约束的尽可能多的prij值选出来,作为p′rij值,然后以1为单位步长逐步调整不满足前后工序生产时间约束的prij值,直到整个[pri1,pri2,…,priJ]满足约束(10)和(11),并计算距离d,取d值最小的[pri1,pri2,…,priJ].步骤4按照初始可行解中的启发式修复策略修复不满足约束(7),(9)和(12)的解.步骤5对于既未匹配又未生产的合同,按照ωi从大到小的步骤选择合同i,如果ΔQk>hik且Cik≠∞,则合同i选择和余材k匹配.否则,在满足约束(9)、(10)、(11)和(12)的条件下,随机安排合同i在各工序的生产时间,如果由于能力原因无法安排某合同的生产,则该合同取消.3.2.4更新历史最好解和惯性系数根据以上设计,算法的执行流程如下:1)初始化各参数.初始惯性系数w0=0.9,设置加速常数ρ1和ρ2,最大迭代次数MaxStep,粒子数R,种群数L等参数.2)每个种群随机生成R个可行颗粒,共生成L个种群.3)依(6)式计算目标函数值,并把每个颗粒的当前解初始化为各自的历史最好解,并将每个种群中最好的个体解初始化为种群最好解,把所有种群中最好的解初始化为全局最好解.4)Fors=1toMaxStepForl=1toLForr=1toR利用(13)、(14)式进行粒子移动;按非可行解的修复策略修复非可行解;EndFor根据(6)式计算目标函数值,更新Plb(种群l的最好解),Plr(种群l中个体r的历史最好解).EndFor更新Pb(全局最好解);Ifn%10=0,种群两两随机结合,各自选出30%的个体,相互交换Plr;n++(迭代次数统计);根据(15)更新惯性系数;EndFor5)结束,输出Pb等实验结果.4合同计划编制和数据集建立为了测试模型的可行性和算法的有效性,本文以某著名钢厂的合同计划实际数据为例,钢铁生产的主要工序有炼钢-连铸、热轧、冷轧等,本文假设所有要生产的合同都经过这三道工序,编制同时考虑匹配和生产的合同计划.算法用VC++.NET2003编程,运行在PentiumM(512M内存)PC机上.基本数据为:计划展望期T=8(以半旬为一个时间单位),工序数J=3(炼钢连铸、热轧、冷轧).本文选取三组数据进行分析,为简化,假设各工序各单位时段的产能不随时间变,如表1所示.4.1实验分析结果设置惩罚系数βi=0.02,αi=0.1,γi=1.0,ηi=20.0,产能利用率的单位惩罚vj=9,产能最低利用系数λ=0.7;匹配惩罚σik=0.2×ωi,以好充次惩罚gkk′=0.4.算法初始惯性系数设置为w0=0.9,然后按式(15)线性衰减至0.4.最大迭代次数MaxStep=500.为了使算法在运算时间和最优解上取得更满意的效果,用第二组合同数据(N=40)对算法的主要参数进行了实验分析.由于经典PSO迭代公式中加速常数取ρ1=ρ2=2.0,因此本文令加速常数ρ1+ρ2=4,对加速常数ρ1和ρ2、粒子群规模R进行了大量实验.对每组参数分别测试10次,统计最好的目标值BF、平均目标值AF、最差目标值WF,并记录最好BF下的库存匹配和排产结果,以及计算时间和平均收敛代数,结果如表2所示.图1给出了与表2对应的波动曲线.由表2和图1可见,当加速常数ρ1=2.5,ρ2=1.5时,避免了过早收敛而陷于局优的现象,算法平均收敛代数较大,结果最好,具有较好的寻优能力;从另一个角度看,当颗粒群规模取R=200时,算法求解能力最好;最好解出现在参数分别取ρ1=2.5,ρ2=1.5,R=200时,从求解能力和时间效率两方面考虑,本文取该值为算法对应的参数值.4.2算法的有效性分析在上文最佳参数设置下,对表1中的三组合同数据进行了实验,结果如表3所示.其中,最好目标值BF对应的库存匹配和合同计划结果如表4所示.从表3和表4的计算结果看出,在保证满足库存余材数量、中间库存和产能等紧约束的条件下,通过模型对合同匹配和排产的合理分配,使绝大多数合同都能按时交货.而且算法的执行在可以接受的运行时间内.图2给出