应用改进遗传算法求解炼钢连铸生产调度问题

D0I:10.13374/i.issnl100103x.2010.09.023 第32卷第9期 北京科技大学学报 Vo132N99 2010年9月 Journal ofUniversity of Science and Technobgy Bejjing S2010 应用改进遗传算法求解炼钢连铸生产调度问题 汪红兵》徐安军)姚琳) 田乃媛杜曦) 1)北京科技大学倍息工程学院，北京1000832)北京科技大学治金与生态工程学院，北京100083 3)安徽大学计算机科学与技术学院，合肥230601 摘要炼钢连铸制造流程是一个复杂的多阶段、多产品生产过程，其生产调度问题可建模为车间调度问题.提出一个改进 遗传算法求解炼钢连铸生产调度问题.改进包括三个方面：基于排序的适应度分配、基于排序的工件过滤交叉算子和基于指 数关系的变异率曲线.经24个bm©ma的比较测试表明，改进遗传算法比传统遗传算法的寻优能力更强.通过l6个生产 计划和6个处理工序的炼钢连铸生产调度实例计算结果表明，改进遗传算法是有效的. 关键词钢铁企业：炼钢：连铸：车间调度：遗传算法 分类号TF089F273 Appling an mproved genetic a lgoritlm for soving the production scheduling problem of steem aking and con tinuous casting WANGHong-bing).XU An jre)YAO Lin.TIAN Nai-yuar?)DUX 1)Shoolof hpmaton Engneerng Universit of Scence and Techrokgy Beijing Beijng 100083 Chha 2)SchoolofMemlugal ad Ecopgical Engneering Unieri of Scerce and Technopgy Beijng Beijirg 100083 Chna 3)ShoolofCompuerScience and Technokgy AnhuiUniversity Hefei230601 China A BSTRACT The m anufacturing flow of steemaking and contnuous casting is a comp ex multiple-Phase and multp le product poduc tion process The producton schedu lng probkm in hismanufacturng fpw can be seen as a pb shop scheduling problem An mproved genetic aleritm pr soMing this problem was proposed and he i proved aspects wee as pllows rank-based fitness ass grment pb filer order based crossover operapr and muntin rate according p an expanential functon relatpn Twenty pur benclm aks were comparatively investgated and the result shows that the i proved genetic algority has a beter capacity of seeking optium han a tra d itional genetic algorithm The productian schedulng problem of steem akng and con tinuous castng with sixteen plans and six proce dureswas compued usng the mproved genetic algorithm It is shown hat the a goritlm is efective KEY WORDS iron and steel plants steem ak ng contnuous casting pb shop scheduling genetic agoritlms 炼钢连铸制造流程是一个复杂的多阶段、多产 步算法：朱宝琳和于海斌)提出应用拉格朗日松弛 品生产过程.钢水从炼钢经精炼到连铸，不同钢种 法求解炼钢、连铸和热轧一体化生产调度模型；T皿g 的产品需要不同的精炼处理形成了不同的工艺路 等应用数学规划方法求解炼钢连铸调度问题； 径，炼钢连铸作为钢铁企业的核心生产环节，其生 A tighehchian等提出一种改进蚁群算法求解炼钢 产调度问题一直吸引众多学者的关注. 连铸调度问题. 庞新富等基于案例推理和人机交互的方法 近年来，各种进化算法，如禁忌算法、蚁群算法 开发炼钢连铸动态智能调度系统：冯振军等结合 和遗传算法，由于其寻优能力强、可求解问题的规模 启发式方法和线性规划方法提出炼钢连铸调度的两 大等特点在各种生产调度问题中得到了越来越广泛 收稿日期：2009-10-21 基金项目：“十一五”国家科技支撑计划重大项目“新一代可循环钢铁流程工艺技术”(N92006BA0307)的子课题：新一代钢厂精准设计技 术和流程动态优化研究 作者简介：汪红兵(1978-)，男，讲师，博士，Ema1 wanghon吗n816@16位cm

第 32卷 第 9期 2010年 9月 北 京 科 技 大 学 学 报 JournalofUniversityofScienceandTechnologyBeijing Vol.32 No.9 Sep.2010 应用改进遗传算法求解炼钢连铸生产调度问题 汪红兵 1) 徐安军 2) 姚 琳 1 ) 田乃媛 2) 杜 曦 3 ) 1) 北京科技大学信息工程学院, 北京 100083 2) 北京科技大学冶金与生态工程学院, 北京 100083 3) 安徽大学计算机科学与技术学院, 合肥 230601 摘 要 炼钢连铸制造流程是一个复杂的多阶段、多产品生产过程, 其生产调度问题可建模为车间调度问题.提出一个改进 遗传算法求解炼钢连铸生产调度问题.改进包括三个方面:基于排序的适应度分配、基于排序的工件过滤交叉算子和基于指 数关系的变异率曲线 .经 24个 benchmark的比较测试表明, 改进遗传算法比传统遗传算法的寻优能力更强.通过 16 个生产 计划和 6个处理工序的炼钢连铸生产调度实例计算结果表明, 改进遗传算法是有效的. 关键词 钢铁企业;炼钢;连铸;车间调度;遗传算法 分类号 TF089;F273 Applinganimprovedgeneticalgorithm forsolvingtheproductionscheduling problemofsteelmakingandcontinuouscasting WANGHong-bing1) , XUAn-jun2) , YAOLin1) , TIANNai-yuan2) , DUXi3) 1) SchoolofInformationEngineering, UniversityofScienceandTechnologyBeijing, Beijing100083, China 2) SchoolofMetallurgicalandEcologicalEngineering, UniversityofScienceandTechnologyBeijing, Beijing100083, China 3) SchoolofComputerScienceandTechnology, AnhuiUniversity, Hefei230601, China ABSTRACT Themanufacturingflowofsteelmakingandcontinuouscastingisacomplexmultiple-phaseandmultiple-productproduc￾tionprocess.Theproductionschedulingprobleminthismanufacturingflowcanbeseenasajobshopschedulingproblem.Animproved geneticalgorithmforsolvingthisproblemwasproposedandtheimprovedaspectswereasfollows:rank-basedfitnessassignment, job filterorder-basedcrossoveroperator, andmutationrateaccordingtoanexponentialfunctionrelation.Twenty-fourbenchmarkswere comparativelyinvestigatedandtheresultshowsthattheimprovedgeneticalgorithmhasabettercapacityofseekingoptimumthanatra￾ditionalgeneticalgorithm.Theproductionschedulingproblemofsteelmakingandcontinuouscastingwithsixteenplansandsixproce￾dureswascomputedusingtheimprovedgeneticalgorithm.Itisshownthatthealgorithmiseffective. KEYWORDS ironandsteelplants;steelmaking;continuouscasting;jobshopscheduling;geneticalgorithms 收稿日期:2009--10--21 基金项目:“十一五”国家科技支撑计划重大项目“新一代可循环钢铁流程工艺技术” ( No.2006BAE03A07)的子课题:新一代钢厂精准设计技 术和流程动态优化研究 作者简介:汪红兵 ( 1978— ), 男, 讲师, 博士, E-mail:wanghongbing0816@163.com 炼钢连铸制造流程是一个复杂的多阶段 、多产 品生产过程 .钢水从炼钢经精炼到连铸, 不同钢种 的产品需要不同的精炼处理形成了不同的工艺路 径 .炼钢连铸作为钢铁企业的核心生产环节, 其生 产调度问题一直吸引众多学者的关注 . 庞新富等 [ 1] 基于案例推理和人机交互的方法 开发炼钢连铸动态智能调度系统;冯振军等 [ 2] 结合 启发式方法和线性规划方法提出炼钢连铸调度的两 步算法;朱宝琳和于海斌 [ 3] 提出应用拉格朗日松弛 法求解炼钢、连铸和热轧一体化生产调度模型 ;Tang 等 [ 4]应用数学规划方法求解炼钢连铸调度问题; Atighehchian等 [ 5]提出一种改进蚁群算法求解炼钢 连铸调度问题 . 近年来, 各种进化算法, 如禁忌算法、蚁群算法 和遗传算法, 由于其寻优能力强、可求解问题的规模 大等特点在各种生产调度问题中得到了越来越广泛 DOI :10.13374/j .issn1001 -053x.2010.09.023

第9期 汪红兵等：应用改进遗传算法求解炼钢连铸生产调度问题 ·1233° 的应用.其中，遗传算法是应用最为广泛的一种进 1算法设计 化算法. 遗传算法(ene tic a gorit四GA)是一类借鉴 设计一个遗传算法，通常要考虑问题编码与解 生物界自然选择和自然遗传机制的高度并行、随机 码、选择算子、交叉算子和变异算子等各个方面. 和自适应搜索算法.该算法是一种模仿自然界生物 1.1问题描述 进化过程中“物竞天择，适者生存”的原理而进行的 一个典型的JSS?就是研究将个工件分配在 一种多参数、多群体同时优化方法，其主要特点是群 m怡机器上加工的组合排序问题.对于炼钢连铸生 体搜索策略和群体中个体之间的信息交换，搜索不 产调度来说。就是研究将n个生产计划分配在m台 依赖于梯度信息.尤其适用于处理传统搜索方法难 处理工序上的组合排序问题，其目标是最小化生产 以解决的复杂和非线性问题 计划的最大完工时间(m业espa.设C为生产计划 实际上，炼钢连铸生产调度可归属为工件工厂 的完工时间，=12；则调度目标表示为 调度问题(b shop scheduling problem JSSP.所谓 m in m ax C)). SS就是研究将n个工件在m台机器上加工的组 1.2编码与解码 合排序问题，每个工件包含一系列必须按照指定顺 编码是完成问题的状态空间到遗传算法的码空 序加工的工序，而每道工序的加工又必须在指定的 间的映射，解码是完成遗传算法的码空间到问题的 机器上进行，要求在满足某些约束条件下确定各个 状态空间的映射.编码在一定程度上决定了各种算 工序的开始和结束时间，并使得加工性能指标达到 子的设计实现，是影响算法性能与效率的重要因素. 最优.这些性能指标可以是成本相关、也可以是时 本文采用基于工序的表达法.假设一个染色体 间相关一般是最小完工时间(makesp码.按照 编码为[13223↓321]，其中1表示工件12 JSSP的定义，炼钢连铸生产调度问题就是将给定的 表示工件23表示工件3该数码=123出现的 个生产计划在m台处理工序上进行的组合排序 次数代表工件的第道工序.例如，第1个1表 问题. 示工件1的第1道工序，最后一个1表示工件1的 由于炼钢连铸生产调度问题可归属为SS则 第3道工序.使用O表示第个工件的第道工序， SSP领域的众多研究成果就可以用来求解炼钢连 则上述染色体解码为Q,9,9,O2Q292 Q,9,Q.再结合每个操作所对应的具体加工机 铸生产调度问题.这里，主要关注遗传算法在SSP 的应用.周辉仁等”提出一种基于矩阵编码的遗传 器，即可以计算该染色体的所对应的完工时间，就完 成染色体的解码过程 算法求解工件车间调度问题，算法取得了较好的收 1.3选择算子 敛速度：张国辉等设计一种全局搜索、局部搜索 目前，大多数遗传算法的选择算子都采用轮盘 和随机产生相结合的初始化方法，提高种群初始解 赌选择法，选择概率的确定根据适应度进行比例分 的质量，加快遗传算法的收敛速度：王小平和曹立 配.但是，这种按比例分配容易导致早熟收敛现 明[9、Xg等0提出自适应遗传算法，前者将算法 象).本文采用基于排序的适应度分配法，其计算 中的交叉率和变异率参数设计为个体适应度和种群 公式如下： 最大适应度之差的线性关系，而后者则将算法中的 Fitness Pos= 交叉率和变异率参数设计为个体适应度和种群最大 2-SP+2(SP-1)(Pos1)/(Nd-1). 适应度之差的指数关系，在算法的求解效率上均取 式中，Nd为种群中个体数目；Pos为个体在种群中 得了一定的成果；Tsujmuray等和Chen等提 的排序位置；P为选择压力，一般取[1.Q2.0],这 出一种部分调度交叉算子，考虑部分调度为自然构 里取2.0例如，种群的适应度列向量为[214 成块，使得后代保留这些块，部分调度使用调度中起 3],则基于排序的适应度分配法的适应度列向量为 始位置和最终位置相同的工件来识别. [1.33332000000.6667]. 本文的工作是在遗传算法的自适应性方面、交 此外，在选择算子的设计上，还考虑采用优良个 叉算子方面，结合基于排序的适应度分配对传统遗 体保留的原则，即优良个体直接进入到后代种群，不 传算法的改进.实验验证了算法的改进效果，并成 参与交叉运算和变异运算 功应用改进遗传算法于炼钢连铸生产调度问题的 1.4交叉算子 求解 传统遗传算法中使用的交叉算子常见的有单点

第 9期 汪红兵等:应用改进遗传算法求解炼钢连铸生产调度问题 的应用 .其中, 遗传算法是应用最为广泛的一种进 化算法 . 遗传算法 ( geneticalgorithm, GA)是一类借鉴 生物界自然选择和自然遗传机制的高度并行 、随机 和自适应搜索算法.该算法是一种模仿自然界生物 进化过程中 “物竞天择, 适者生存 ”的原理而进行的 一种多参数 、多群体同时优化方法, 其主要特点是群 体搜索策略和群体中个体之间的信息交换, 搜索不 依赖于梯度信息 .尤其适用于处理传统搜索方法难 以解决的复杂和非线性问题 [ 6] . 实际上, 炼钢连铸生产调度可归属为工件工厂 调度问题 ( jobshopschedulingproblem, JSSP) .所谓 JSSP, 就是研究将 n个工件在 m台机器上加工的组 合排序问题, 每个工件包含一系列必须按照指定顺 序加工的工序, 而每道工序的加工又必须在指定的 机器上进行, 要求在满足某些约束条件下确定各个 工序的开始和结束时间, 并使得加工性能指标达到 最优.这些性能指标可以是成本相关 、也可以是时 间相关, 一般是最小完工时间 ( makespan) .按照 JSSP的定义, 炼钢连铸生产调度问题就是将给定的 n个生产计划在 m台处理工序上进行的组合排序 问题. 由于炼钢连铸生产调度问题可归属为 JSSP, 则 JSSP领域的众多研究成果就可以用来求解炼钢连 铸生产调度问题.这里, 主要关注遗传算法在 JSSP 的应用 .周辉仁等 [ 7]提出一种基于矩阵编码的遗传 算法求解工件车间调度问题, 算法取得了较好的收 敛速度 ;张国辉等 [ 8] 设计一种全局搜索 、局部搜索 和随机产生相结合的初始化方法, 提高种群初始解 的质量, 加快遗传算法的收敛速度;王小平和曹立 明 [ 9] 、Xing等 [ 10] 提出自适应遗传算法, 前者将算法 中的交叉率和变异率参数设计为个体适应度和种群 最大适应度之差的线性关系, 而后者则将算法中的 交叉率和变异率参数设计为个体适应度和种群最大 适应度之差的指数关系, 在算法的求解效率上均取 得了一定的成果;Tsujimuray等 [ 11] 和 Cheng等 [ 12]提 出一种部分调度交叉算子, 考虑部分调度为自然构 成块, 使得后代保留这些块, 部分调度使用调度中起 始位置和最终位置相同的工件来识别 . 本文的工作是在遗传算法的自适应性方面 、交 叉算子方面, 结合基于排序的适应度分配对传统遗 传算法的改进.实验验证了算法的改进效果, 并成 功应用改进遗传算法于炼钢连铸生产调度问题的 求解. 1 算法设计 设计一个遗传算法, 通常要考虑问题编码与解 码、选择算子、交叉算子和变异算子等各个方面. 1.1 问题描述 一个典型的 JSSP, 就是研究将 n个工件分配在 m台机器上加工的组合排序问题 .对于炼钢连铸生 产调度来说, 就是研究将 n个生产计划分配在 m台 处理工序上的组合排序问题, 其目标是最小化生产 计划的最大完工时间 (makespan).设 Ci为生产计划 i的完工时间, i=1, 2, …, n, 则调度目标表示为 T=min{max(Ci) }. 1.2 编码与解码 编码是完成问题的状态空间到遗传算法的码空 间的映射, 解码是完成遗传算法的码空间到问题的 状态空间的映射.编码在一定程度上决定了各种算 子的设计实现, 是影响算法性能与效率的重要因素. 本文采用基于工序的表达法 .假设一个染色体 编码为[ 1, 3, 2, 2, 3, 1, 3, 2, 1], 其中 1表示工件 1, 2 表示工件 2, 3表示工件 3.该数码 i=1, 2, 3出现的 次数 j代表工件 i的第 j道工序 .例如, 第 1个 1表 示工件 1的第 1道工序, 最后一个 1表示工件 1的 第 3道工序 .使用 Oij表示第 i个工件的第 j道工序, 则上述染色体解码为 O11, O31, O21, O22, O32, O12, O33, O23, O13.再结合每个操作所对应的具体加工机 器, 即可以计算该染色体的所对应的完工时间, 就完 成染色体的解码过程. 1.3 选择算子 目前, 大多数遗传算法的选择算子都采用轮盘 赌选择法, 选择概率的确定根据适应度进行比例分 配.但是, 这种按比例分配容易导致早熟收敛现 象 [ 13] .本文采用基于排序的适应度分配法, 其计算 公式如下 : Fitness( Pos) = 2 -SP+2( SP-1) ( Pos-1) /( Nind-1) . 式中, Nind为种群中个体数目 ;Pos为个体在种群中 的排序位置;SP为选择压力, 一般取 [ 1.0, 2.0], 这 里取 2.0.例如, 种群的适应度列向量为 [ 2, 1, 4, 3], 则基于排序的适应度分配法的适应度列向量为 [ 1.333 3, 2.000 0, 0, 0.666 7] . 此外, 在选择算子的设计上, 还考虑采用优良个 体保留的原则, 即优良个体直接进入到后代种群, 不 参与交叉运算和变异运算. 1.4 交叉算子 传统遗传算法中使用的交叉算子常见的有单点 · 1233·

。1234 北京科技大学学报 第32卷 交叉、多点交叉和均匀交叉以及基于排序的均匀交 为个体适应度和种群最大适应度之差的线性关系， 叉.对于单点交叉、多点交叉和均匀交叉，由于产生 而文献[10]则提出将算法中的交叉率和变异率参 子代种群个体中可能存在非法的调度方案，需要一 数设计为个体适应度和种群最大适应度之差的指数 些额外的修补技术，导致算法的效率较低.基于排 关系，并且验证了这种指数关系取得了较好的效果. 序的均匀交叉虽然能满足工件车间调度问题的求 对于SSP设T为个体的完工时间，T和 解，但模板中0和1是均匀产生的，使得在交叉过程 分别为种群中的最大完工时间和最小完工时间. 中难于保留较长的模式，而这对于算法的收敛是非 当个体的完工时间越靠近T则其变异率应该越 常不利的. 大，而当个体的完工时间越靠近m其变异率应该 本文采用的交叉算子就是在基于排序的均匀交 越小，本文采用的基于指数关系的变异率曲线是对 叉算子的基础上，改进模板中0和1的产生方式 文献[10的改进，其形式为 针对工件工厂调度问题，采用工件集合过滤方式来 MutE 承担上述模板的作用.因此，称本文采用的交叉算 MaMut e hr T e-1 Ta≠Tn 子为基于排序的工件过滤交叉算子，其计算过程如 下所示 MaxMutr Tax-m h 设一个四工件三机器的SS某次迭代中两个 式中，MaMu为最大变异率.与文献[10]所不同 个体的编码为 的是，曲线适应于种群中的所有个体，而不是仅仅适 =(132312132444), 用于均值以上的个体，而且在曲线的具体形式上也 P2=(112433412432). 是不同的. 随机产生一个工件编号的排列Num=(23l 2算法实现 4),并产生两个不同的随机整数P09和P0②根据 Po和Po2从Nu中取出相应的工件编号集合. 改进遗传算法的执行过程与传统遗传算法的执 例如，当P09=2P02=3时，取出的工件集合为 行过程大致相同.其改进的方面包括基于排序的适 Se lNum=(3I).然后以该工件集合来过滤父代并 应度分配，基于排序的工件过滤交叉算子和基于指 交叉产生子代，对应的子代Q和2对应的子代 数关系的变异率曲线 C2分别如下： q=(133113“, 3结果分析 C2=(113313). 实验评测基于Lawrence提出的各种benc 其中，*表示过滤掉的基因.再将2中多余的 mak其中电1到5是10×5（即10个工件和5 个体{24按照2中的顺序插入到Q中，将日中 个机器的问题)规模的问题：06到0是15×5 多余的个体{24}按照中的顺序插入到C②中. 规模的问题：间1到5是20×5规模的问题：6 0=(132314134242), 到20是10X10规模的问题：22和②4是15× 2=(112233214434). 10规模的问题；128是20×10规模的问题；马2是 1.5变异算子 30×10规模的问题.本算法的结果与文献[15-16 遗传算法中的变异算子，是指以一定概率随机 的传统遗传算法的结果进行比较. 改变染色体上的某些位，形成一个新的个体.本文 实验参数为：种群数Nd=30迭代次数Max 采用的变异算子与大多数JSS的求解一样，采用基 Ga=300选择比例PeSe=0.9.交叉率Xow= 于工件对交换的方法，其中交换的位置是随机产生 0.8最大变异率MaMu-0.4实验环境为Matb 的 65.1.实验结果如表1所示.在表1中，传统遗传 1.6自适应性 算法记录为GA,本文改进遗传算法为GA2特别 遗传算法中的自适应性体现为算法执行过程中 展示了G2算法的五次实验结果，并计算了所寻优 动态修改交叉率和变异率.一般来说，交叉率应设 值的均值.由表1可以看出，改进遗传算法比传统 置为一个较大的值，从而可以更多地在种群各个个 遗传算法的寻优能力更强.而且在电5.6、08 体之间交换信息.本文关注的自适应性主要是动态 09闯0冉3.间4和5的测试中，己经完全找 修改变异率，设计一种基于指数关系的变异率曲线. 到了己知最优值，在闭1、电7冉1和2测试中， 文献[9]提出将算法中的交叉率和变异率参数设计 也有数次找到己知最优值

北 京 科 技 大 学 学 报 第 32卷 交叉、多点交叉和均匀交叉以及基于排序的均匀交 叉 .对于单点交叉、多点交叉和均匀交叉, 由于产生 子代种群个体中可能存在非法的调度方案, 需要一 些额外的修补技术, 导致算法的效率较低.基于排 序的均匀交叉虽然能满足工件车间调度问题的求 解, 但模板中 0和 1是均匀产生的, 使得在交叉过程 中难于保留较长的模式, 而这对于算法的收敛是非 常不利的. 本文采用的交叉算子就是在基于排序的均匀交 叉算子的基础上, 改进模板中 0和 1 的产生方式 . 针对工件工厂调度问题, 采用工件集合过滤方式来 承担上述模板的作用.因此, 称本文采用的交叉算 子为基于排序的工件过滤交叉算子, 其计算过程如 下所示 . 设一个四工件三机器的 JSSP.某次迭代中两个 个体的编码为 P1 =( 132312132444), P2 =( 112433412432) . 随机产生一个工件编号的排列 JNum=( 2, 3, 1, 4), 并产生两个不同的随机整数 Pos1 和 Pos2, 根据 Pos1和 Pos2从 JNum中取出相应的工件编号集合 . 例如, 当 Pos1 =2, Pos2 =3 时, 取出的工件集合为 SelJNum=( 3, 1) .然后以该工件集合来过滤父代并 交叉产生子代, P1对应的子代 C1和 P2对应的子代 C2分别如下 : C1 =( 13 ＊ 31 ＊ 13 ＊＊＊＊ ), C2 =( 11 ＊＊ 33 ＊ 1 ＊＊ 3 ＊ ) . 其中, ＊表示过滤掉的基因 .再将 P2中多余的 个体{2, 4}按照 P2中的顺序插入到 C1中, 将 P1中 多余的个体 {2, 4}按照 P1中的顺序插入到 C2中 . C1 =( 132314134242), C2 =( 112233214434) . 1.5 变异算子 遗传算法中的变异算子, 是指以一定概率随机 改变染色体上的某些位, 形成一个新的个体.本文 采用的变异算子与大多数 JSSP的求解一样, 采用基 于工件对交换的方法, 其中交换的位置是随机产生 的 . 1.6 自适应性 遗传算法中的自适应性体现为算法执行过程中 动态修改交叉率和变异率.一般来说, 交叉率应设 置为一个较大的值, 从而可以更多地在种群各个个 体之间交换信息 .本文关注的自适应性主要是动态 修改变异率, 设计一种基于指数关系的变异率曲线 . 文献[ 9]提出将算法中的交叉率和变异率参数设计 为个体适应度和种群最大适应度之差的线性关系, 而文献[ 10] 则提出将算法中的交叉率和变异率参 数设计为个体适应度和种群最大适应度之差的指数 关系, 并且验证了这种指数关系取得了较好的效果. 对于 JSSP, 设 Ti为个体 i的完工时间, Tmax和 Tmin分别为种群中的最大完工时间和最小完工时间. 当个体的完工时间越靠近 Tmax, 则其变异率应该越 大, 而当个体的完工时间越靠近 Tmin, 其变异率应该 越小 .本文采用的基于指数关系的变异率曲线是对 文献 [ 10]的改进, 其形式为 Mutr= MaxMutr e-e ( Tmax-Ti) /( Tmax-Tmin) e-1 , Tmax≠Tmin MaxMutr, Tmax =Tmin 式中, MaxMutr为最大变异率 .与文献 [ 10] 所不同 的是, 曲线适应于种群中的所有个体, 而不是仅仅适 用于均值以上的个体, 而且在曲线的具体形式上也 是不同的 . 2 算法实现 改进遗传算法的执行过程与传统遗传算法的执 行过程大致相同.其改进的方面包括基于排序的适 应度分配 、基于排序的工件过滤交叉算子和基于指 数关系的变异率曲线. 3 结果分析 实验评测基于 Lawrence [ 14] 提出的各种 bench￾mark.其中 la01到 la05是 10 ×5(即 10个工件和 5 个机器的问题 ) 规模的问题;la06 到 la10 是 15 ×5 规模的问题;la11到 la15是 20 ×5规模的问题;la16 到 la20是 10 ×10规模的问题 ;la22和 la24是 15 × 10规模的问题;la28是 20 ×10规模的问题;la32是 30 ×10规模的问题 .本算法的结果与文献 [ 15--16] 的传统遗传算法的结果进行比较 . 实验参数为:种群数 Nind=30, 迭代次数 Max￾Gen=300, 选择比例 PerSel=0.9, 交叉率 Xovr= 0.8, 最大变异率 MaxMutr=0.4.实验环境为 Matlab 6.5.1.实验结果如表 1所示 .在表 1中, 传统遗传 算法记录为 GA1, 本文改进遗传算法为 GA2.特别 展示了 GA2算法的五次实验结果, 并计算了所寻优 值的均值 .由表 1可以看出, 改进遗传算法比传统 遗传算法的寻优能力更强 .而且在 la05、la06、la08、 la09、la10、la13、la14 和 la15的测试中, 已经完全找 到了已知最优值, 在 la01、la07、la11和 la12测试中, 也有数次找到已知最优值. · 1234·

第9期 汪红兵等：应用改进遗传算法求解炼钢连铸生产调度问题 1235 表1不同遗传算法的寻优结果比较 Tab le1 Comparison of computational results for different genetic agorithms GA2 问题 已知最优值 GAL 偏差% 偏差小 1 2 3 4 5 均值 闭1 666 94 19.22 666 666 678 690 666 673 1.05 02 655 686 473 682 682 682 676 676 680 382 03 597 699 17.09 654 639 646 621 668 646 821 闻4 590 662 1220 607 645 607 620 616 619 492 05 593 593 0.00 593 593 593 593 593 593 0.00 06 926 987 6.59 926 926 926 926 926 000 07 890 9%2 8.09 926 897 890 910 904 1.57 F08 863 9%3 11.59 863 863 863 863 000 )9 951 171 1262 951 951 951 951 000 网0 958 10I1 5.53 958 958 958 958 000 网1 1222 1340 9.66 1222 1730 1222 1228 049 两2 1039 1210 16.46 1039 1039 17 1039 1047 077 网3 1150 1362 1843 1150 115 150 1150 a00 网4 1292 1351 457 1292 129 29 1292 000 间5 1207 1365 13.09 1207 120 1249 1224 139 两6 945 1120 18.52 1040 1085 1003 1003 1039 995 两7 784 963 2283 822 826 822 822 823 495 网8 848 973 1474 926 862 862 866 886 443 网9 842 990 17.58 925 968 g75 939 925 936 11.21 ②0 902 1136 25.94 1013 1008 10B 1003 1008 1007 11.64 22 927 1175 2675 1121 1112 1127 1112 1127 1120 2080 24 935 1136 21.50 1090 1088 1089 1086 1084 1087 1630 28 1216 1574 29.44 1434 1326 1456 1434 1434 1417 1651 32 1850 2328 25.84 2117 2154 2143 2134 2132 2136 1546 表2不同钢种的工艺路径 4问题求解 Table 2 Different poocedure roues for different steel kinds min 某工厂一条生产线有1台脱磷转炉(DPBOF、 生产钢种 DPBOF DCBOF CAS LF RH 1650CC 1台脱碳转炉(DCBOF、1台CAS设备、1台I精 深冲超深冲SPCC 18 28 23 58 炼炉、1台H精炼炉和1台1650连铸机 结构用钢Q195 20 30 23- 54 (1650C℃.根据不同钢种对精炼处理的要求不同 高强度钢HSS-CQ 子 36 一 25 52 形成不同的工艺路线，如表2所示. 无取向硅钢35W440 24 34 46 55 以表2的生产钢种为例，按每个钢种生产二炉， 无取向硅钢35W250 2 必 59 基于改进遗传算法，求出最优调度方案.图1和图2 管线钢X42 26 帮 4025 56 分别是改进遗传算法的迭代曲线和最优调度甘特 管线钢X60 白 今 4035 56 图.图2中，图示“SPCC1”表示钢种SPCC的第1 低合金结构钢SM400 22 30 -35-55 个计划，图示“SPCC2”表示钢种SPCC的第2个计 注：“一”表示生产钢种不经过该工序. 划，以此类推.改进遗传算法求得的最小完工时间 考虑连铸机连浇约束时，其处理的方法是首先 为968m迎其迭代曲线表明改进遗传算法具有较强 给出最大连浇炉数P根据该炉数调整最优调度 的寻优能力，其生成的最优调度甘特图表明算法是 甘特图中的连铸机设备计划.从左至右每个计划 有效的. 为一个浇次，然后插入一个连铸机的检修等待时间

第 9期 汪红兵等:应用改进遗传算法求解炼钢连铸生产调度问题 表 1 不同遗传算法的寻优结果比较 Table1 Comparisonofcomputationalresultsfordifferentgeneticalgorithms 问题 已知最优值 GA1 偏差 /% GA2 1 2 3 4 5 均值 偏差 /% la01 666 794 19.22 666 666 678 690 666 673 1.05 la02 655 686 4.73 682 682 682 676 676 680 3.82 la03 597 699 17.09 654 639 646 621 668 646 8.21 la04 590 662 12.20 607 645 607 620 616 619 4.92 la05 593 593 0.00 593 593 593 593 593 593 0.00 la06 926 987 6.59 926 926 926 926 926 926 0.00 la07 890 962 8.09 926 897 896 890 910 904 1.57 la08 863 963 11.59 863 863 863 863 863 863 0.00 la09 951 1 071 12.62 951 951 951 951 951 951 0.00 la10 958 1 011 5.53 958 958 958 958 958 958 0.00 la11 1 222 1 340 9.66 1 222 1 239 1 222 1 237 1 222 1 228 0.49 la12 1 039 1 210 16.46 1 039 1 039 1 039 1 079 1 039 1 047 0.77 la13 1 150 1 362 18.43 1 150 1 150 1 150 1 150 1 150 1 150 0.00 la14 1 292 1 351 4.57 1 292 1 292 1 292 1 292 1 292 1 292 0.00 la15 1 207 1 365 13.09 1 207 1 207 1 207 1 249 1 249 1 224 1.39 la16 945 1 120 18.52 1 040 1 085 1 064 1 003 1 003 1 039 9.95 la17 784 963 22.83 822 826 822 822 822 823 4.95 la18 848 973 14.74 926 862 912 862 866 886 4.43 la19 842 990 17.58 925 968 925 939 925 936 11.21 la20 902 1 136 25.94 1 013 1 008 1 003 1 003 1 008 1 007 11.64 la22 927 1 175 26.75 1 121 1 112 1 127 1 112 1 127 1 120 20.80 la24 935 1 136 21.50 1 090 1 088 1 089 1 086 1 084 1 087 16.30 la28 1 216 1 574 29.44 1 434 1 326 1 456 1 434 1 434 1 417 16.51 la32 1 850 2 328 25.84 2 117 2 154 2 143 2 134 2 132 2 136 15.46 4 问题求解 某工厂一条生产线有 1台脱磷转炉 ( DPBOF) 、 1台脱碳转炉 ( DCBOF) 、1台 CAS设备 、1台 LF精 炼 炉、 1 台 RH精 炼 炉 和 1 台 1650 连 铸 机 ( 1650CC) .根据不同钢种对精炼处理的要求不同 形成不同的工艺路线, 如表 2所示. 以表 2的生产钢种为例, 按每个钢种生产二炉, 基于改进遗传算法, 求出最优调度方案.图 1和图 2 分别是改进遗传算法的迭代曲线和最优调度甘特 图 .图 2中, 图示 “SPCC- 1”表示钢种 SPCC的第 1 个计划, 图示 “SPCC- 2”表示钢种 SPCC的第 2个计 划, 以此类推 .改进遗传算法求得的最小完工时间 为 968min, 其迭代曲线表明改进遗传算法具有较强 的寻优能力, 其生成的最优调度甘特图表明算法是 有效的 . 表 2 不同钢种的工艺路径 Table2 Differentprocedureroutesfordifferentsteelkinds min 生产钢种 DPBOFDCBOF CAS LF RH 1650CC 深冲超深冲 SPCC 18 28 23 — — 58 结构用钢 Q195 20 30 23 — — 54 高强度钢 HSS-CQ 25 36 — — 25 52 无取向硅钢 35W440 24 34 — — 46 55 无取向硅钢 35W250 22 35 — — 55 59 管线钢 X42 26 38 — 40 25 56 管线钢 X60 25 37 — 40 35 56 低合金结构钢 SM400 22 30 — 35 — 55 注:“ — ”表示生产钢种不经过该工序. 考虑连铸机连浇约束时, 其处理的方法是首先 给出最大连浇炉数 n, 根据该炉数 n调整最优调度 甘特图中的连铸机设备计划 .从左至右每 n个计划 为一个浇次, 然后插入一个连铸机的检修等待时间 · 1235·

。1236 北京科技大学学报 第32卷 1300 t最后对每个浇次计划中炉次计划进行连续性调 整，以浇次计划中的最后一个炉次计划为基准，该浇 次计划中的其他炉次计划按顺序后延.对图2的最 1100 优调度甘特图按照=8和上32进行调整，如图3 所示. 1000 5结语 50 100150200250300 迭代次数 炼钢连铸生产调度问题可归属为JSS则SSP 图1改进遗传算法的迭代曲线 领域的众多研究成果就可以用来求解炼钢连铸生产 Fig 1 Ierat on curve or the mpoved genetic agorith 调度问题.提出了一种改进遗传算法求解该问题， 脱磷转炉 ■SPCC1 ■SPCC2 ■01951 ■01952 FHSS-CQ_1■HSS-C02 脱碳转炉 ■35W4401 ■35W4402 ■35W2501 ■35W2502 ■X601 -X602 CAS ■X421 ■X422 ■SM4001 口SM400_2 LF炉 RH 1650连铸机 200 400 600 800 1000 时间min 图2改进遗传算法的最优调度甘特图（调整前） Fg 2 OPti ized scheduling Gantt graph pr the mproved genetic agoritm before ad jusment 脱磷转炉 ■SPCC_1 ■SPCC2 ■Q195_1 ■Q1952 FHSS-CQ1■HSS-C02 脱碳转炉 画35W4401 ■35W4402 ■35W2501 ■35W2502 ■X601 ■X602 CAS ■X421 ■X422 ■sM4001 ■SM4002 F炉 RH 1650连铸机 200 400 600 800 1000 时间min 图3改进遗传算法的最优调度甘特图（调整后） Fi设3Opt恤灰dscheduling Gantt graph for the mproved g知etic aritm(afer adjusmen 主要包括三个方面：基于排序的适应度分配、基于排 传算法的寻优能力比传统遗传算法更强.通过对一 序的工件过滤交叉算子和基于指数关系的变异率曲 个炼钢连铸生产调度的计算实例，验证了该算法是 线.通过大量benclm ark的对比实验表明，改进遗 有效的

北 京 科 技 大 学 学 报 第 32卷 图 1 改进遗传算法的迭代曲线 Fig.1 Iterationcurvefortheimprovedgeneticalgorithm t, 最后对每个浇次计划中炉次计划进行连续性调 整, 以浇次计划中的最后一个炉次计划为基准, 该浇 次计划中的其他炉次计划按顺序后延.对图 2的最 优调度甘特图按照 n=8和 t=32进行调整, 如图 3 所示 . 5 结语 炼钢连铸生产调度问题可归属为 JSSP, 则 JSSP 领域的众多研究成果就可以用来求解炼钢连铸生产 调度问题 .提出了一种改进遗传算法求解该问题, 图 2 改进遗传算法的最优调度甘特图 (调整前 ) Fig.2 OptimizedschedulingGanttgraphfortheimprovedgeneticalgorithm( beforeadjustment) 图 3 改进遗传算法的最优调度甘特图 (调整后 ) Fig.3 OptimizedschedulingGanttgraphfortheimprovedgeneticalgorithm( afteradjustment) 主要包括三个方面:基于排序的适应度分配、基于排 序的工件过滤交叉算子和基于指数关系的变异率曲 线 .通过大量 benchmark的对比实验表明, 改进遗 传算法的寻优能力比传统遗传算法更强 .通过对一 个炼钢连铸生产调度的计算实例, 验证了该算法是 有效的. · 1236·

第9期 汪红兵等：应用改进遗传算法求解炼钢连铸生产调度问题 ·1237 参考文献 the flexible b shop scheduling pobkm J Mech Eng 2009.45 I I]PangX E YuS P Luw etal Research and deve kpment of (7:45 steemaking and continuous casting dynam ic ntellgence schedu (张国辉，高亮，李培根，等.改进遗传算法求解柔性作业车 Iing system Control Eng China 2005 12(6):553 间调度问题.机械工程学报，200945(7)：145) (庞新富，俞胜平，刘炜，等。炼钢连铸动态智能调度系统的 I9 WangX P Cao LM GeneticA gorithm Theory Application and 研究与开发.控制工程，200512(6)：553) Sofware mpkmenntion Xi X Jiaoong University Press 【】FengZ】YangGK Du B et al Two stge optmigzatin a 2002 ritms based on heuristic and linear Pogramming in continuous (王小平，曹立明.遗传算法：理论，应用与软件实现.西安： casting scheduling Metall Ind Au omn 2005 294 18 西安交通大学出版社，2002) (冯振军，杨根科，杜斌，等.炼钢连铸调度的启发式和线性 10 Xng Y]Chen ZT Sun J An mproved adaptive gnetic alg 规划两步优化算法.治金自动化.200529418) ritm pr joh-shop scheduling prob lem/Proceedings of the3 rd I 【31 Zhu BI.YuH B Poduction schedu lingmodel and a oritlm or ema ticnalConference a Nal Computation(KCNC 2007). steemaking continuous castinghot olling pocesses Comput Inte Hak2007:1752 gr Manuf Syst 2003.9(1):33 [1l]TsujmumyY GenM Kubon E SoMing pbshop scheduling (侏宝琳，于海斌。炼钢-连铸热轧生产调度模型及算法研 Pob km wih fuzzy processing tme usng genetic aporim J Jm 究.计算机集成制造系统，20039(1)：33) Soc Fuzy Theory Syst 1995 7(2):1073 [4 TangLX Li JY YangZH Amathema ticalprogrammingmal [12 ChengR GenM TsujmumyY.A uprial survey of pb shop el for scheduling steem ak ing contnuous castng production Eur I scheduling problems using genetic a gorithms PartII.Hybrd Oper R2000120(2:423 genetic search sta egies Conput hd Eng 1999 36(2):343 【习Atghehch知A BinriM Taikesh H A novel hybrid a poritm [13ckT HoffneisterF Extended selectionmechanims n genet or schedu ling stee Lmaking contnuous cast ing produc tion Comput c a britm/Poceedings of the4h Intemational Con ference an oPer R5200936(8):2450 GeneticA Foritms San Digo 1991 92 [6 JingLW.Sudies on J Shop Scheduling Pobkms Based onGe [14 Lawrence Resaurce Constm ned Project Stheduling an Experi neticA gorithm Dissertation,Sharghai Shanghai Jiaorng Uni mental Investiga tion of Heuristic Schedul ing Techn Aues(Suppe ers02007 ment)[Disseratan.Pittsbugb Gmduare School of ndustrl (蒋丽雯.基于遗传算法的车间作业调度问题研究【学位论 Adm inistm tin CamegieMelbn Universit 1984 文1.上海：上海交通大学，2007 15 Yamadh T Sudes on Metheuristics pr Joshop and Fpwstop I 7 Zhou HR Zheng PE ZongY et a]Method prGA-based ok Schedulng Problem Dissenaton.Japan Kyop Universit t知o pb shop scheduling optmizat仰APp]Res Comput20s 2003.69 25(10):2991 [16 Hasan SMK Ruhul David C Hybri genetic a poritlm pr (周辉仁，郑不谔，宗蕴，等.基于遗传算法的作业车间调度 solv ing pb shop scheduling pooblm//Proceed ings of the 6th 优化求解方法.计算机应用研究.200825(10)：2991) IFEE/ACIS In tema tiora l Conference on Computer and Iomation 【图ZhangGH Gaol LiPG etal mproved genetic apritm or Science Mebome 2007 519

第 9期 汪红兵等:应用改进遗传算法求解炼钢连铸生产调度问题 参 考 文 献 [ 1] PangXF, YuSP, LiuW, etal.Researchanddevelopmentof steelmakingandcontinuouscastingdynamicintelligenceschedu￾lingsystem.ControlEngChina, 2005, 12 ( 6) :553 (庞新富, 俞胜平, 刘炜, 等.炼钢连铸动态智能调度系统的 研究与开发.控制工程, 2005, 12( 6) :553) [ 2] FengZJ, YangGK, DuB, etal.Twostageoptimizationalgo￾rithmsbasedonheuristicandlinearprogrammingincontinuous castingscheduling.MetallIndAutom, 2005, 294:18 (冯振军, 杨根科, 杜斌, 等.炼钢连铸调度的启发式和线性 规划两步优化算法.冶金自动化, 2005, 294:18 ) [ 3] ZhuBL, YuHB.Productionschedulingmodelandalgorithmfor steelmaking-continuouscasting-hotrollingprocesses.ComputInte￾grManufSyst, 2003, 9( 1 ) :33 (朱宝琳, 于海斌.炼钢-连铸-热轧生产调度模型及算法研 究.计算机集成制造系统, 2003, 9( 1) :33) [ 4] TangLX, LiuJY, YangZH.Amathematicalprogrammingmod￾elforschedulingsteelmakingcontinuouscastingproduction.EurJ OperRes, 2000, 120 ( 2) :423 [ 5] AtighehchianA, BijariM, TarkeshH.Anovelhybridalgorithm forschedulingsteel-makingcontinuouscastingproduction.Comput OperRes, 2009, 36( 8) :2450 [ 6] JiangLW.StudiesonJobShopSchedulingProblemsBasedonGe￾neticAlgorithms[ Dissertation] .Shanghai:ShanghaiJiaotongUni￾versity, 2007 (蒋丽雯.基于遗传算法的车间作业调度问题研究 [ 学位论 文] .上海:上海交通大学, 2007) [ 7] ZhouHR, ZhengPE, ZongY, etal.MethodforGA-basedsolu￾tiontojobshopschedulingoptimization.ApplResComput, 2008, 25( 10) :2991 (周辉仁, 郑丕谔, 宗蕴, 等.基于遗传算法的作业车间调度 优化求解方法.计算机应用研究, 2008, 25( 10) :2991) [ 8] ZhangGH, GaoL, LiPG, etal.Improvedgeneticalgorithmfor theflexiblejobshopschedulingproblem.JMechEng, 2009, 45 ( 7 ) :145 (张国辉, 高亮, 李培根, 等.改进遗传算法求解柔性作业车 间调度问题.机械工程学报, 2009, 45( 7 ) :145 ) [ 9] WangXP, CaoLM.GeneticAlgorithm:Theory, Applicationand SoftwareImplementation.Xian:XianJiaotongUniversityPress, 2002 (王小平, 曹立明.遗传算法:理论、应用与软件实现.西安: 西安交通大学出版社, 2002) [ 10] XingYJ, ChenZT, SunJ.Animprovedadaptivegeneticalgo￾rithmforjob-shopschedulingproblem∥Proceedingsofthe3rdIn￾ternationalConferenceonNaturalComputation( ICNC2007 ). Haikou, 2007:1752 [ 11] TsujimurayY, GenM, KubotaE.Solvingjob-shopscheduling problemwithfuzzyprocessingtimeusinggeneticalgorithm.JJpn SocFuzzyTheorySyst, 1995, 7 ( 2) :1073 [ 12] ChengR, GenM, TsujimurayY.Atutorialsurveyofjobshop schedulingproblemsusinggeneticalgorithms:PartⅡ .Hybrid geneticsearchstrategies.ComputIndEng, 1999, 36( 2 ) :343 [ 13] BäckT, HoffmeisterF.Extendedselectionmechanismsingenet￾icalgorithms∥Proceedingsofthe4thInternationalConferenceon GeneticAlgorithms.SanDiego, 1991:92 [ 14] LawrenceS.ResourceConstrainedProjectScheduling:anExperi￾mentalInvestigationofHeuristicSchedulingTechniques( Supple￾ment) [ Dissertation] .Pittsburgh:GraduateSchoolofIndustrial Administration, CarnegieMellonUniversity, 1984 [ 15] YamadaT.StudiesonMetaheuristicsforJobshopandFlowshop SchedulingProblems[ Dissertation] .Japan:KyotoUniversity, 2003:69 [ 16] HasanSMK, RuhulS, DavidC.Hybridgeneticalgorithmfor solvingjob-shopschedulingproblem∥ Proceedingsofthe6th IEEE/ACISInternationalConferenceonComputerandInformation Science.Melbourne, 2007:519 · 1237·