基于蚁群算法的炼钢-连铸作业计划编制方法

D01:10.13374j.isml00103x.2009.04.0I6 第31卷第4期 北京科技大学学报 Vol.31 No.4 2009年4月 Journal of University of Science and Technology Beijing Apr.2009 基于蚁群算法的炼钢连铸作业计划编制方法 郑忠)朱道飞) 高小强 1)重庆大学材料科学与工程学院，重庆4000452)重庆大学经济与工商管理学院重庆400044 摘要为提高炼钢连铸作业计划编制中资源配置的有效性，提出了一种面向生产流程动态网络的自组织资源配置蚁群算 法.炼钢一连铸作业计划以最小化炉次作业冲突时间和作业前等待时间、尽早安排连铸机开浇时间为目标，以连铸机连浇等 工艺要求为约束条件建立模型，按生产流程网络结构的时空逆序关系设计了蚁群求解算法.利用某钢厂实际生产作业计划数 据进行的算法验证结果表明：模型及算法能迅速得到高质量的可执行炼钢一连铸生产作业计划. 关键词炼钢连铸：生产作业计划：蚁群算法：流程网络图 分类号TP278:F273 Production planning based on an ant colony algorithm for steel-making and con- tinuous casting ZHENG Zhong.ZHU Dao-fe.GAO Xiao-giang2) 1)Collge of Materials Science and Engineering.Chongqing Uriversity.Chongqing 400045.China 2)Colege of Economics and Business Administ ration.Chongqing University.Chonging 400044.China ABSTRACT An ant colony algorithm of self-organization resource allocation for dy namic procedure netw orks in production process w as proposed to improve the validity of resource allocation in steehmaking and continuous casting production planning.A production planning model for steehmaking and continuous casting was established w ith sequence casting constraint.In the model,the objective is to minimize the operation conflict time and the queue w aiting time and to start pouring early.The ant colony algorithm was de- signed on the base of the time and space reverse relation of structure of prooedure netw orks in production process.The test w ith pro- duction data in a commercial steel plant show s that the model and algorithm can draw quickly a high-quality and performable produc- tion plan. KEY WORDS stee-making and continuous casting:production planning ant colony algorithm:procedure netw orks 炼钢和连铸工序的协调生产对改善钢厂的生产 算法和模拟退火算法的全局寻优能力弱且难以解决 组织方式和提高系统的运行效率起着非常重要的作 大规模组合优化问题，遗传算法又存在同一炉次在 用.因此，炼钢一连铸作业计划编制问题成为研究 相邻工序间的作业排序以及同一加工设备上不同炉 热点匀 次的作业排序等复杂约束问题处理的困难19 炼钢连铸作业计划编制问题通常被抽象成混 蚁群算法开始在求解车间作业计划编制与调度 合流水车间的作业排序问题，以铸机断浇、作业前等 优化方面取得较好成效，目前主要应用在流水车 待等作业偏离预定生产目标所产生的惩罚费用为目间和半导体生产调度中，大多数研究者在利用蚁群 标函数建立数学规划模型，并采用启发式方 算法求解Jobshop问题时，都利用类似于Jobshop问 法9，模拟退火算法和遗传算法)等方法进行求 题析取图的解构造图来确定在同一设备上不同任务 解.此建模思想是从“控制损失”的角度来考虑问 的加工顺序，将解决Jobshop问题的蚁群算法解构 题，难以确定目标的优化程度：求解方法中的启发式造过程转变为蚂蚁在Jobo叩解构造图上的从虚拟 收稿日期：200803-02 基金项目：国家高技术研究发展计划资助项目(No.2007AA04Z161):国家自然科学基金钢铁联合基金资助项目(No.50574110) 作者简介：郑忠(1963一)，女，教授，博士生导师，E-maik zhengzh@cqu.ed血.cm

基于蚁群算法的炼钢-连铸作业计划编制方法 郑 忠1) 朱道飞1) 高小强2) 1) 重庆大学材料科学与工程学院, 重庆 400045 2) 重庆大学经济与工商管理学院, 重庆 400044 摘 要 为提高炼钢-连铸作业计划编制中资源配置的有效性, 提出了一种面向生产流程动态网络的自组织资源配置蚁群算 法.炼钢-连铸作业计划以最小化炉次作业冲突时间和作业前等待时间、尽早安排连铸机开浇时间为目标, 以连铸机连浇等 工艺要求为约束条件建立模型, 按生产流程网络结构的时空逆序关系设计了蚁群求解算法.利用某钢厂实际生产作业计划数 据进行的算法验证结果表明:模型及算法能迅速得到高质量的可执行炼钢-连铸生产作业计划. 关键词 炼钢-连铸;生产作业计划;蚁群算法;流程网络图 分类号 TP278 ;F 273 Production planning based on an ant colony algorithm for steel-making and con￾tinuous casting ZHENG Zhong 1) , ZHU Dao-fei 1) , GAO Xiao-qiang 2) 1) College of Materials Science and Engineering, Chongqing Uni versit y, Chongqing 400045, China 2) College of Economi cs and Business Administration, Chongqing University, Chongqing 400044, China ABSTRACT An ant colony alg orithm of self-org anization resource allocation fo r dy namic procedure ne tw orks in production process w as proposed to improve the validity of resource allocation in steel-making and continuous casting production planning.A production planning model for steel-making and continuous casting was established w ith sequence casting constraint .I n the model, the objective is to minimize the opera tio n conflict time and the queue w aiting time and to start pouring early.The ant colony alg orithm was de￾signed on the base o f the time and space reverse relation of structure of pro cedure netw orks in productio n process.The test w ith pro￾duction data in a commercial steel plant show s that the model and algorithm can draw quickly a high-quality and performable produc￾tio n plan . KEY WORDS steel-making and continuous casting ;production planning;ant colony algorithm ;procedure ne tw orks 收稿日期:2008-03-02 基金项目:国家高技术研究发展计划资助项目( No .2007AA04Z161) ;国家自然科学基金钢铁联合基金资助项目( No .50574110) 作者简介:郑 忠( 1963—) , 女, 教授, 博士生导师, E-mail:zhengzh@cqu.edu.cn 炼钢和连铸工序的协调生产对改善钢厂的生产 组织方式和提高系统的运行效率起着非常重要的作 用[ 1] .因此, 炼钢-连铸作业计划编制问题成为研究 热点 [ 2-5] . 炼钢-连铸作业计划编制问题通常被抽象成混 合流水车间的作业排序问题, 以铸机断浇、作业前等 待等作业偏离预定生产目标所产生的惩罚费用为目 标函数建立数学规划模型[ 6-7] , 并采用启发式方 法[ 6] 、模拟退火算法[ 8] 和遗传算法[ 9] 等方法进行求 解.此建模思想是从“ 控制损失” 的角度来考虑问 题, 难以确定目标的优化程度 ;求解方法中的启发式 算法和模拟退火算法的全局寻优能力弱且难以解决 大规模组合优化问题, 遗传算法又存在同一炉次在 相邻工序间的作业排序以及同一加工设备上不同炉 次的作业排序等复杂约束问题处理的困难 [ 10] . 蚁群算法开始在求解车间作业计划编制与调度 优化方面取得较好成效 [ 11] , 目前主要应用在流水车 间和半导体生产调度中 .大多数研究者在利用蚁群 算法求解 Jobshop 问题时, 都利用类似于 Jobshop 问 题析取图的解构造图来确定在同一设备上不同任务 的加工顺序, 将解决 Jobshop 问题的蚁群算法解构 造过程转变为蚂蚁在 Jobshop 解构造图上的从虚拟 第 31 卷 第 4 期 2009 年 4 月 北 京 科 技 大 学 学 报 Journal of University of Science and Technology Beijing Vol .31 No.4 Apr.2009 DOI :10.13374/j .issn1001 -053x.2009.04.016

第4期 郑忠等：基于蚁群算法的炼钢连铸作业计划编制方法 ·505。 节点出发的节点遍历问题上州.随着工件数和加 计划中钢种的加工工艺路径，将各炉次分配到所经 工工序数的增加，解构造图的规模和解空间呈指数 过工序的相应工位上加工，并确定在工位的作业时 增长趋势，导致算法的搜索时间较长且解的质量不 间，使各炉次间没有作业时间冲突，以得到炼钢一连 高. 铸生产作业计划方案 为编制高质量的炼钢一连铸生产作业计划，提 1.2作业计划编制方法原理 高计划编制中资源配置的合理性，以最小化炉次作 针对炼钢连铸作业计划编制特点，按面向生 业冲突时间和作业前等待时间、尽可能提前安排连 产工艺流程网络结构的时空逆序关系构建了基于蚁 铸机的开浇时间为目标函数，按满足连浇等工艺约 群算法的炼钢一连铸作业计划编制方法.其原理如 束来建立炼钢一连铸作业计划模型；借助蚁群能同 图1所示. 时利用启发式信息和历史积累信息进行路径自组织 该炼钢连铸作业计划编制方法的特点在于： 选择的特点，构建一种面向生产流程网络图而非解 以生产工艺流程动态网络结构为作业计划编制的基 构造图的蚁群算法来求解模型.最后，以某钢厂的 础，具体浇次计划和炉次计划的制定过程互为约束 实际生产数据验证模型和算法的有效性. 和影响，按保证连浇生产的浇次计划确定炉次计划 的工位与时间安排，通过反馈机制可进行计划间的 1 作业计划编制数学模型 调整：设计按逆工艺流程进行工序和工位选择和逆 1.1作业计划编制问题描述 时间序进行炉次任务安排的蚁群算法，算法每“代” 炼钢连铸作业计划编制是指在满足钢厂现有 产生的计划方案会根据“信息素”和启发式规则等自 生产条件下，在计划生产期内，根据己知的批量计划 主进化至最优计划方案，从算法机制上保证自组织 (即浇次计划和炉次计划)，为各连铸机确定合适的 进行资源配置：资源配置的合理性可用计划编制质 开浇时间，在保证各铸机实现连浇的基础上，按炉次 量来体现. 读取批量计划 浇次计划 炉次计划 1.浇次内 /开浇时连浇蚁群逆流程自组织】 、间搜索计算算法倒推 择路 1.工序间炉次 连浇约束 一一 77 作业先后顺序 2浇次同活卖 2.相同工位上 各开 各序结按到选剑 调整时间民飞铸 逆先择一 相邻炉次作业 先后顺序 在开业 3.钢种工艺路径 的间 各始时和原工 工写间晚则位 1.确定各连铸机 各炉次的开浇时间 1.炉次作业工位选择 的开浇时间 二二二==2确定炉次在各工位上 2,保证连浇生产 作业计划方案反馈 开始和结束作业时间 图1炼钢一连铸作业计划编制方法的原理 Fig.I Principle of steelmaking-continuus casting production planning 此蚁群算法在算法运行的对象模型构造和表达法，改进了基于遗传算法和时间并行倒推相结合的 方式以及算法设计与常规蚁群算法不同.常规蚁群 计划编制方法1中按设定规则选择炉次作业工位 算法通过解构造图来静态地表征蚂蚁路径上的所有 的灵活性：而且，工序上不同炉次按逆时间序“后到 解：而本文则构造炼钢连铸生产工艺流程网络图， 先加工”的原则安排作业工位，也改变了逆流程时采 通过蚂蚁对应炉次的加工工艺路径与网络图中工序 用“先到先加工”的规则，需采用冲突消解规则进行 进行匹配来动态选择加工路线并生成问题的解.在 有限的相邻炉次间作业冲突的消减并可能影响所 算法设计上，常规蚁群算法根据路径上历史信息素 调整炉次在后续工位的作业时间. 情况来择路，而本文还引进体现生产原则的启发式1.3作业计划编制数学模型描述 信息来改变择路规则， 模型应用的前提条件为：(1)批量计划已知： 基于蚁群算法的炼钢一连铸作业计划编制方 (2)浇次计划中炉次在铸机上的作业顺序不变：

节点出发的节点遍历问题 [ 12-14] .随着工件数和加 工工序数的增加, 解构造图的规模和解空间呈指数 增长趋势, 导致算法的搜索时间较长且解的质量不 高. 为编制高质量的炼钢 -连铸生产作业计划, 提 高计划编制中资源配置的合理性, 以最小化炉次作 业冲突时间和作业前等待时间 、尽可能提前安排连 铸机的开浇时间为目标函数, 按满足连浇等工艺约 束来建立炼钢-连铸作业计划模型 ;借助蚁群能同 时利用启发式信息和历史积累信息进行路径自组织 选择的特点, 构建一种面向生产流程网络图而非解 构造图的蚁群算法来求解模型.最后, 以某钢厂的 实际生产数据验证模型和算法的有效性 . 1 作业计划编制数学模型 1.1 作业计划编制问题描述 炼钢-连铸作业计划编制是指在满足钢厂现有 生产条件下, 在计划生产期内, 根据已知的批量计划 (即浇次计划和炉次计划), 为各连铸机确定合适的 开浇时间, 在保证各铸机实现连浇的基础上, 按炉次 计划中钢种的加工工艺路径, 将各炉次分配到所经 过工序的相应工位上加工, 并确定在工位的作业时 间, 使各炉次间没有作业时间冲突, 以得到炼钢-连 铸生产作业计划方案. 1.2 作业计划编制方法原理 针对炼钢-连铸作业计划编制特点, 按面向生 产工艺流程网络结构的时空逆序关系构建了基于蚁 群算法的炼钢-连铸作业计划编制方法 .其原理如 图 1 所示. 该炼钢-连铸作业计划编制方法的特点在于: 以生产工艺流程动态网络结构为作业计划编制的基 础, 具体浇次计划和炉次计划的制定过程互为约束 和影响, 按保证连浇生产的浇次计划确定炉次计划 的工位与时间安排, 通过反馈机制可进行计划间的 调整 ;设计按逆工艺流程进行工序和工位选择和逆 时间序进行炉次任务安排的蚁群算法, 算法每“代” 产生的计划方案会根据“信息素”和启发式规则等自 主进化至最优计划方案, 从算法机制上保证自组织 进行资源配置 ;资源配置的合理性可用计划编制质 量来体现. 图 1 炼钢-连铸作业计划编制方法的原理 Fig.1 Principle of steelmaking-continuous casting production planning 此蚁群算法在算法运行的对象模型构造和表达 方式以及算法设计与常规蚁群算法不同 .常规蚁群 算法通过解构造图来静态地表征蚂蚁路径上的所有 解;而本文则构造炼钢-连铸生产工艺流程网络图, 通过蚂蚁对应炉次的加工工艺路径与网络图中工序 进行匹配来动态选择加工路线并生成问题的解 .在 算法设计上, 常规蚁群算法根据路径上历史信息素 情况来择路, 而本文还引进体现生产原则的启发式 信息来改变择路规则 . 基于蚁群算法的炼钢-连铸作业计划编制方 法, 改进了基于遗传算法和时间并行倒推相结合的 计划编制方法[ 15] 中按设定规则选择炉次作业工位 的灵活性 ;而且, 工序上不同炉次按逆时间序“后到 先加工”的原则安排作业工位, 也改变了逆流程时采 用“先到先加工” 的规则, 需采用冲突消解规则进行 有限的相邻炉次间作业冲突的消减, 并可能影响所 调整炉次在后续工位的作业时间 . 1.3 作业计划编制数学模型描述 模型应用的前提条件为:( 1) 批量计划已知; ( 2) 浇次计划中炉次在铸机上的作业顺序不变; 第 4 期 郑 忠等:基于蚁群算法的炼钢-连铸作业计划编制方法 · 505 ·

。506 北京科技大学学报 第31卷 (3)炉次在工序上的加工时间和工序间的运输时间 x,Mk=xiMk十tiMk十G,M.k 存在不确定性，但各时间的分布特征已知：(4)各工 (i,i∈n,k∈Ⅱw) (2) 位的最早可用时刻已知.定义模型中符号含义为： x,,k=x,.k-,k-d(i,j')-2,k i一炉次的序号，共有N个炉次：广一生产流程网络 (i∈j'∈⑨，k'∈，k∈) (3) 图中工序的编号，共M道生产工序：k一工序j上 工位的编号，共Q(j)个工位：'一工序j工位k上 Hj,k≤Hmx（i∈具j∈⑧，k∈马) （4) 紧邻炉次i的后一炉次：广'一炉次i加工工艺路径 合Cx≤1(icn.je0) (5) 上工序j的紧前工序；2一全部炉次集合，={i i∈[1，W}:Θ-最长加工工序集合，©={j∈[L, x,i,Dx,,k+i,k(i,i∈且，j∈⊙，k∈) :⑨一炉次i的加工工艺路径，由加工经过的 (6) 工序编号组成⊙∈⊙；马一工序j上的加工工位集 xi,,k≥，k(i∈nj∈Θ，k∈可) (7) 合，由K个工位的编号组成，马={k|k∈[L, 目标函数(1)表示工位上作业冲突时间、炉次作 K}:i,,k一炉次i在工序j工位k上的开始作业 业前等待时间以及连铸机最大可提前开浇时间三部 时间：红，k一炉次i在工序j工位k上的作业时间； 分加权和最小.根据各目标在生产中的重要程度， d(j,j)一炉次在工序j和工序j'之间的运输时间： 权重系数由生产经验设置为12≥3：约束(2) “,k一炉次i在工序j工位k上作业前的允许等待 为连铸机连浇约束；约束(3)为炉次在相邻工序上开 时间；ma一炉次作业前的最长允许等待时间； 始作业时间的倒推关系式：约束(4)表示炉次在作业 ,k一工序j工位k上第1炉次的开始作业时间： 前的等待时间在最大允许等待时间范围内；约束(5) ,k一作业计划初始时刻工序j工位k的最早可用 表示炉次在每道工序最多被分配到其中一个工位上 加工；约束(6)表示在同一工位上，前一炉次处理结 时间；j,k一工序j工位k上炉次i与紧邻的后一 炉次i作业间的间隙时间； 束后才能处理下一炉次：约束(7)表示炉次在工位上 1,炉次i分配给工序j的工位k加工 的开始作业时间应迟于计划编制时刻的各工位最早 Ck=0,否则 可用时间. 模型中的炉次作业冲突时间是指当铸机开浇时 2面向生产工艺流程网络图的蚁群算法 刻选择不合适时，可能导致工位上作业炉次的开始 为利用蚁群算法求解炼钢一连铸生产作业计划 作业时刻早于计划编制时工位的最早可用时刻（完 成已下达任务的结束时间或用户指定的可用时刻)， 模型，对体现蚁群系统原理的蚂蚁探路算法进行分 出现炉次作业冲突.工序j工位k上炉次i与工位 析，并对比抽象出面向生产工艺流程网络图的蚁群 的最早可用时刻间可能存在的冲突时间f()= 算法.两者的对比关系如表1所示 mar{0,,k一xi,k},各工位上的总冲突时间为： 表1炼钢一连铸作业计划编制与蚁群探路的对应关系 C.fd(i). Table I Corresponding relation betw een steelmaking-continuous cast- jEBEn IEn ing production planning and ants rout ing 当工位上相邻炉次存在作业时间冲突时，通过 项目蚁群探路算法 作业计划编制算法 将后分配炉次的开始与结束作业时间提前能消除作 食物源 末道工序后的虚拟节点 业冲突，但会增加所调整炉次在下道工序作业前的 蚁穴 首道工序前的虚拟节点 等待时间.所有炉次作业前的等待时间为： 蚂蚁 炉次对应的蚂蚊 f2=∑∑∑C,kh.E. 基本要素 蚂蚁路径 逆流程的工序与工位 jEBEIIEn 信息素 工位/全局信息素 为提高连铸机的生产效率，应尽可能缩短连铸 启发式信息 工位占用的启发式信息 机的预定开浇时刻与最早可选开浇时刻间的差距 信息素更新规则 信息素局部/全局更新 最大可提前开浇时间为： 规则 路径选择策略 各工序的工位选择策略 f3=max{M,1-tM1,;M,k-tMkh,k∈ΠM. 目标 较短的路径 优化的作业计划方案 炼钢一连铸作业计划编制数学模型为： minz=aifi+a2f2+a3f3 (1) 炼钢连铸作业计划编制的蚁群算法为：将计 s.t. 划中的所有炉次通过与之相应的蚂蚁，依次从“食

( 3) 炉次在工序上的加工时间和工序间的运输时间 存在不确定性, 但各时间的分布特征已知 ;( 4) 各工 位的最早可用时刻已知.定义模型中符号含义为 : i —炉次的序号, 共有 N 个炉次;j —生产流程网络 图中工序的编号, 共 M 道生产工序;k —工序 j 上 工位的编号, 共 Q( j) 个工位;i′—工序 j 工位 k 上 紧邻炉次 i 的后一炉次;j′—炉次 i 加工工艺路径 上工序j 的紧前工序 ;Ψ—全部炉次集合, Ψ={i i ∈[ 1, N] };Θ—最长加工工序集合, Θ={j j ∈[ 1, M] };Θj —炉次 i 的加工工艺路径, 由加工经过的 工序编号组成, Θj ∈ Θ;Πj —工序 j 上的加工工位集 合, 由 K j 个工位的编号组成, Πj ={k k ∈ [ 1, K j] };xi , j , k —炉次 i 在工序j 工位k 上的开始作业 时间;τi, j , k —炉次 i 在工序j 工位k 上的作业时间 ; d( j , j′) —炉次在工序 j 和工序j′之间的运输时间 ; μi, j , k —炉次 i 在工序j 工位k 上作业前的允许等待 时间;μmax —炉次作 业前的最长允许等待时间 ; τj , k —工序 j 工位 k 上第 1 炉次的开始作业时间 ; τ′j , k —作业计划初始时刻工序 j 工位k 的最早可用 时间 ;σi, j , k —工序 j 工位k 上炉次i 与紧邻的后一 炉次i′作业间的间隙时间 ; Ci, j, k = 1, 炉次 i 分配给工序 j 的工位k 加工 0, 否则 模型中的炉次作业冲突时间是指当铸机开浇时 刻选择不合适时, 可能导致工位上作业炉次的开始 作业时刻早于计划编制时工位的最早可用时刻( 完 成已下达任务的结束时间或用户指定的可用时刻), 出现炉次作业冲突.工序 j 工位k 上炉次 i 与工位 的最早可用时刻间可能存在的冲突时间 fi, j, k ( i) = max{0, τ′j , k -x i, j , k}, 各工位上的总冲突时间为 : f 1 =j ∑ ∈ Θi k∑ ∈ Πj i∑ ∈ Ψ Ci , j , k f i, j , k ( i) . 当工位上相邻炉次存在作业时间冲突时, 通过 将后分配炉次的开始与结束作业时间提前能消除作 业冲突, 但会增加所调整炉次在下道工序作业前的 等待时间 .所有炉次作业前的等待时间为: f 2 = j ∑ ∈ Θi k∑ ∈ Πj i∑ ∈ Ψ Ci, j , k μi , j, k . 为提高连铸机的生产效率, 应尽可能缩短连铸 机的预定开浇时刻与最早可选开浇时刻间的差距 . 最大可提前开浇时间为: f 3 =max{τM , 1 -τ′M, 1, …, τM , k -τ′M, k}, k ∈ ΠM . 炼钢-连铸作业计划编制数学模型为: min z =α1 f 1 +α2 f 2 +α3 f 3 ( 1) s.t . xi′, M, k =x i, M, k +τi, M, k +σi , M , k ( i, i′∈ Ψ, k ∈ ΠM) ( 2) xi , j′, k′=xi , j , k -μi , j , k -d ( j, j′) -τi, j′, k′ ( i ∈ Ψ, j 、j′∈ Θi , k′∈ Πj′, k ∈ Πj) ( 3) μi, j , k ≤μmax ( i ∈ Ψ, j ∈ Θi , k ∈ Πj) ( 4) ∑ O( j ) k =1 Ci , j, k ≤1 ( i ∈ Ψ, j ∈ Θi) ( 5) xi′, j , k >xi , j , k +τi , j , k ( i, i′∈ Ψ, j ∈ Θi , k ∈ Πj ) ( 6) xi , j , k ≥τ′j , k ( i ∈ Ψ, j ∈ Θ, k ∈ Πj) ( 7) 目标函数( 1) 表示工位上作业冲突时间、炉次作 业前等待时间以及连铸机最大可提前开浇时间三部 分加权和最小.根据各目标在生产中的重要程度, 权重系数由生产经验设置为 α1 >α2 ≥α3 ;约束( 2) 为连铸机连浇约束 ;约束( 3)为炉次在相邻工序上开 始作业时间的倒推关系式;约束( 4)表示炉次在作业 前的等待时间在最大允许等待时间范围内 ;约束( 5) 表示炉次在每道工序最多被分配到其中一个工位上 加工 ;约束( 6)表示在同一工位上, 前一炉次处理结 束后才能处理下一炉次 ;约束( 7)表示炉次在工位上 的开始作业时间应迟于计划编制时刻的各工位最早 可用时间. 2 面向生产工艺流程网络图的蚁群算法 为利用蚁群算法求解炼钢-连铸生产作业计划 模型, 对体现蚁群系统原理的蚂蚁探路算法进行分 析, 并对比抽象出面向生产工艺流程网络图的蚁群 算法.两者的对比关系如表 1 所示 . 表1 炼钢-连铸作业计划编制与蚁群探路的对应关系 Table 1 Corresponding relation betw een steelmaking-con tinuous cast￾ing production planning and ants routing 项目 蚁群探路算法 作业计划编制算法 食物源 末道工序后的虚拟节点 蚁穴 首道工序前的虚拟节点 基本要素 蚂蚁 炉次对应的蚂蚁 蚂蚁路径 逆流程的工序与工位 信息素 工位/ 全局信息素 启发式信息 工位占用的启发式信息 规则 信息素更新规则 信息素局部/ 全局更新 路径选择策略 各工序的工位选择策略 目标 较短的路径 优化的作业计划方案 炼钢-连铸作业计划编制的蚁群算法为:将计 划中的所有炉次, 通过与之相应的蚂蚁, 依次从“食 · 506 · 北 京 科 技 大 学 学 报 第 31 卷

第4期 郑忠等：基于蚁群算法的炼钢连铸作业计划编制方法 507。 物源”经生产工艺流程动态网络的工序和工位，在相 2.1.2信息素更新策略 应的时间段内，搬运到“蚁穴”的过程.通过开浇时 算法中采用信息素局部和全局更新相结合的 间搜索算法改变算法的起始时间：蚂蚁按信息素和 策略. 启发式信息为炉次选择工位，工位信息素和全局信 (1)信息素局部更新.蚂蚁完成加工工位选择 息素在每代蚂蚁运行中会被更新.重复上述操作， 后，按下式进行信息素更新： 当计划指标达到设定的优化效果时，即得到优化的 t做'(i,t)=(1-P)做'(i,t)+△t&'(i,t)(11) 炼钢一连铸作业计划. 式中， 21算法中的关键问题 △k(i,t)= 工位选择策略和第t代至第1十1代间信息素 (work/flow人，k'为局部最优加工工位 更新策略设计至关重要，其直接影响算法的收敛速 9 否则 度和所得作业计划方案的优劣. 按炉次作业前的等待时间是否最小来判断加工 2.1.1工位选择策略 工位是否是局部最优工位.P为信息素蒸发率， 工位上的信息素浓度反映了工位利用的历史信 twok和tw分别表示炉次i当前总加工时间和物流 息，隐含资源配置规律：而工位上的启发式信息值用 时间. 于体现生产组织原则等.蚂蚁按伪随机比例选择策 (2)信息素全局更新.所有蚂蚁从食物源返回 略为当前工位k上的炉次i从紧前工序的可选工位 到蚁穴后，通过计算模型的目标函数值来判断当前 集π(，k)中选择作业工位k',即： 解是否是当前全局最优解，并按下式进行信息素全 ag船{凝(i,)(i,)》, 9≤90 局更新： P'(i,t), qqo k(i,t+1)=k'(i,t)十△x做(i)(12) (8) 其中， 其中，90∈(0,1)为常数，q∈(0,1)为随机数： Q k'在全局最优路径上 :'(i,t)和(i,t)分别表示第t代位于工位k的 △k(i)= Zgb 蚂蚁搬运炉次i到紧前工序工位k时，工位k'上的 0, 否则 信息素浓度以及与工位k相关联基于问题的启发式 zb为目前找到的模型目标函数最小值. 信息值：α和B分别表示控制信息素和启发式信息 信息素局部和全局更新后，为防止工位上信息 影响权重的参数. 素过多积累或完全蒸发，将工位上信息素限制在 式8)表示：第t代位于工位k的蚂蚁搬运炉次 Tmin,tmax]. i到紧前工序工位k'之前，先随机生成g,如果g不 2.2算法实现 大于q则从炉次i当前作业工位k的紧前工序所 基于生产流程网络的蚁群算法编制N个炉次 有可选工位中找出妖(i,t)赋(i,t)最大的工位 经过M道工序中若干工位的炼钢一连铸作业计划 k作为下一加工工位，否则按下式以概率P:'(,t) 算法描述如下： 来选择加工工位： Production planning Pkk'(i,t)= Begin (i,t)i,t) Step 1初始化. '(i,t)妖(i,t)' s∈π(i,k) (1)读取生产流程网络结构、工位状态、工位最 k'∈（正.k) (9) 早可用时刻及批量计划： 0, 否则 (2)设置蚁群算法参数及生产流程网络中各节 根据炼钢连铸生产中作业炉次的运行规则， 点上信息素浓度，令蚂蚁代数计数器t=1: 将工位上主设备利用率均衡和炉次等待时间最小作 Step2生成铸机预定开浇时间、炉次的作业时 为启发式信息，即： 间和运输时间. tiik' 盟2。片了， (1)由开浇时间搜索算法生成各连铸机的预定 n傲'(i,)=0k)+h,,k (10) 开浇时间； 其中，x(k')为分配炉次i之前工位k'上已分配的加 (2)根据式(2)计算各炉次在铸机上的开始和 工时间总和，Q为信息素浓度常量 结束浇注时间；

物源”经生产工艺流程动态网络的工序和工位, 在相 应的时间段内, 搬运到“蚁穴”的过程.通过开浇时 间搜索算法改变算法的起始时间 ;蚂蚁按信息素和 启发式信息为炉次选择工位, 工位信息素和全局信 息素在每代蚂蚁运行中会被更新.重复上述操作, 当计划指标达到设定的优化效果时, 即得到优化的 炼钢 -连铸作业计划 . 2.1 算法中的关键问题 工位选择策略和第 t 代至第 t +1 代间信息素 更新策略设计至关重要, 其直接影响算法的收敛速 度和所得作业计划方案的优劣 . 2.1.1 工位选择策略 工位上的信息素浓度反映了工位利用的历史信 息, 隐含资源配置规律;而工位上的启发式信息值用 于体现生产组织原则等.蚂蚁按伪随机比例选择策 略为当前工位 k 上的炉次i 从紧前工序的可选工位 集π( i, k) 中选择作业工位 k′, 即: k′= arg max k′∈π( i, k){τ α kk′( i, t) η β kk′( i, t)}, q ≤q0 Pkk′( i, t), q >q0 ( 8) 其中, q0 ∈ ( 0, 1) 为 常数, q ∈( 0, 1) 为 随机数 ; τkk′( i, t)和 ηkk′( i, t)分别表示第 t 代位于工位k 的 蚂蚁搬运炉次 i 到紧前工序工位 k′时, 工位 k′上的 信息素浓度以及与工位k′相关联基于问题的启发式 信息值 ;α和 β 分别表示控制信息素和启发式信息 影响权重的参数 . 式( 8)表示 :第 t 代位于工位k 的蚂蚁搬运炉次 i 到紧前工序工位k′之前, 先随机生成 q, 如果 q 不 大于q0 则从炉次 i 当前作业工位 k 的紧前工序所 有可选工位中找出 τα kk′( i, t) ηβ kk′( i, t) 最大的工位 k′作为下一加工工位, 否则按下式以概率 Pkk′( i, t) 来选择加工工位 : Pk k′( i, t) = τα kk ( i, t ) ηβ kk′( i, t) k′∈ ∑π( i, k) τα kk′( i, t) ηβ kk′( i, t) , s ∈ π( i, k) 0, 否则 ( 9) 根据炼钢-连铸生产中作业炉次的运行规则, 将工位上主设备利用率均衡和炉次等待时间最小作 为启发式信息, 即: ηkk′( i, t) =Q τij′k′ τ( k′) +τi j′k′ min k′∈π( i, k) μi , j′, k′ μi , j′, k′ ( 10) 其中, τ( k′) 为分配炉次 i 之前工位k′上已分配的加 工时间总和, Q 为信息素浓度常量. 2.1.2 信息素更新策略 算法中采用信息素局部和全局更新相结合的 策略. ( 1) 信息素局部更新.蚂蚁完成加工工位选择 后, 按下式进行信息素更新 : τkk′( i, t) =( 1 -ρ) τkk′( i, t) +Δτkk′( i, t) ( 11) 式中, Δτk k′( i, t) = Q( τwork/ τflow ), k′为局部最优加工工位 0, 否则 按炉次作业前的等待时间是否最小来判断加工 工位是否是局部最优工位 .ρ为信息素蒸发率, τwo rk和 τf low 分别表示炉次 i 当前总加工时间和物流 时间. ( 2) 信息素全局更新.所有蚂蚁从食物源返回 到蚁穴后, 通过计算模型的目标函数值来判断当前 解是否是当前全局最优解, 并按下式进行信息素全 局更新 : τk k′( i, t +1) =τkk′( i, t) +Δτkk′( i) ( 12) 其中, Δτk k′( i) = Q z g b , k′在全局最优路径上 0, 否则 z gb为目前找到的模型目标函数最小值. 信息素局部和全局更新后, 为防止工位上信息 素过多积累或完全蒸发, 将工位上信息素限制在 [ τmin, τmax] . 2.2 算法实现 基于生产流程网络的蚁群算法编制 N 个炉次 经过M 道工序中若干工位的炼钢-连铸作业计划 算法描述如下: Production planning Begin Step 1 初始化 . ( 1) 读取生产流程网络结构、工位状态、工位最 早可用时刻及批量计划 ; ( 2) 设置蚁群算法参数及生产流程网络中各节 点上信息素浓度, 令蚂蚁代数计数器 t =1 ; Step 2 生成铸机预定开浇时间 、炉次的作业时 间和运输时间. ( 1) 由开浇时间搜索算法生成各连铸机的预定 开浇时间; ( 2) 根据式( 2) 计算各炉次在铸机上的开始和 结束浇注时间; 第 4 期 郑 忠等:基于蚁群算法的炼钢-连铸作业计划编制方法 · 507 ·

。508 北京科技大学学报 第31卷 (3)按分布规律生成各炉次在各工序上的作业 (4)按式11)更新工位的信息素； 时间和工序间的运输时间； (5)从T1中删除任务i; Step3蚁群A(t)从“食物源”搬运所有炉次到 Loop While Ti-1≠Φ 生产流程的末道工序相应工位上， End If (1)生成与炉次数量相等的蚁群，放置在“食物 Step7判断工序(j一1)是否是生产流程的首道 源”，令工序计数器=M: 工序.若j-D1,则令j=ji-l,转到Step4:否则， (2)每只蚂蚁搬运一个炉次于炉次开始作业时 转到Step8. 刻xi,k到达相应的连铸机： Step8所有蚂蚁返回“蚁穴”，生成蚁群算法“搬 Step4工序j各工位上的所有蚂蚁对应的炉次 运”过程对应的作业计划方案按式(12)更新第t代 加入当前任务集中. 蚂蚁的全局信息素 Step5统计T中各蚂蚁路由到炉次加工工艺 Step9若满足算法终止条件，转Step 10:否则， 路径上紧前工序j的可选加工工位，计算在各工位 令t=t十l,转Step2. 上的预计开始与结束作业时间，并存储到工序j的 Step 100输出优化的炼钢一连铸作业计划. 预分配任务集合T中. End IfΦThen 转到Step6; 3仿真实例及结果分析 Else 在Windows XP下用Visual Basic6.0开发实现 「中各炉次按开始作业时间逆序排序： 了炼钢一连铸作业计划编制模型.以某炼钢厂转炉 Do 至连铸的生产流程为对象，建立如图2所示的应用 (1)由生产流程网络及T中开始作业最晚 对象模型，并利用某钢厂实际生产计划数据来测试 的炉次i的工艺路径确定由当前工序 模型和算法. j工位k到紧前工序上的可选工位 集π(i,k): (2)按式(3)计算π(i,k)各工位的预计开 连铸1 RHI 始和结束作业时间，保存到工序j的 预分配任务集合T中： (3)从「删除炉次i: 铸2 Loop While T≠Φ RH2 End If 转炉3 Step6工序广-1的预分配任务集合T-1中的 蚂蚁按工位选择策略为炉次选择加工工位. 图2炼钢连铸生产流程 Fig 2 Production process of steelmaking and con tinuous casting IfTi-1=ΦThen 转到Step7; 以某天8h的生产批量计划(7浇次，37炉次) Else 为例，在己知钢种工艺路径，以及铸机上浇注顺序等 T一1中的所有炉次按平均预计开始作业时 条件下，钢种在工序上作业时间和工序间运输时间 间逆序排序； 按正态分布选择，其均值由生产实绩统计来确定，方 Do 差则参照统计数据并根据工艺和生产组织要求由人 (1)搬运炉次i的蚂蚁按工位选择策略 工设置，采用所建数学模型和基于生产流程网络的 (式(8)从π(i,k)中选择加工工位 蚁群算法进行作业计划编制. k: 蚁群算法中参数设置为：蚂蚁数按炉次数37设 (2)按式(6)调整炉次i在工位k上的开 定，最大进化代数为100，信息素影响因子为2，启发 始和结束作业时间； 式信息影响因子为5，信息素挥发率p=0.l,tmim= (3)更新工位k的可用时间区间，统计炉 0.00L,tmx=10,q0=0.1.在CPU为P42.8G, 次i在工位k上的作业等待时间和冲 512M内存的台式机上进行多次实验，算法均能在 突时间： 进化30代（约40s)内收敛到优化解，模型软件系统

( 3) 按分布规律生成各炉次在各工序上的作业 时间和工序间的运输时间 ; Step 3 蚁群 A( t) 从“食物源”搬运所有炉次到 生产流程的末道工序相应工位上. ( 1) 生成与炉次数量相等的蚁群, 放置在“食物 源”, 令工序计数器 j =M ; ( 2) 每只蚂蚁搬运一个炉次于炉次开始作业时 刻 x i, j , k到达相应的连铸机; Step 4 工序 j 各工位上的所有蚂蚁对应的炉次 加入当前任务集 Γ中 . Step 5 统计 Γ中各蚂蚁路由到炉次加工工艺 路径上紧前工序j′的可选加工工位, 计算在各工位 上的预计开始与结束作业时间, 并存储到工序 j′的 预分配任务集合 Tj′中. If Γ=ΥThen 转到 Step 6 ; Else Γ中各炉次按开始作业时间逆序排序; Do ( 1) 由生产流程网络及 Γ中开始作业最晚 的炉次 i 的工艺路径确定由当前工序 j 工位k 到紧前工序 j′上的可选工位 集 π( i, k ) ; ( 2) 按式( 3)计算 π( i, k) 各工位的预计开 始和结束作业时间, 保存到工序 j′的 预分配任务集合 Tj′中; ( 3) 从 Γ删除炉次i ; Loop While Γ≠Υ End If Step 6 工序 j -1 的预分配任务集合 Tj -1中的 蚂蚁按工位选择策略为炉次选择加工工位. If Tj -1 =ΥThen 转到 Step 7 ; Else Tj -1中的所有炉次按平均预计开始作业时 间逆序排序; Do ( 1) 搬运炉次 i 的蚂蚁按工位选择策略 (式( 8)) 从 π( i, k ) 中选择加工工位 k′; ( 2) 按式( 6) 调整炉次 i 在工位 k′上的开 始和结束作业时间; ( 3) 更新工位 k′的可用时间区间, 统计炉 次 i 在工位k′上的作业等待时间和冲 突时间; ( 4) 按式( 11)更新工位的信息素; ( 5) 从 Tj-1中删除任务 i ; Loop While Tj -1 ≠Υ End If Step 7 判断工序( j -1) 是否是生产流程的首道 工序.若 j -1 >1, 则令 j =j -1, 转到 Step 4 ;否则, 转到S tep 8 . Step 8 所有蚂蚁返回“蚁穴”, 生成蚁群算法“搬 运”过程对应的作业计划方案, 按式( 12)更新第 t 代 蚂蚁的全局信息素 . Step 9 若满足算法终止条件, 转 Step 10 ;否则, 令 t =t +1, 转 Step 2 . Step 10 输出优化的炼钢-连铸作业计划. End 3 仿真实例及结果分析 在 Windows XP 下用 Visual Basic 6.0 开发实现 了炼钢-连铸作业计划编制模型.以某炼钢厂转炉 至连铸的生产流程为对象, 建立如图 2 所示的应用 对象模型, 并利用某钢厂实际生产计划数据来测试 模型和算法 . 图 2 炼钢-连铸生产流程 Fig.2 Production process of st eelmaking and con tinuous casting 以某天 8 h 的生产批量计划( 7 浇次, 37 炉次) 为例, 在已知钢种工艺路径, 以及铸机上浇注顺序等 条件下, 钢种在工序上作业时间和工序间运输时间 按正态分布选择, 其均值由生产实绩统计来确定, 方 差则参照统计数据并根据工艺和生产组织要求由人 工设置, 采用所建数学模型和基于生产流程网络的 蚁群算法进行作业计划编制 . 蚁群算法中参数设置为 :蚂蚁数按炉次数 37 设 定, 最大进化代数为 100, 信息素影响因子为 2, 启发 式信息影响因子为 5, 信息素挥发率 ρ=0.1, τmin = 0.001, τmax =10, q0 =0.1 .在 CPU 为 P4 2.8 G, 512 M 内存的台式机上进行多次实验, 算法均能在 进化 30 代(约 40 s)内收敛到优化解, 模型软件系统 · 508 · 北 京 科 技 大 学 学 报 第 31 卷