基于遗传算法的可重入钢管生产优化调度

D01:10.133741.is9m1001053x.2009.08.23 第31卷第8期 北京科技大学学报 Vol.31 No.8 2009年8月 Journal of University of Science and Technology Beijing Aug.2009 基于遗传算法的可重入钢管生产优化调度 陈晓慧12) 张启忠2易树平段鹰 赖志柱引 1)重庆大学机械传动国家重点实验室，重庆4000302)重庆大学工业工程研究所，重庆4000303)贵州省毕节学院数学系，毕节551700 摘要在可重入冷拔无缝钢管生产的计划和调度中，根据四个条件对工件进行组批，通过规则假设把组批后的批钢管看作 单个加工工件，建立以最后完工时间、交货期满意度和机器总负荷为目标的多目标组批排序优化模型，设定其约束条件，采用 基于Pareto的混合遗传算法对模型进行优化求解.通过算例证明该模型的有效性和合理性. 关键词钢管；可重入生产：混合遗传算法：优化调度 分类号TP273.1 Optimal scheduling of steel tube re-entrant lines based on a genetic algorithm CHEN Xiao-hui2.ZHANG Qi-zhong2.YI Shurping2.DUAN Y ing?).LAIZhi-zhu 1)State Key Lab of Mechanical Transmission.Chongqing University.Chongjing 400030.China 2)Institute of Indust rial Engineering.Chongqing University.Chongqing 400030.China 3)Department of Mathematics,Bijie University.Bijie 551700.China ABSTRACI In order to make planning and scheduling for colddrawn seamless steel tube re-entrant lines,workpieces were grouped together according to four conditions.then the grouped steel tubes wee taken as one workpiece through the assumption of conditions The model of multi-objective order-grouping scheduling optimization w as studied.where the final completion time.the delivery satis- faction and the total load of machine were concerned.In addition,the constraint conditions wee put forward.The Paretobased hy- brid genetic algorithm was used to make the optimal solution of the model.The effectiveness and rationality of the optimization mode w as prov ed by an example. KEY WORDS steel tube:re-entrant lines;hybiid genetic algonithm:optimization scheduling 随着市场需求的不断变化，无缝钢管生产逐渐 文献6一刃把钢管调度问题看作作业车间调度、流 呈现出多品种、小批量面向订单制造的趋势.无缝 水车间调度来进行优化求解. 钢管的生产过程复杂，要经过管坯连铸、加热、穿孔、 以上研究中，钢管生产流程大多只涉及一道次 减径、矫直和表面处理等多道工序，流经多个车间. 流程，也就是作业车间调度(job shop)和流水车间调 钢管按照壁厚、外径、交货长度、孔型和钢级等工艺 度(flow shop)模型，但在实际的钢管加工企业中，由 参数分为不同的规格，其工艺方法和生产路线多样. 于产品规格范围大、机器设备数量及性能有限致使 面对复杂的钢管生产计划调度的难题，现有研究主 某些工序存在多道次加工，呈现出可重入生产(re 要集中在组批计划和轧批排序计划！.组批计划将 entrant lines))方式的特点，即工件在加工工艺路线 用户合同转换为轧制批计划，如文献2]提出了合同 的不同阶段多次访问同一加工站.由于有别于传统 组批优化问题的启发式算法：轧批排序计划将组成 离散制造业Job Shop与Flow Shop两种生产制造系 的多个轧制批进行生产顺序排定，文献[)建立了轧 统的特性，Kumar等将其归类为第三种生产制造方 批排序模型并采用遗传算法求解，文献[4把钢管生 式7.作为一类典型的离散事件动态系统，可重入 产中批量计划抽象为多阶段批量计划与调度问题， 生产方式不仅存在于冷拔无缝钢管生产中，在机械 收稿日期：200904-04 基金项目：国家自然科学基金资助项目(No.70871127):重庆市科技攻关计划资助项目(Na CSTC2008AB3032):重庆大学211"工程三期创新 人才培养计划资助项目(No.S一09107 作者简介：陈晓慧(1969-)，女，博土，副教授，E-mail:chenxiaohui@cqu.adu.cm

基于遗传算法的可重入钢管生产优化调度 陈晓慧 1, 2) 张启忠 2) 易树平 2) 段 鹰 2) 赖志柱 3) 1) 重庆大学机械传动国家重点实验室, 重庆 400030 2) 重庆大学工业工程研究所, 重庆 400030 3) 贵州省毕节学院数学系, 毕节 551700 摘 要 在可重入冷拔无缝钢管生产的计划和调度中, 根据四个条件对工件进行组批, 通过规则假设把组批后的批钢管看作 单个加工工件, 建立以最后完工时间、交货期满意度和机器总负荷为目标的多目标组批排序优化模型, 设定其约束条件, 采用 基于 Pareto 的混合遗传算法对模型进行优化求解.通过算例证明该模型的有效性和合理性. 关键词 钢管;可重入生产;混合遗传算法;优化调度 分类号 TP273.1 Optimal scheduling of steel tube re-entrant lines based on a genetic algorithm CHEN Xiao-hui 1, 2) , ZHANG Qi-zhong 2) , Y I Shu-ping 2) , DU AN Y ing 2) , LAI Zhi-zhu 3) 1) St at e Key Lab of Mechanical Transmission, Chongqing University, Chongqing 400030, China 2) Institut e of Industrial Engineering, Chongqing University, Chongqing 400030, China 3) Department of Mathematics, Bijie University, Bijie 551700, China ABSTRACT In o rder to make planning and scheduling for cold-drawn seamless steel tube re-entrant lines, workpieces were g rouped tog ether acco rding to four conditions, then the grouped steel tubes w ere taken as one workpiece throug h the assumption of conditions. The model of multi-objective order-g rouping scheduling optimization w asstudied, where the final completion time, the deliv ery satis￾faction and the to tal load of machine were concerned .I n addition, the constraint conditions w ere put fo rward.The Pareto-based hy￾brid g enetic alg orithm was used to make the o ptimal solution of the model.The effectiveness and rationality of the optimization model w as prov ed by an example. KEY WORDS steel tube;re-entrant lines ;hybrid genetic algo rithm ;optimization scheduling 收稿日期:2009-04-04 基金项目:国家自然科学基金资助项目( No .70871127) ;重庆市科技攻关计划资助项目( No.CS TC2008AB3032) ;重庆大学“ 211”工程三期创新 人才培养计划资助项目( No .S-09107) 作者简介:陈晓慧( 1969—) , 女, 博士, 副教授, E-mail:chenxiaohui@cqu.edu.cn 随着市场需求的不断变化, 无缝钢管生产逐渐 呈现出多品种、小批量面向订单制造的趋势.无缝 钢管的生产过程复杂, 要经过管坯连铸 、加热 、穿孔 、 减径、矫直和表面处理等多道工序, 流经多个车间 . 钢管按照壁厚、外径、交货长度 、孔型和钢级等工艺 参数分为不同的规格, 其工艺方法和生产路线多样 . 面对复杂的钢管生产计划调度的难题, 现有研究主 要集中在组批计划和轧批排序计划 [ 1] .组批计划将 用户合同转换为轧制批计划, 如文献[ 2] 提出了合同 组批优化问题的启发式算法;轧批排序计划将组成 的多个轧制批进行生产顺序排定, 文献[ 3] 建立了轧 批排序模型并采用遗传算法求解, 文献[ 4] 把钢管生 产中批量计划抽象为多阶段批量计划与调度问题, 文献[ 6-7] 把钢管调度问题看作作业车间调度、流 水车间调度来进行优化求解 . 以上研究中, 钢管生产流程大多只涉及一道次 流程, 也就是作业车间调度( job shop) 和流水车间调 度( flow shop) 模型, 但在实际的钢管加工企业中, 由 于产品规格范围大、机器设备数量及性能有限致使 某些工序存在多道次加工, 呈现出可重入生产( re￾entrant lines) 方式的特点, 即工件在加工工艺路线 的不同阶段多次访问同一加工站.由于有别于传统 离散制造业 Job Shop 与 Flow Shop 两种生产制造系 统的特性, Kumar 等将其归类为第三种生产制造方 式[ 7] .作为一类典型的离散事件动态系统, 可重入 生产方式不仅存在于冷拔无缝钢管生产中, 在机械 第 31 卷 第 8 期 2009 年 8 月 北 京 科 技 大 学 学 报 Journal of University of Science and Technology Beijing Vol .31 No.8 Aug.2009 DOI :10.13374/j .issn1001 -053x.2009.08.023

。1068* 北京科技大学学报 第31卷 加工行业的大部件生产和高精密器件的多道次加工 1 中，以及半导体生产加工中也普遍存在8.可重入 可重入钢管生产线描述及优化调度模型的 建立 钢管生产，因其路径的高度重入、复杂的工艺过程、 不同的设备特性以及多品种小批量生产方式等特点 1.1可重入钢管生产线描述 构成了非常复杂的约束条件，使得这类系统调度问 冷拔无缝钢管的生产主要经过管坯连铸、热轧、 题的求解困难.本研究将结合冷拔无缝钢管生产的 酸洗润滑、冷拔、退火、矫直和表面处理等工序，以 可重入性特点，根据四个条件对工件进行组批，建立 某钢管公司的冷拔无缝钢管生产流程为例（工艺流 多目标轧批排序优化模型，并采用基于Pareto的混 程如图1所示)，其热轧工段、精整工段的加工为单 合遗传算法对优化模型进行求解. 道次加工，而在冷拔工段时由于产成品规格范围大、 管坯 酸洗修磨 冷剪 加热 穿孔 扎管 打头 热轧工段 半成品打头 退火 冷拔 润滑 检验修磨 酸洗 冷拔工段 轿直 切管 成品检验 喷印 包扎入库浸油 过秤 打捆小薄管 精整工段 入库过秤 打辋探伤收集炉管、流体管 入库小过秤 打捆结构管 图1某钢管公司冷拔无缝钢管生产工艺流程 Fig.I Technological pmces of the production line in a steel tube pant 机器设备数量及性能有限，钢管需要多道次冷拔，因 工站J:包含p台机器，且站前存在缓冲区B:,假设 此在酸洗、检验修磨、润滑、冷拔和退火之间存在可 缓冲区容量B;为无限大，工作站J;内等待加工、正 重入生产 在加工和已加工完尚未送往下一加工站的所有工件 1.2组批计划设定 都在缓冲区B:内占有位置.每一工件需加工D道 在可重入冷拔无缝钢管的计划和调度中，当工 次，每一工序由对应的加工站J:内的一台机器单独 件满足以下条件时可以组合成为同一轧批：()加 完成，设工件W。第k道次在J:加工站上的加工时 工工艺路径相同：(2)各工序加工时间相同：(3)合 间为h.为简化模型，这里暂不考虑工件进出系统 同交货期相近或相同：(4)成品管规格的壁厚、外 及在各加工站间的传输时间.可重入钢管生产系统 径、交货长度、孔型和钢级相同. 的轧批排序模型如图2所示.图中，J,表示第1个 为了让复杂模型能得到有效优化，借鉴Job 加工站，B:为加工站J:前的缓冲站，MP:为加工站 Shop和Flow Shop调度的优化建模思路，本文设定 J,中的第P,台机器 三个规则： K道次 规则1同一组批内的钢管不作批内排序： M M 规则2每批钢管生产时的准备时间和辅助时 M 间记入加工时间中： I OUT 规则3由于同一组批内每根钢管的工艺参数 M 相同，因此把一批钢管看作一个加工工件，加工时间 J 为所有钢管加工时间之和， 图2可重入钢管生产系统的轧批排序模型 13轧批排序问题描述 Fig 2 Scheduling model of a re-entrant steel tube production system 经过组批规则形成的N批待加工钢管，在可重 入生产模型下，需要对轧批加工顺序进行排序 优化调度满足以下约束条件： 参考Kumar的定义7，N批待加工冷拔无缝 (1)任何一个工件只能在前一道工序完成后， 钢管的可重入生产可简化为N个工件T个工序的 方能进入后一道工序： 可重入生产系统：T个加工站J1,J2,,J,每个加 (2)不同工件的工序之间没有先后约束：

加工行业的大部件生产和高精密器件的多道次加工 中, 以及半导体生产加工中也普遍存在[ 8] .可重入 钢管生产, 因其路径的高度重入、复杂的工艺过程 、 不同的设备特性以及多品种小批量生产方式等特点 构成了非常复杂的约束条件, 使得这类系统调度问 题的求解困难.本研究将结合冷拔无缝钢管生产的 可重入性特点, 根据四个条件对工件进行组批, 建立 多目标轧批排序优化模型, 并采用基于 Pareto 的混 合遗传算法对优化模型进行求解. 1 可重入钢管生产线描述及优化调度模型的 建立 1.1 可重入钢管生产线描述 冷拔无缝钢管的生产主要经过管坯连铸、热轧、 酸洗润滑 、冷拔 、退火 、矫直和表面处理等工序 .以 某钢管公司的冷拔无缝钢管生产流程为例( 工艺流 程如图 1 所示) , 其热轧工段 、精整工段的加工为单 道次加工, 而在冷拔工段时由于产成品规格范围大、 图 1 某钢管公司冷拔无缝钢管生产工艺流程 Fig.1 Technologi cal process of the production line in a steel tube plant 机器设备数量及性能有限, 钢管需要多道次冷拔, 因 此在酸洗 、检验修磨、润滑、冷拔和退火之间存在可 重入生产 . 1.2 组批计划设定 在可重入冷拔无缝钢管的计划和调度中, 当工 件满足以下条件时可以组合成为同一轧批:( 1) 加 工工艺路径相同 ;( 2) 各工序加工时间相同;( 3) 合 同交货期相近或相同;( 4) 成品管规格的壁厚、外 径、交货长度、孔型和钢级相同 . 为了让复杂模型能得到有效优化, 借鉴 Job Shop 和 Flow Shop 调度的优化建模思路, 本文设定 三个规则 : 规则 1 同一组批内的钢管不作批内排序 ; 规则 2 每批钢管生产时的准备时间和辅助时 间记入加工时间中; 规则 3 由于同一组批内每根钢管的工艺参数 相同, 因此把一批钢管看作一个加工工件, 加工时间 为所有钢管加工时间之和 . 1.3 轧批排序问题描述 经过组批规则形成的 N 批待加工钢管, 在可重 入生产模型下, 需要对轧批加工顺序进行排序 . 参考 Kumar 的定义[ 7] , N 批待加工冷拔无缝 钢管的可重入生产可简化为N 个工件 T 个工序的 可重入生产系统 :T 个加工站J 1, J 2, …, J t , 每个加 工站 J i 包含 pi 台机器, 且站前存在缓冲区 Bi , 假设 缓冲区容量 Bi 为无限大, 工作站 J i 内等待加工 、正 在加工和已加工完尚未送往下一加工站的所有工件 都在缓冲区 Bi 内占有位置.每一工件需加工 D 道 次, 每一工序由对应的加工站 Ji 内的一台机器单独 完成, 设工件 Wo 第k 道次在J i 加工站上的加工时 间为 hoki .为简化模型, 这里暂不考虑工件进出系统 及在各加工站间的传输时间 .可重入钢管生产系统 的轧批排序模型如图 2 所示.图中, Jt 表示第 t 个 加工站, B t 为加工站J t 前的缓冲站, MtPt为加工站 J t 中的第Pt 台机器 . 图 2 可重入钢管生产系统的轧批排序模型 Fig.2 Scheduling model of a re-entrant st eel tube production system 优化调度满足以下约束条件 : ( 1) 任何一个工件只能在前一道工序完成后, 方能进入后一道工序; ( 2) 不同工件的工序之间没有先后约束; · 1068 · 北 京 科 技 大 学 学 报 第 31 卷

第8期 陈晓慧等：基于遗传算法的可重入钢管生产优化调度 。1069。 (3)每台机器同一时刻只能加工一个工件： 关系：式(8)表示一工件只能先加工完前一道次之后 (4)每个工件每道次在各个机器上的加工时间 才能进行下一道次加工，式(10)表示工序'贴在加 是确定的： 工站中有且仅有一台机器为其加工. (5)每个工件的可重入次数是确定的： (2)交货期满意度f2.随着产品生命周期的日 (6)每工件只有在加工完前一道次之后才能进 益缩短和客户需求水平的不断提高，企业对于准时 行下一道次加工： 交货的要求越来越高，产品的提前/拖期惩罚值也成 (7)在零时刻，所有的工件都可被加工. 为衡量系统调度性能的一个主要目标.基于图2轧 2钢管生产优化调度目标函数 批排序模型，工件W。的交货期窗口表示为[e, lo,其中e、l。分别为工件W。的最早和最晚交货 生产计划调度的目标包括基于加工完成时间的 期，当clo,称工件 指标、基于交货期的性能指标、基于库存的指标、基 W。拖期.如果工件在其交货期窗口内完工，则没有 于生产成本的指标以及综合性能指标等.考虑到钢 惩罚；否则不论工件W。提前或者拖期，都将对工件 管企业生产实际的需求，本文选择完成时间、交货期 W。的提前、拖期进行惩罚.总惩罚值f2可表示为： 满意程度和设备利用率三项指标建立多目标优化函 数.完成时间用工件的最后完工时间1度量，交货 f= 会ae+ase》 (12) 期满意度指标用提前/拖期(E/T)惩罚值f2度量， eo-Co Co<eo 设备利用率目标用机器总负荷f3度量.因此，多目 z1(co)= (13) 0 e≤c≤b 标调度优化的目标函数为： f(=minf1 (1) Co-lo co lo z2c)= (14) f(2=minf2 (2) 0 e≤co≤lo f(3到=minf3 (3) a1十a2=1 (15) (1)最后完工时间f.基于图2的轧批排序模 式中，a1、a2分别为工件W。的单位提前、拖期惩罚 型，现有N批待加工钢管.设工件W。第k道次在 权重，z1(c)、z2(co)分别为工件W。的提前、拖期 加工站上的加工工序记Vk:.最后完工时间f的 惩罚函数. 数学表达如下： (3)机器总负荷∫3.对一生产系统来说机器 f=max{co} (4) 是其重要的资源之一，机器的使用情况直接体现生 Co-XODT (5) 产系统的效率和效益.本文通过机器总负荷∫3的 约束条件如下： 情况来体现设备利用率目标. xaki一So贴=hai (6) f= (16) Xok!-hok1 Xoki;Vaki <Vokl (7) 6(k+i一k⊙0 (8) 空2unKe (17) xah≥hak,Hi其中，%ip=0或1 (9) 式(17)表示设备资源的有限性，任何一台设备的总 =1,P=1,29A 负荷都小于整个调度时长 (10) yahp=0或1,0=1,2，；N: 3基于Pareto遗传算法的模型求解 k=1,2,…D;i=L,2,,t;P=1,2,P: 针对轧批排序优化问题，需采用优化算法求解. (11) 常用的优化调度方法有多目标加权法、动态规划法、 式中，co是工件Wo的最后完工时间；saki、xaki和hak 局部搜索算法、交互式仿真方法以及遗传算法等. 是工序V:的开始时间、完成时间和处理时间；<表 对于遗传算法，Reeves9和Chen!1等通过对Fow 示了前后关系，Voi<Vk意味着Vak领先Vaki;如果 Shop调度研究结果表明，遗传算法优于模拟退火算 工件W。第k道次的第i工序分配给了对应加工站 法、邻近搜索算法和SPIRIT算法.文献I刂证明了 J下的第P台机器，则VakiP-=l;否则YakiPi=0. 遗传算法在可重入生产中具有优良的求解能力.进 式(6)和(9)表示工序'k:的开始时间、加工时 一步地，文献[I2-l3]研究了基于Pareto遗传算法 间和结束时间的关系，式(7)表示两工序之间的前后 的多目标优化方法，相比其他优化算法，该方法在收

( 3) 每台机器同一时刻只能加工一个工件; ( 4) 每个工件每道次在各个机器上的加工时间 是确定的 ; ( 5) 每个工件的可重入次数是确定的; ( 6) 每工件只有在加工完前一道次之后才能进 行下一道次加工 ; ( 7) 在零时刻, 所有的工件都可被加工 . 2 钢管生产优化调度目标函数 生产计划调度的目标包括基于加工完成时间的 指标 、基于交货期的性能指标 、基于库存的指标 、基 于生产成本的指标以及综合性能指标等 .考虑到钢 管企业生产实际的需求, 本文选择完成时间、交货期 满意程度和设备利用率三项指标建立多目标优化函 数.完成时间用工件的最后完工时间 f 1 度量, 交货 期满意度指标用提前/拖期( E/T) 惩罚值 f 2 度量, 设备利用率目标用机器总负荷 f 3 度量 .因此, 多目 标调度优化的目标函数为 : f ( 1) =min f 1 ( 1) f ( 2) =min f 2 ( 2) f ( 3) =min f 3 ( 3) ( 1) 最后完工时间 f 1 .基于图 2 的轧批排序模 型, 现有 N 批待加工钢管.设工件 Wo 第k 道次在 Ji 加工站上的加工工序记 Vok i .最后完工时间 f 1 的 数学表达如下: f 1 =max{co} ( 4) co =x ODT ( 5) 约束条件如下: xok i -soki =hoki ( 6) xok l -hok l ≥xoki , Voki Vokl ( 7) so( k +1) i -soki >0 ( 8) xoki ≥hoki , i 其中, yokiP =0 或 1 ( 9) ∑ P i P =0 yokiP =1, P =1, 2, …, Pi ( 10) yokiP =0 或 1, o =1, 2, …, N ; k =1, 2, …, D ;i =1, 2, …, t ;P =1, 2, …, Pi ( 11) 式中, co 是工件 Wo 的最后完工时间 ;soki 、xok i和hoki 是工序 Voki的开始时间、完成时间和处理时间; 表 示了前后关系, Voki Vok l意味着 Vok l领先 Voki ;如果 工件 Wo 第k 道次的第i 工序分配给了对应加工站 Ji 下的第P 台机器, 则 yok iP =1 ;否则 yokiP =0 . 式( 6)和( 9)表示工序 Vok i的开始时间、加工时 间和结束时间的关系, 式( 7)表示两工序之间的前后 关系;式( 8) 表示一工件只能先加工完前一道次之后 才能进行下一道次加工, 式( 10)表示工序 Voki在加 工站Ji 中有且仅有一台机器为其加工. ( 2) 交货期满意度 f 2 .随着产品生命周期的日 益缩短和客户需求水平的不断提高, 企业对于准时 交货的要求越来越高, 产品的提前/拖期惩罚值也成 为衡量系统调度性能的一个主要目标.基于图 2 轧 批排序模型, 工件 Wo 的交货期窗口表示为[ eo, lo] , 其中 eo 、lo 分别为工件 Wo 的最早和最晚交货 期,当 co lo, 称工件 Wo 拖期 .如果工件在其交货期窗口内完工, 则没有 惩罚 ;否则不论工件 Wo 提前或者拖期, 都将对工件 Wo 的提前、拖期进行惩罚.总惩罚值 f 2 可表示为: f 2 = ∑ N o =1 ( a1 z 1( co) +a2 z 2( co)) ( 12) z 1( co) = eo -co co lo 0 eo ≤co ≤lo ( 14) a1 +a2 =1 ( 15) 式中, a1 、a2 分别为工件 Wo 的单位提前、拖期惩罚 权重, z 1( co) 、z 2 ( co )分别为工件 Wo 的提前、拖期 惩罚函数. ( 3) 机器总负荷 f 3 .对一生产系统来说, 机器 是其重要的资源之一, 机器的使用情况直接体现生 产系统的效率和效益 .本文通过机器总负荷 f 3 的 情况来体现设备利用率目标 . f 3 = ∑ N o =0 ∑ D k =0 ∑ T i =0 ∑ P i P =0 hokiyokiP ( 16) ∑ N o =0 ∑ D k =0 hok iyokiP <max{co} ( 17) 式( 17)表示设备资源的有限性, 任何一台设备的总 负荷都小于整个调度时长. 3 基于 Pareto 遗传算法的模型求解 针对轧批排序优化问题, 需采用优化算法求解. 常用的优化调度方法有多目标加权法 、动态规划法、 局部搜索算法 、交互式仿真方法以及遗传算法等. 对于遗传算法, Reeves [ 9] 和 Chen [ 10] 等通过对 Flow Shop 调度研究结果表明, 遗传算法优于模拟退火算 法 、邻近搜索算法和SPIRIT 算法.文献[ 11] 证明了 遗传算法在可重入生产中具有优良的求解能力.进 一步地, 文献[ 12-13] 研究了基于 Pareto 遗传算法 的多目标优化方法, 相比其他优化算法, 该方法在收 第 8 期 陈晓慧等:基于遗传算法的可重入钢管生产优化调度 · 1069 ·

。1070 北京科技大学学报 第31卷 敛性和多样性上具有更大的优势.本文采用的 3.2交叉和变异 Pareto遗传算法包括交叉、变异、选择、离散变量圆 为了保证优秀个体不会因为交叉变异被破坏， 整算子、小生境算子和Pareto解集过滤器六个算 采用精英保留策略，使当前群体中适应度最高的 子.其中，小生境能够阻止种群的早熟收敛，使个体 Pareto解个体不参与交叉和变异.为了保证Pareto 均匀分布在Pareto前沿，从而维持种群的多样性. 解的多样性，每代进化过程中对适应度非常接近的 Pareto解集过滤器能过滤出每一代的非劣解，最终 个体采用小生境技术处理：因为在运算过程中，人工 形成均匀分布的Pareto解集14 群体规模有限和算子产生的随机误差导致基因漂移 3.1编码与解码 现象.小生境技术能防止基因漂移，使群体均匀地 可重入生产调度模型不仅要确定工序的加工顺 分布在Pareto最优解集中坶 序，还需为每道工序选择一台合适的机器，因此仅采 3.3终止条件 用基于工序的传统编码方法不能得到问题的解.为 设定：种群规模P,最大进化代数T,当运行代 适应可重入生产系统的特殊性，采用染色体两层编 数达到T时，进化终止 码方案1月.第1层编码为各工序的优先权随机数， 4应用算例与仿真结果分析 1,Q]中产生，其中Q表示总的工序数.第2层 编码是各工序所选择的加工机器，从原始数据表中 在可重入钢管生产中，假设工件经组批计划得 随机选出对应机器.对于编码方案的解码主要是排 到四批待加工钢管，分别是形、W2、W3和W4,可 定工序加工的顺序，将各工件的加工工序看作关键 重入生产系统为三个加工站，五台机器(J1为2台， 路径网络图上的顶点.结合各工序的优先权随机数 J2为2台，J3为1台)，计为M11、M12、M21、M22和 对关键路径网络图进行拓扑排序后得到每个工件的 M31,其主要数据如表1所示.根据上文所述的轧批 最后完成时间. 排序计划求解最优化排序. 表1工序加工时间表 Table I Pmduct ion time of each process 工件 工序号V 加工时间（机器号） 交货期窗口[a,勾 工件工序号1 加工时间（机器号） 交货期窗口e。lg Vi 4(Mn).5(Mp) Va 2(M1,3(M12 Vie 6(Mu),5(Mn) V32 4(M21,3(M22 ViB 4(M) Va3 5(M3i) Via 5(Mm,3(Me) 【28.30 3 V 4M1i,5(M12) 【20.2☑ V12 3(Ma).4(M) V 5M2i,4(M22J Vis 1(M) V23 3(M3 V2u 3(Mi,5(M Vat 6(M1,4(M12 V22 3(M),5(Mm) Vaz 7(M2iJ,5(M22) V23 1(M) Vas 5(M3) [25,27 4 [27,29 V22 3(Mu),3(Mp) Ve 5(M1i,3(M12) V22 5(Mu,2(M2J Ve 4M2,3(M22) V28 3(M) Ves 2(M3) 根据上述算法设计，采用MATLAB编程遗传 表2最优化结果 算法中的运行参数为：群体大小M=100,终止代数 Table 2 Optimal solutions T=3000.交叉概率P=0.7,变异概率Pm=0.01. 优化算法 最后完工时间/h交货期满意度机器总负荷 设客户满意度函数中提前，拖期惩罚权重a1、a2各 基于Pareto的 29 0 78 为05.当三个目标同时优化时，由于Pareto最优 GA SPT规则 29 78 解集构成曲面，无法通过图直观显示，从解集中可获 取一个Pareto最优解，如表2所示，图3为Pareto最 从基于Pareto的遗传算法得到的最优解及 优解对应的甘特图.相应地，用最短加工时间 SPT规则得到的解，各工件的最后完工时间c。如表 (SPT)规则进行优化，其结果如表2所示. 3所示.从表2、表3可知，在该案例的优化中，基于

敛性和多样性上具有更大的优势.本文采用的 Pareto 遗传算法包括交叉、变异、选择、离散变量圆 整算子 、小生境算子和 Pareto 解集过滤器六个算 子.其中, 小生境能够阻止种群的早熟收敛, 使个体 均匀分布在 Pareto 前沿, 从而维持种群的多样性 . Pareto 解集过滤器能过滤出每一代的非劣解, 最终 形成均匀分布的 Pareto 解集[ 14] . 3.1 编码与解码 可重入生产调度模型不仅要确定工序的加工顺 序, 还需为每道工序选择一台合适的机器, 因此仅采 用基于工序的传统编码方法不能得到问题的解 .为 适应可重入生产系统的特殊性, 采用染色体两层编 码方案[ 15] .第 1 层编码为各工序的优先权随机数, 在[ 1, Q] 中产生, 其中 Q 表示总的工序数 .第 2 层 编码是各工序所选择的加工机器, 从原始数据表中 随机选出对应机器.对于编码方案的解码主要是排 定工序加工的顺序, 将各工件的加工工序看作关键 路径网络图上的顶点, 结合各工序的优先权随机数 对关键路径网络图进行拓扑排序后得到每个工件的 最后完成时间. 3.2 交叉和变异 为了保证优秀个体不会因为交叉变异被破坏, 采用精英保留策略, 使当前群体中适应度最高的 Pareto 解个体不参与交叉和变异.为了保证 Pareto 解的多样性, 每代进化过程中对适应度非常接近的 个体采用小生境技术处理;因为在运算过程中, 人工 群体规模有限和算子产生的随机误差导致基因漂移 现象 .小生境技术能防止基因漂移, 使群体均匀地 分布在 Pareto 最优解集中[ 14] . 3.3 终止条件 设定 :种群规模 P, 最大进化代数 T, 当运行代 数达到 T 时, 进化终止. 4 应用算例与仿真结果分析 在可重入钢管生产中, 假设工件经组批计划得 到四批待加工钢管, 分别是 W1 、W2 、W3 和 W4, 可 重入生产系统为三个加工站, 五台机器( J 1 为 2 台, J 2 为 2 台, J 3 为 1 台), 计为 M11 、M12 、M21 、M22和 M31, 其主要数据如表1 所示.根据上文所述的轧批 排序计划求解最优化排序. 表 1 工序加工时间表 Table 1 Production time of each process 工件 工序号 Vok i 加工时间( 机器号) 交货期窗口[ eo, lo] V 111 4( M 11) , 5( M 12) V 112 6( M 21) , 5( M 22) 1 V 113 4( M 31 ) [ 28, 30] V 121 5( M 11 ) , 3( M 12 ) V 122 3( M 21 ) , 4( M 22 ) V 123 1( M 31 ) V 211 3( M 11 ) , 5( M 12 ) V 212 3( M 21 ) , 5( M 22 ) 2 V 213 1( M 31 ) [ 25, 27] V 221 3( M 11) , 3( M 12) V 222 5( M 21) , 2( M 22) V 223 3( M 31) 工件 工序号 Vok i 加工时间( 机器号) 交货期窗口[ eo, l o] V 311 2( M11) , 3( M12) V 312 4( M21) , 3( M22) 3 V 313 5( M31 ) [ 20, 22] V 321 4( M11 ) , 5( M12 ) V 322 5( M21 ) , 4( M22 ) V 323 3( M31 ) V 411 6( M11 ) , 4( M12 ) V 412 7( M21 ) , 5( M22 ) 4 V 413 5( M31 ) [ 27, 29] V 421 5( M11) , 3( M12) V 422 4( M21) , 3( M22) V 423 2( M31) 根据上述算法设计, 采用 MAT LAB 编程, 遗传 算法中的运行参数为:群体大小 M =100, 终止代数 T =3 000, 交叉概率 Pc =0.7, 变异概率 Pm =0.01 . 设客户满意度函数中提前 、拖期惩罚权重 a1 、a2 各 为 0.5 .当三个目标同时优化时, 由于 Pareto 最优 解集构成曲面, 无法通过图直观显示, 从解集中可获 取一个Pareto 最优解, 如表 2 所示, 图3 为 Pareto 最 优解对 应的甘特图 .相应地, 用 最短加工时 间 ( SPT)规则进行优化, 其结果如表 2 所示. 表 2 最优化结果 Table 2 Optimal solutions 优化算法 最后完工时间/ h 交货期满意度 机器总负荷 基于 Pareto 的 29 0 78 GA S PT 规则 29 1 78 从基于 Pareto 的遗传算法得到的最优解及 SPT 规则得到的解, 各工件的最后完工时间 co 如表 3 所示 .从表 2 、表 3 可知, 在该案例的优化中, 基于 · 1070 · 北 京 科 技 大 学 学 报 第 31 卷

第8期 陈晓慧等：基于遗传算法的可重入钢管生产优化调度 。1071。 dergrouping pmoblem.Ind Eng Manage.2004(1):86 机器4 M34☐ 3 (李虎.霍佳震.钢管生产的合同组批优化算法.工业工程与 管理，20041)：86 M4 33 [3 Lu F.Tian G H.Solving scheduling problems of molling sequence M 3 3□ with an adaptive genetic algorithm.J Shandong Univ Eng Sci, 3352 2003.33(3):311 (路飞，田国会.用自适应遗传算法求解轧制顺序调度问题 M 354321 山东大学学报：工学版，2003,33(3)：311) 0 10 15 20 25 30 [4 Chen C W,Dong S H.Ding W E.Optimization of multi-stage 时间h ☐工件形测工件形圆工件用工件用， production planning in ERW pipe manufacturing.J Univ Sci ①1表示加工时间 Technol Bejing,2006.28(7):691 (陈超武，董绍华，丁文英.ERW钢管多阶段生产计划的编制 及优化.北京科技大学学报，2006,28(7)：691) 图3最大完成时间的Pareto解的甘特图 [5 Zhong H Y.Hu JZ.A heuristic algorithm for steel pipes pro Fig.3 Gantt of maximum completion time based on Pareto duction scheduing.Ind Eng Manage,2008(2):80 表3Pato最优解与SPT规则解的工件完工时间。 (钟海嫣.霍佳震.钢管冷区生产调度的一种启发式算法.工 业工程与管理.2008(2)：80) Table3 Work competion time co by Pareto and SPT mules [6 Cui J S,Li T K,Zhang W X.Hybrid fbw shop scheduling model 工件W Pareto最优解的C。 SPT规则的c。 and its genetic algorithm.J Univ Sci Technol Bjing.2005.27 W (5):623 29 27 (崔建双，李铁克，张文新.混合流水车间调度模型及其遗传 W2 26 26 算法.北京科技大学学报.2005,27(5)：623) W3 22 23 [7 Kumar P R.Re-entrant lines.Queuing Syst,1993.13(1/3): W 28 29 87 [8 Wang Y,Wu Z M,Sui Y.Scheduling re entrant manufacturing Pareto的遗传算法相比SPT规则的各工件完工时 lines of semiconductor based on GA.Comnput Simul,2007.24 间更符合合同交货期，交货期满意度指标更有优势. (12):247 (王永，吴智铭，隋义。基于遗传算法的可重入半导体生产线 由此可见，基于Pareto的混合遗传算法在钢管可重入 的调度.计算机仿真.2007.2412)：247) 生产的计划与调度优化问题上可行和合理，有较好的 9Reeves C R.A genetic algorithm for flow shop sequencing.Com- 优化性能，算法的求解速度快，结果具有可操作性. pu1 Oper Res,1995,22(1):5 [10 Chen CL Vempati V S.Aljaber N.An application of genetic 5结论 algorit hms for flow shop problems EurJ Oper Res,1995,80: 389 可重入生产系统不仅在冷拔无缝钢管生产，而 11]Deng K,Lin J,Wang F.Scheduling of re-entrant lne based on swarm intelligence//2008 Inter national Symposium on Knowl 且在机械加工、半导体生产等制造系统中广泛存在. edge Acquisition and Modeling.Wuhan.2008:323 本文研究可重入钢管生产的优化调度问题，把若干 12]Zhu X J.Pan D.Wang A L,et al.Multiobjective optimization 参数相同的工件组为一批，设定规则把组批的钢管 design with mixeddiscrete variables in mechanical engineering via Pareto genetic algorithm.J Shanghai Jicotong Univ,2000, 看作单个加工工件，以最后完工时间、交货期满意 343):411 度、机器总负荷建立多目标优化函数，并对每一目标 (朱学军，攀登，王安麟，等混合变量多目标优化设计的 建立数学模型，采用基于Pareto的混合遗传算法对 Pareto遗传算法实现.上海交通大学学报，2000,34(3)： 411) 模型进行优化求解.为适应可重入生产系统的要 13 Wu X L,Sun S D.Yu JJ,et al.Research on multi-obiective 求，遗传算法采用两层编码结构，并将关键路径网络 optimization for flexible job shop scheduling.Comput Integr 图应用到染色体的编码及解码中，选择策略集成了 Manuf Sys1,2006.12(5):731 (吴秀丽，孙树栋，余建军，等。多目标柔性作业车间调度优 精英保留策略和小生境技术，从而保证了解的多样 化研究.计算机集成制造系统.2006.12(5)：731) 性.应用算例的结果表明，相比SPT优化规则，基于 14 Gu F,Chen H P,Lu B Y.The soution for multi-objective flex- Pareto的遗传算法对优化调度有更好的优化性能. ibk job shop scheduling based on genet ic algorithm.Oper Res Manage Sci,2006.15(1):B4 参考文献 (古蜂，陈华平，卢冰原.基于遗传算法的多目标柔性工作车 间调度问题求解.运筹与管理，2006.15(1)：134 [1]Tang LX.Zhang G F,Yang Z H,et al.Research on hot rolling 15]Yu Q W.Zhao L Pan S X.A scheduling optimization of flexi- scheduling for tube production.Iron Steel,1999.34(4):73. bl jolrshop using genetic algrithm.Modular Mach Tool Au- (唐立新，张国范，杨自厚，等.热轧钢管轧批排序模型及算 tom Manuf Tech,2004(4):32 法.钢铁，1999.344)：73) (余琦玮，赵亮，潘双夏.基于遗传算法的柔性作业车间调度 [2 Li H.Huo Z J.A heuristic akorithm for seamless stee tube or- 优化.组合机床与自动化加工技术，2004(4)：32)

图 3 最大完成时间的Pareto 解的甘特图 Fig.3 Gantt of maximum completion time based on Paret o 表 3 Pareto 最优解与S PT 规则解的工件完工时间 co Tabl e 3 Work completion time co by Paret o and S PT rules 工件 W Pareto 最优解的 co SPT 规则的 co W1 29 27 W2 26 26 W3 22 23 W4 28 29 Pareto 的遗传算法相比 SPT 规则的各工件完工时 间更符合合同交货期, 交货期满意度指标更有优势 . 由此可见, 基于 Pareto 的混合遗传算法在钢管可重入 生产的计划与调度优化问题上可行和合理, 有较好的 优化性能, 算法的求解速度快, 结果具有可操作性. 5 结论 可重入生产系统不仅在冷拔无缝钢管生产, 而 且在机械加工、半导体生产等制造系统中广泛存在 . 本文研究可重入钢管生产的优化调度问题, 把若干 参数相同的工件组为一批, 设定规则把组批的钢管 看作单个加工工件, 以最后完工时间 、交货期满意 度、机器总负荷建立多目标优化函数, 并对每一目标 建立数学模型, 采用基于 Pareto 的混合遗传算法对 模型进行优化求解.为适应可重入生产系统的要 求, 遗传算法采用两层编码结构, 并将关键路径网络 图应用到染色体的编码及解码中, 选择策略集成了 精英保留策略和小生境技术, 从而保证了解的多样 性.应用算例的结果表明, 相比 SPT 优化规则, 基于 Pareto 的遗传算法对优化调度有更好的优化性能 . 参 考 文 献 [ 1] Tang L X, Zhang G F, Yang Z H, et al.Research on hot rolling scheduling for tube production.Iron S teel, 1999, 34( 4) :73. ( 唐立新, 张国范, 杨自厚, 等.热轧钢管轧批排序模型及算 法.钢铁, 1999, 34( 4) :73) [ 2] Li H, Huo Z J.A heuristic algorithm f or seamless steel tube or￾der-grouping problem .Ind Eng Manage, 2004( 1) :86 ( 李虎, 霍佳震.钢管生产的合同组批优化算法.工业工程与 管理, 2004( 1) :86) [ 3] Lu F, Tian G H .Solving scheduling problems of rolling sequence w ith an adaptive geneti c algorithm .J Shandong Uni v Eng Sci, 2003, 33 ( 3) :311 ( 路飞, 田国会.用自适应遗传算法求解轧制顺序调度问题. 山东大学学报:工学版, 2003, 33 ( 3) :311) [ 4] Chen C W, Dong S H, Ding W E .Optimization of multi-stage production planning in ERW pipe manuf acturing .J Uni v Sci Technol Bejing , 2006, 28( 7) :691 ( 陈超武, 董绍华,丁文英.ERW 钢管多阶段生产计划的编制 及优化.北京科技大学学报, 2006, 28( 7) :691) [ 5] Zhong H Y, Huo J Z .A heu ristic algorithm for st eel pipes pro￾duction scheduling .Ind Eng Manage, 2008( 2) :80 ( 钟海嫣, 霍佳震.钢管冷区生产调度的一种启发式算法.工 业工程与管理.2008( 2) :80) [ 6] Cui J S, Li T K, Zhang W X.Hybrid flow shop scheduling model and its genetic algorithm .J Uni v S ci Technol Bejing , 2005, 27 ( 5) :623 ( 崔建双, 李铁克, 张文新.混合流水车间调度模型及其遗传 算法.北京科技大学学报, 2005, 27( 5) :623) [ 7] Kumar P R.Re-entrant lines.Queuing Syst , 1993, 13( 1/ 3 ) : 87 [ 8] Wang Y, Wu Z M , Sui Y .Scheduling re-entrant manuf acturing lines of semiconduct or based on GA.Com put Simu l, 2007, 24 ( 12) :247 ( 王永, 吴智铭, 隋义.基于遗传算法的可重入半导体生产线 的调度.计算机仿真, 2007, 24( 12) :247) [ 9] Reeves C R.A geneti c algorithm f or flow shop sequencing .Com￾pu t Oper Res, 1995, 22( 1) :5 [ 10] Chen C L, Vempati V S , Aljaber N.An application of genetic algorithms f or flow shop problem s.Eur J Oper Res, 1995, 80: 389 [ 11] Deng K, Lin J, Wang F .Scheduling of re-entrant line based on swarm int elligence ∥2008 Inter national Sym posium on Knowl￾edge Acquisition and Modeling.Wuhan, 2008:323 [ 12] Zhu X J, Pan D, Wang A L, et al.Multiobjective optimization design w ith mixed-discret e variables in mechanical engineering via Pareto genetic algorithm .J S hanghai Jiaotong Uni v, 2000, 34( 3) :411 (朱学军, 攀登, 王安麟, 等.混合变量多目标优化设计的 Paret o 遗传算法实现.上海交通大学学报, 2000, 34( 3 ) : 411) [ 13] Wu X L, S un S D, Yu J J, et al.Research on multi-objecti ve optimization for flexible job shop scheduling .Comput Int egr Manu f S yst, 2006, 12( 5) :731 ( 吴秀丽, 孙树栋, 余建军, 等.多目标柔性作业车间调度优 化研究.计算机集成制造系统.2006, 12( 5) :731) [ 14] Gu F, Chen H P, Lu B Y .The solution for multi-objecti ve flex￾ible job shop scheduling based on genetic algorithm .Oper Res Manage S ci, 2006, 15( 1) :134 ( 古峰, 陈华平, 卢冰原.基于遗传算法的多目标柔性工作车 间调度问题求解.运筹与管理, 2006, 15( 1) :134) [ 15] Yu Q W, Zhao L, Pan S X.A scheduling optimization of flexi￾ble job-shop using genetic algorithm .Modu lar Mach Tool Au￾tom Manu f Tech , 2004(4) :32 ( 余琦玮, 赵亮, 潘双夏.基于遗传算法的柔性作业车间调度 优化.组合机床与自动化加工技术, 2004( 4) :32) 第 8 期 陈晓慧等:基于遗传算法的可重入钢管生产优化调度 · 1071 ·