《MTSP模型及求解》word版.doc

热轧生产调度的多旅行商问题模型及求解摘要：传统对于热轧调度的研究,往往采用的是串行策略，实质是一种贪婪方法,可能导致局部最优。本文从全局最优观点提出能够同时产生一个班次中的M个轧制单元计划的并行策略，并且根据实际生产约束，可以热轧调度问题归结为多旅行商问题模型。为了求解，将MTSP变换为单旅行商问题模型，并适用改进遗传算法能有效搜索出最优解。关键词：热轧生产；调度；旅行商问题；改进遗传算法钢铁企业在实际编制热轧生产调度时，一般都是从合同订单预选池中挑选订单，依次编制出M个轧制计划单元1。这种策略模拟人工编制计划的思想，采用串行策略建立了单旅行商模型2。但是这种策略类似于贪婪方法，有可能陷入局部最优。一种合理的办法是并行方法，即从订单池中同时编制出M个轧制单元计划。并行方法可以归结为MTSP。1热轧生产调度的问题描述1.1问题描述 将全部订单看成一个个节点(相当于TSP中的城市)，一个轧制生产单元看成是经过一定数目节点的一条旅行路径，节点之间的距离(评价值)可定义为轧制规范的评价值（如相邻板坯的宽度、厚度、硬度等必须满足一定的约束条件），则热轧生产调度问题可归结为非对称旅行商模型3。由于热轧生产调度问题中的轧制单元计划是一条开放路径，每一个订单只能轧制一次。如果一个热轧调度包括M条轧制单元计划，则存在M个开放路径，并且任意两个轧制单元计划的开始和结束点的订单都不相同。这意味着任意两个轧制单元计划之间没有相同的点(订单)，开始订单也不确定，所以必须建立全新的模型。1.2 热轧调度问题进入标准MTSP问题的变换为了将热轧调度问题转换为MTSP问题,引进了M个虚拟节点(定单) 其编号为N+1,N+2,N+M。通过两个步骤：第一步是一个虚拟节点被引进热轧调度问题当中，要求所有的轧制单元计划都从这个虚拟节点出发。这个虚拟节点既是源点也是收点，这样就构成了闭合回路。第二步是M-1个附加节点被引进，这样可以保证M个闭合回路的形成，同时满足每个节点正好被访问一次，也就是每一个生产定单正好被轧制一次4。2 热轧生产调度的MTSP模型2.1 评价指标、变量和参数定义按照轧制工艺规范约束,相邻板坯之间的宽度、厚度和硬度等的变化越小，综合衡量的指标越优。因此，两节点之间的距离可定义为相邻轧件轧制参数的改变(跳跃)值；将相邻板坯之间的宽度、厚度和硬度跳跃值之和作为惩罚值，对超出轧制规范约束的赋予一个较大的惩罚值。对任一轧制计划单元，其优化目标可定义为：每个轧制单元的总评价惩罚值(相邻节点评价值之和)最小。假设有N个订单将在一个班次内的M个轧制单元计划进行轧制，这N个订单可以看成N个节点，M个轧制单元计划可以看成M个旅行商。引进M个虚拟节点，那么热轧计划排出问题可以建成MTSP模型。在数学模型建立上，借助单TSP模型的表达，即等价于一个旅行商访问N+M城市5。在建立模型之前,先将模型中用到的变量和参数定义如下：对于i, j1,N1如果订单j直接跟在订单i之后生产Xij= 0否则当iN+1,N+M, j1,N 1 如果订单j是第i-N个计划的第一个被轧制的Xij= 0否则当i1,N, jN+1,N+M1 如果订单i是第j-N个计划的最后一个被轧制的Xij= 0 否则Cij分别表示从订单i转换到订单j的惩罚,定义如下：Cij=ij|GjGj+1|+ij|WjWj+1|+ij|HjHj+1|其中:1if (|GjGj+1|) Gij= i, j1,N, ij if (|GjGj+1|) G 1if (|Wj-Wj+1|) Wij= i, j1,N, ijif (|Wj-Wj+1|)W 1 if (|Hj-Hj+1|) Hij= i, j1,N, ijif(|Hj-Hj+1|) H其中:Gj、Wj、Hj分别表示订单j的厚度、宽度和硬度;G、W、H分别为热轧轧制规范所允许的相邻板坯最大厚度、宽度与硬度跳跃值。Cij = 0, i1,N, jN+1,N+MCij = 0, iN+1,N+M, j1,NCij = , i, jN+1,N+MCij = , i, j1,N+M2.2数学模型在上述变量定义下,轧制批计划的数学模型可表述为：min (1)s. t. , i1,2,N+M (2), j1,2,N+M (3)0 Xij(Wj-Wi) W (4)|Xij(Gj-Gi)| G (5)|Xij(Hj-Hi)| H (6), S 1,N+M, 2|S|N+M-2 (7)Xij0,1, i, j1,N+M (8)目标函数式(1)使得总的惩罚最小;约束式(2)表示任务i之后轧制的任务有且只有一个；约束式(3)表示在订单j之前有且只有一个任务被轧制；约束式(4)(6)表示轧制规范，其中式(4)表示相邻板坯宽度跳跃约束，式(5)表示相邻板坯厚度跳跃约束，式(6)表示硬度等级跳跃约束；约束式(7)是为了避免在可行解中构成子回路而引进的约束；约束式(8)表示变量是0-1变量6。按照热轧生产约束，相邻板坯之间的宽度、厚度和硬度等变化越小，则综合衡量指标越优。因此两节点之间的距离可定义为相邻轧件的各轧制参数的改变(跳跃)值之和，以此作为相邻板坯之间的对轧制参数宽度、厚度和硬度跳跃值惩罚。相邻板坯之间的宽度、厚度和硬度跳跃值之和越大，则作为惩罚值也就越大，对应的轧制计划评价就越差。3 改进的遗传算法解决旅行商问题将热轧调度中的N种任务看成N个城市,把加工不同任务的转换惩罚看成是城市之间的距离，这样就把热轧生产问题归结为一个旅行商问题7。遗传算法（GA）是一种全新的随机搜索与优化算法，而标准遗传算法执行的效率不高，而且容易在局部最优解处收敛8。为了提高搜索的速度和效率，并针对对热轧调度的TSP问题模型，我们对标准遗传算法进行改进，得到了一种改进的遗传算法(MGA)。根据生物遗传规律,双亲血缘关系越远,子代优良的可能性越大。在两交换启发交叉规则中，由2个父代生成1个子代，当2个父代的链结构接近时，通过HGA交叉后，子代不会有很大的改善9。这里提出了一种改进遗传算法，称为三交换启发交叉方法（THGA），主要有2点改进：(1)通过增加交配的父代染色体的数量，由3个父代产生1个子代；(2)动态调整交叉和变异概率，从而降低了染色体近亲繁殖的可能,有效地控制了进化过程10。3.1三交换启发交叉方法的基本思想选3个参加交配的染色体作为父代，以8个城市（订单）为例来说明这一过程，其中dij由表1给出,父代染色体为：A = 3 2 1 4 8 7 6 5B = 2 4 6 8 1 3 5 7C = 8 7 5 6 4 3 2 1SUM1=42，SUM2=40，SUM3=46(SUM1，SUM2，SUM3分别为这3种排法所走的距离或惩罚费用总和) 随机选出初始城市（定单）j=1，Sj=3右转动,使3成为3父代的第1位置。A = 3 2 1 4 8 7 6 5B = 3 5 7 2 4 6 8 1C = 3 2 1 8 7 5 6 4由于d(3,2)d(3,5)，所以有：A =5 2 1 4 8 7 6B =5 7 2 4 6 8 1C =5 6 4 2 1 8 7由此规则计算可得：O =3 5 7 6 8 4 2 1SUM0 = 24(SUM0为3个父代所产生的子代所走的距离或惩罚费用总和)，显然SUM0远远小于SUM1，SUM2和SUM3。123456781031127563250741812335031649471907895586610135161473205279788710181211387160表1：8个城市（订单）之间的距离（跳变惩罚）3.2交叉概率的变参方法设K=1，则Pc的表达式为：当f f时， Pc= K (1)当ff时， Pc= K (2)其中：f=SUM1+SUM2+SUM3 / 3 (3)f当前交叉的3个父代的平均值；ffit为当前代中最短的路程值；f当前代的平均值;SUM1,SUM2,SUM3分别为未交叉的3个父代的总距离或惩罚费用。Pc变参的理由是当某一代中所有生成的子代的值很接近时，显然，结果可能在局部最优处徘徊，所以必须增大Pc，以避免局部最优。当3个父代的平均值(设为f)和当前代中最优值相差较大时，说明这3个父代和当前最佳值还有很大差距，需要通过交换产生更好的排序结果。3.3变异概率的变参方法变异概率Pm的变参形式表达如下：当ff, Pm = K2(fbest-f)/(fbest-f) (4)当f f, Pm = K4 (5)其中K2=0.5，K4=0.5；fbest为当前代中最佳值；f为当前代的平均值；f当要进行变异的父代。这是为了防止局部最优,随着f的变化设置不同的变异概率。当fbest与 f 很接近时，说明某一代中所有的值可能在局部最优附近徘徊，所以让Pm较大,以摆脱局部最优。当fbest与 f相差很远时，说明f离最优值还相差很大，所以要增大变异概率。4结论通过以实际生产数据为例,进行仿真，结果表明，所给出的算法非常有效。下面是考虑120个订单（城市）的TSP问题，将本文提出的改进的遗传算法与目前较好的两种启发式交叉方法(GX和GSX)进行比较，结果如表2所示：算法交叉方法变异方法迭代次数最优解1GX逆序法100016729.452GSX2-OPT100015689.633三交叉改进启发式100015274.98表2：实 验 结 果由试验结果可知：当采用算法1时，收敛速度慢相当慢，而且解的质量不高。而方法2要稍优于方法l。方法3实际上在756代时便已经达到了最优解，因此可见当采用改进的遗传算法不论是收敛速度和解的质量都是最好的11。对于热轧调度问题首先建立了MTSP模型，与一般单TSP模型不同的是，它能够同时安排多个轧制单元计划，符合现场实际情况。再将MTSP模型转化为单TSP模型，在求解上，用改进遗传算法，即三交换启发交叉变参算法，可以高效率搜索出最优解进行求解。结果证明应用TSP问题的改进遗传算法能够有效地解决轧钢厂生产调度问题。参考文献：1 金光熙,孙福兴,柏世彬,等.宝钢的生产管理.北京:冶金工业出版社,1994：104130.2 唐立新.CIMS下生产批量计划理论及其应用.北京:科学出版社,1999.11512.3 TANG Li-xin, LIU Ji-yin, RONG Ai-ying,et al. Multiple traveling salesman problem model for hot rolling scheduling in Shanghai Baoshan iron & steel complex J.European Journal of Operational Research,2000,124(2): 267-282.4 唐立新.热轧调度并行处理策略的多旅行商模型J.东北大学学报,1999,20(2):148150.5 Lenstra J K,Rinnooy Kan AHG. Some simple applications of the traveling salesman problem. Operational Research Quarterly, 1975, 26.717733.6 黄可为; 汪定伟. 热轧计划中的多旅行商问题及其计算方法J计算机应用研究, 2007（07）7 唐立新.轧钢厂的精轧工序轧制批量调度的优化