ERW钢管多阶段生产计划的编制及优化

D01:10.13374j.isml00103x2006.07.018 第28卷第7期 北京科技大学学报 Vol.28 Na 7 2006年7月 Journal of University of Science and Technology Beijing Jul.2006 ERW钢管多阶段生产计划的编制及优化 陈超武董绍华 文英 北京科技大学机械工程学院，北京100083 摘要生产计划是企业生产管理的起点和依据.本文分析了高频电阻焊钢管的生产流程和生产 计划的特点，提出了钢管企业多阶段生产计划提前/拖期惩罚模型，并用实数编码遗传算法进行了 求解及优化，得到生产计划的较优解.仿真结果表明.模型和算法是可行和高效的.求解方法在钢 管实际生产计划编制中得到了良好的应用 关键词ERW钢管；多阶段生产：生产计划：遗传算法 分类号F406.2 多阶段生产计划问题大量存在于现代制造系 度的综合模型，该模型包括生产计划模型和车间 统中1②，该问题详细地描述了产品从原材料到 调度模型.李秀等8研究了制造能力约束下的车 产成品的生产过程中各阶段的生产安排，各生产 间批量生产计划提前/拖期问题，并用遗传算法求 阶段间呈现顺序加工关系，且前后阶段紧密衔接 解但没有考虑生产中的库存问题. 存在着物质和能量的转换与传递到.制造企业生 针对上述研究现状本文研究了高频电阻焊 产计划的制定一般均是采取自上而下的顶层控制 (ERM钢管生产流程，建立了钢管多阶段生产计 法.Britran和Tirupatic等经研究后指出49，现 划模型，并采遗传算法进行求解，实现了ERW钢 有的MRP和MRPⅡ系统都是依据最终产品，零 管生产计划的快速有效编制及优化. 配件的订单要求，制定出任务计划和交货期限，并 1 ERW钢管生产计划问题 生成整个生产计划.但它们都没有考虑具体的生 产车间的生产能力制约，因此制定出来的生产计 直缝焊管采用ERW新型生产工艺制作而成 划就没有合理性和可操作性的保证.徐和平等) 的钢管产品，生产工艺流程如图1. 建立了一个多阶段生产制造系统的生产计划与调 纵剪 板带库 成型 成 库1 水 质量 检验 成品库 图1ERW钢管生产工艺流程 Fig 1 Flow chart of ERW pipe production 某钢管企业传统的计划工作完全通过人工方 的一次订货量至少十几吨，每个月的合同数以百 式进行，尽管生产计划的编制有一套较完整的编 计. 制规则，从总体到局部计划员都力求达到最佳效 (2)生产具有流水车间的特点，纵剪、成型、 果，但由于计划过程中存在着大量的人工协调和 水压、质量检验为流水作业等生产阶段.生产阶 资源平衡，计算工作量较大有限的人力使得协调 段间存在着顺次关系，前一阶段必须及时为后一 和平衡的准确性及效果不佳.该企业生产包括以 阶段提供原料，以保证整个生产过程的顺畅 下特点： (3)就整个生产过程来看，成型阶段是生产 (1)品种多，批量小.当前该钢管企业的产 的瓶颈.如何安排多个生产阶段使其工作能力均 品目录上有几千种不同的产品，客户对某种产品 能充分发挥是影响产能的一个关键 收稿日期：2005-04-12修回日期：20060302 2ERW钢管生产计划模型 作者简介：陈超武(1977一人，男.博士研究生：董绍华(1960一人， 男.教授.博士生导师 交货期窗口下提前/拖期生产计划问题随着

ERW 钢管多阶段生产计划的编制及优化 陈超武 董绍华 丁文英 北京科技大学机械工程学院, 北京 100083 摘 要 生产计划是企业生产管理的起点和依据.本文分析了高频电阻焊钢管的生产流程和生产 计划的特点, 提出了钢管企业多阶段生产计划提前/ 拖期惩罚模型, 并用实数编码遗传算法进行了 求解及优化, 得到生产计划的较优解.仿真结果表明, 模型和算法是可行和高效的.求解方法在钢 管实际生产计划编制中得到了良好的应用. 关键词 ERW 钢管;多阶段生产;生产计划;遗传算法 分类号 F406.2 多阶段生产计划问题大量存在于现代制造系 统中[ 1 2] , 该问题详细地描述了产品从原材料到 产成品的生产过程中各阶段的生产安排 .各生产 阶段间呈现顺序加工关系, 且前后阶段紧密衔接, 存在着物质和能量的转换与传递[ 3] .制造企业生 产计划的制定一般均是采取自上而下的顶层控制 法.Britran 和 Tirupatic 等经研究后指出 [ 4 6] , 现 有的 M RP 和 M RP Ⅱ系统都是依据最终产品、零 配件的订单要求, 制定出任务计划和交货期限, 并 生成整个生产计划.但它们都没有考虑具体的生 产车间的生产能力制约, 因此制定出来的生产计 划就没有合理性和可操作性的保证.徐和平等[ 7] 建立了一个多阶段生产制造系统的生产计划与调 度的综合模型, 该模型包括生产计划模型和车间 调度模型 .李秀等[ 8] 研究了制造能力约束下的车 间批量生产计划提前/拖期问题, 并用遗传算法求 解, 但没有考虑生产中的库存问题 . 针对上述研究现状, 本文研究了高频电阻焊 ( ERW) 钢管生产流程, 建立了钢管多阶段生产计 划模型, 并采遗传算法进行求解, 实现了 ERW 钢 管生产计划的快速有效编制及优化 . 1 ERW 钢管生产计划问题 直缝焊管采用 ERW 新型生产工艺制作而成 的钢管产品, 生产工艺流程如图 1 . 图1 ERW钢管生产工艺流程 Fig.1 Flow chart of ERW pipe production 收稿日期:2005 04 12 修回日期:2006 03 02 作者简介:陈超武( 1977—) , 男, 博士研究生;董绍华( 1960—) , 男, 教授, 博士生导师 某钢管企业传统的计划工作完全通过人工方 式进行, 尽管生产计划的编制有一套较完整的编 制规则, 从总体到局部, 计划员都力求达到最佳效 果, 但由于计划过程中存在着大量的人工协调和 资源平衡, 计算工作量较大, 有限的人力使得协调 和平衡的准确性及效果不佳.该企业生产包括以 下特点: ( 1) 品种多, 批量小 .当前该钢管企业的产 品目录上有几千种不同的产品, 客户对某种产品 的一次订货量至少十几吨, 每个月的合同数以百 计. (2) 生产具有流水车间的特点, 纵剪、成型、 水压 、质量检验为流水作业等生产阶段.生产阶 段间存在着顺次关系, 前一阶段必须及时为后一 阶段提供原料, 以保证整个生产过程的顺畅 . (3) 就整个生产过程来看, 成型阶段是生产 的瓶颈.如何安排多个生产阶段使其工作能力均 能充分发挥是影响产能的一个关键 . 2 ERW 钢管生产计划模型 交货期窗口下提前/拖期生产计划问题随着 第 28 卷 第 7 期 2006 年 7 月 北 京 科 技 大 学 学 报 Journal of University of Science and Technology Beijing Vol .28 No.7 Jul.2006 DOI :10.13374/j .issn1001 -053x.2006.07.018

。692 北京科技大学学报 2006年第7期 JT思想的发展，企业管理者越来越注重如何制 由提前/拖期生产计划模型中，目标函数为： 定考虑到提前/拖期费用的生产计划习. 式(4)为提前和拖期惩罚总费用最小.约束条件 Chengl1g首次把交货期窗口的概念应用到提前/ 包括：式(5)表示每一阶段生产能力的约束：式(6) 拖期问题中，认为要想避免惩罚，任务完工时间必 表示计划期内生产与需求的平衡：式(7)为非负约 须落在交货期窗口内，只要不在交货期窗口内，就 束 会引起提前/拖期惩罚.在求解方法中，经典优化 可以看出，约束(5)的个数是J·T,当阶段数 技术对问题模型进行简化，以求得最优解1】.针 J较大时，问题的规模对于一般求解方法将显得 对钢管生产的特点，考虑的是在给定的外部需求 过大，而此问题又是一个典型的求解优化问题. 和带有生产能力约束的前提下，以提前/拖期的惩 在优化求解的算法中，分为经典优化技术与启发 罚最小为目标编制最优的多阶段生产计划 式优化方法，本研究采用遗传算法来求解. 设钢管企业A在计划期L,T]内要生产I 种产品，每种产品要经过J个生产阶段加工，决 3算法设计 策为产品i第1日的计划生产量为x:(t).根据客 3.1遗传编码 户的订货合同汇总，可得到产品i第t日的合同 遗传求解大多数问题可采用基因呈一维排列 交货量为F:(t).己知单位产品i对阶段j的能 的染色体的表现形式，尤其是基于{0,1}编码的二 力需求量为c,阶段j第t日的可用能力为 值编码形式.但在基于无限资源的规划问题中， C(t).初始时刻，产品i的库存量为1i,10表 设计任务或设计变量所组成的串如果用二进制字 示初始的欠产量，初始时刻为1=0. 串表示，不但使串长加长，而且使得规律无从可 设单位产品i单位时间提前的附加成本为 循也不利于与目标函数相对应？.实数编码方 ,单位时间拖期的罚款为B,一般有>.假 法为，个体的每个基因值用某一范围内的一个实 设企业为连续生产，各阶段中间不产生库存.由 数来表示，个体的编码长度等于其决策变量的个 企业生产情况可以得出，产品i的提前惩罚费用 数.这是遗传算法中在解决连续参数优化问题时 为 普遍使用的一种编码方式，具有较高的精度，在表 o=4m+-刻] 示连续渐变问题方面具有优势，实数编码方法在 高维度问题中得到很好的应用.因此，本研究对 (1) 多阶段生产计划问题采用实数编码方案，优化问 产品i的拖期惩罚费用为： 题则转化为对编码的实数取值问题，编码使用的 =mar- 是决策变量的真实值，遗传算法的选择、交叉以及 变异操作直接在表现型上进行， 设(t)为产品在时刻加工量(i=1,2 由式(1)和(2)，附加的惩罚费用总额为： ;1=1,2,；T),则生产计划的编码矩阵为： f(x)=f(a)+f(β) (3) x1(1)x2(1) …x1) 由此，提前/拖期生产计划的模型如下： x1(t)x2(2) x(2) minf(x) (8) x1(T)x2(t) …x(T小 进而，基于该矩阵可以构造遗传算法的染色体为： maaF-x(-] P=(x1(1),x21),x1(1);x1(2,x22),; 4) x(2);;x1(T),x2(T),;x(T)）(9) 3.2种群初始化 s.t. ∑9)≤9(.j=121=12T 由于多阶段生产计划问题涉及问题的分解与 (5) 规划，群体规模对遗传算法的结果有很大影响，为 空+1=F=121 保证群体的多样性，防止算法收敛于局部最优解， (6) 群体规模应该大于20个.由于初始种群随机产 x(t≥0，i=1,2,1,t=L,2,；T(7) 生，满足等式约束较麻烦，所以在算法一开始，就

JIT 思想的发展, 企业管理者越来越注重如何制 定考 虑 到 提 前/拖 期 费 用 的 生 产 计 划[ 9] . Cheng [ 10] 首次把交货期窗口的概念应用到提前/ 拖期问题中, 认为要想避免惩罚, 任务完工时间必 须落在交货期窗口内, 只要不在交货期窗口内, 就 会引起提前/拖期惩罚.在求解方法中, 经典优化 技术对问题模型进行简化, 以求得最优解[ 11] .针 对钢管生产的特点, 考虑的是在给定的外部需求 和带有生产能力约束的前提下, 以提前/拖期的惩 罚最小为目标, 编制最优的多阶段生产计划. 设钢管企业 A 在计划期[ 1, T] 内要生产 I 种产品, 每种产品要经过 J 个生产阶段加工, 决 策为产品 i 第t 日的计划生产量为 xi( t) .根据客 户的订货合同汇总, 可得到产品 i 第 t 日的合同 交货量为Fi ( t) .已知单位产品 i 对阶段 j 的能 力需求量为 cij , 阶段 j 第 t 日的可用能力为 Cj( t) .初始时刻, 产品 i 的库存量为Ii , Ii <0 表 示初始的欠产量, 初始时刻为 t =0 . 设单位产品 i 单位时间提前的附加成本为 αi , 单位时间拖期的罚款为 βi , 一般有 βi >αi .假 设企业为连续生产, 各阶段中间不产生库存 .由 企业生产情况可以得出, 产品 i 的提前惩罚费用 为: f( α) =αimax 0, Ii + ∑ t k =1 xi( k ) - ∑ t k =1 Fi( k) ( 1) 产品 i 的拖期惩罚费用为 : f( β) =βimax 0, ∑ t k =1 Fi( k ) - ∑ t k =1 xi( k) -Ii ( 2) 由式( 1)和( 2), 附加的惩罚费用总额为 : f ( x ) =f ( α) +f ( β) ( 3) 由此, 提前/拖期生产计划的模型如下: min f ( x ) = ∑ I i =1 ∑ T t =1 αimax 0, Ii + ∑ t k =1 xi( k ) - ∑ t k =1 Fi( k ) + βimax 0, ∑ t k =1 Fi( k ) - ∑ t k =1 xi( k ) -Ii ( 4) s .t . ∑ I i =1 cijx i( t ) ≤Cj( t), j =1, 2, …, J , t =1, 2, …, T ( 5) ∑ T t =1 xi( t) +Ii = ∑ T t =1 Fi( t ), i =1, 2, …, I ( 6) xi( t) ≥0, i =1, 2, …, I, t =1, 2, …, T ( 7) 由提前/拖期生产计划模型中, 目标函数为: 式( 4) 为提前和拖期惩罚总费用最小.约束条件 包括 :式( 5)表示每一阶段生产能力的约束;式( 6) 表示计划期内生产与需求的平衡;式( 7)为非负约 束. 可以看出, 约束( 5)的个数是 J·T, 当阶段数 J 较大时, 问题的规模对于一般求解方法将显得 过大, 而此问题又是一个典型的求解优化问题. 在优化求解的算法中, 分为经典优化技术与启发 式优化方法, 本研究采用遗传算法来求解. 3 算法设计 3.1 遗传编码 遗传求解大多数问题可采用基因呈一维排列 的染色体的表现形式, 尤其是基于{0, 1}编码的二 值编码形式.但在基于无限资源的规划问题中, 设计任务或设计变量所组成的串如果用二进制字 串表示, 不但使串长加长, 而且使得规律无从可 循, 也不利于与目标函数相对应 [ 12] .实数编码方 法为, 个体的每个基因值用某一范围内的一个实 数来表示, 个体的编码长度等于其决策变量的个 数.这是遗传算法中在解决连续参数优化问题时 普遍使用的一种编码方式, 具有较高的精度, 在表 示连续渐变问题方面具有优势, 实数编码方法在 高维度问题中得到很好的应用.因此, 本研究对 多阶段生产计划问题采用实数编码方案, 优化问 题则转化为对编码的实数取值问题, 编码使用的 是决策变量的真实值, 遗传算法的选择 、交叉以及 变异操作直接在表现型上进行 . 设 xi( t) 为产品在时刻加工量( i =1, 2, …, I ;t =1, 2, …, T) , 则生产计划的编码矩阵为: x 1( 1) x2( 1) … x I( 1) x 1( t) x2( 2) … x I( 2)     x 1( T) x2( t) … x I ( T ) ( 8) 进而, 基于该矩阵可以构造遗传算法的染色体为: P =( x1( 1), x 2( 1), …, x 1( 1) ;x 1( 2), x 2( 2), …, xI ( 2) ;…;x 1( T), x 2( T) , …, x I( T) ) ( 9) 3.2 种群初始化 由于多阶段生产计划问题涉及问题的分解与 规划, 群体规模对遗传算法的结果有很大影响, 为 保证群体的多样性, 防止算法收敛于局部最优解, 群体规模应该大于 20 个.由于初始种群随机产 生, 满足等式约束较麻烦, 所以在算法一开始, 就 · 692 · 北 京 科 技 大 学 学 报 2006 年第 7 期

Vol.28 No.7 陈超武等：ERW钢管多阶段生产计划的编制及优化 ·693。 要采取措施使它们和相等数量的问题变量一起被 (2)交叉.根据个体的交叉概率p%在上一 消去，这样做就减少了一部分搜索空间，留下的线 代群体中选择数对个体进行交叉操作，这样就有 性不等式的约束就构成了搜寻解时必须进行搜索 Np。个个体参与交叉.采用多点复合交叉操作， 的凸集.搜索空间的凸性确保了解的线性组合无 如表1，首先根据交叉概率确定种群中个体是否 需检验约束就产生新的解，从而在全局角度减少 参与交叉，然后选择单个或多个决策变量作为交 了进化中搜索的范围，避免发散的搜索域带来的 叉点，实施基于决策变量的实数交叉运算，最后将 “进化停滞”问题. 各执行实数交叉运算的决策变量实行交换操作， 通过对生产能力和各品种需求量的分析，将 能保证决策变量的可行性， 需求量分解成若干天生产的组合，依次形成计划 表1复合交叉的过程 期的生产任务：通过不同时间任务的排列，产生初 Table 1 Process of complex crossover 始种群Po,种群规模为N.如Po的一个个体为： 个体 2 P0=(186,0,0,0,0:53,0,0,0,0:0,379, 父代 P=(pp…,pP=(pp3…,p) 0,0,0:0,0,0,0,494:0,0,0,0,359)(10) 子代 C=(c,c…,cC=(c,c2…,c) 3.3适应度函数 由于遗传算法中适应度函数要比较排序并在 复合交叉过程采用算术交叉的方法，算术交 此基础上计算选择概率，所以适应度函数的值要 叉产生子代个体C1,C2的方式为 取正值.因此需要将目标函数映射成求最大值 c=p+(1-)pi,c=p+(1-)pi, 形式且函数值非负的适应度函数，转换方法为： 入∈0，刂 (14 Cmam一f(x,f升xKCmax f(p)= (11) 式中，p为父代个体1基因，p为父代个体2基 0, 否则 因，c}为子代个体1基因，c为子代个体2基因. 式中，f(x)为最小化的目标函数，Cma是一个足 为了保证最优基因不被破坏，受小生境遗传 够大的正整数. 算法的启发，对上述交叉算子进行改进.如果交 3.4约束条件处理 叉得到的新个体C1或C2不差于原来的个体P1 处理遗传算法采用罚函数法将约束优化问题 或P2,则替换原来的P1或P2,否则保留原来的 转化为考虑代价或惩罚的非约束优化问题.本研 个体. 究中，约束条件包括不等式约束和等式约束两部 (3)变异.根据个体的变异概率pm,在上一 分，通过惩罚方法可转化为以下非约束极大值问 代群体中随机选择NPm个个体进行变异操作，在 题其中r为惩罚系数本文中r为负值 父代个体P=(p,p2,pi,;pn,对其变异 fpj=rp+m0空s小G) 元素p,生成随机数r∈[0，]，产生变异个体 P'=(p1,p2,pi,,pm)的过程为： rmax 0空)+-空F pi十u(a-p),r=0 p (15) (12) pi一upi, r=1 3.5遗传操作 式中，a为P:的上限，随机数u∈[0，]，变异操 遗传算法遗传操作包括三个基本遗传算子： 作能保证决策变量的可行性 选择、交叉和变异.这三个遗传算子的操作都是 3.6终止条件 在随机扰动情况下进行的， 采用规定最大迭代次数为终止条件，即迭代 (1)选择操作.本研究采用比例选择的方 次数达到规定的迭代次数Gr时停止计算. 法用正比于个体适应度的概率来选择相应的个 遗传算法的流程如下： 体选择概率为： 迭代开始：t=0: 种群初始化：P(0) (13) 适应性评价：Fitness(P(O): 同时为保证算法的收敛性，采用了最优保存 While(迭代次数长Gmax)do 策略(elitist strategy),即把第n十I代种群的适应 选择：P'(t)=select(P(t),ps: 度值最差个体用上代最优个体替代. 交叉：P"(t)=crossover(P(t),pe;

要采取措施使它们和相等数量的问题变量一起被 消去, 这样做就减少了一部分搜索空间, 留下的线 性不等式的约束就构成了搜寻解时必须进行搜索 的凸集.搜索空间的凸性确保了解的线性组合无 需检验约束就产生新的解, 从而在全局角度减少 了进化中搜索的范围, 避免发散的搜索域带来的 “进化停滞”问题 . 通过对生产能力和各品种需求量的分析, 将 需求量分解成若干天生产的组合, 依次形成计划 期的生产任务;通过不同时间任务的排列, 产生初 始种群 P 0, 种群规模为 N .如 P0 的一个个体为: P 1 0 =( 186, 0, 0, 0, 0 ;53, 0, 0, 0, 0 ;0, 379, 0, 0, 0 ;…;0, 0, 0, 0, 494 ;0, 0, 0, 0, 359) ( 10) 3.3 适应度函数 由于遗传算法中适应度函数要比较排序并在 此基础上计算选择概率, 所以适应度函数的值要 取正值.因此, 需要将目标函数映射成求最大值 形式且函数值非负的适应度函数, 转换方法为 : f ( p) = Cmax -f ( x ), f( x ) <Cmax 0, 否则 ( 11) 式中, f ( x ) 为最小化的目标函数, C max是一个足 够大的正整数. 3.4 约束条件处理 处理遗传算法采用罚函数法将约束优化问题 转化为考虑代价或惩罚的非约束优化问题.本研 究中, 约束条件包括不等式约束和等式约束两部 分, 通过惩罚方法可转化为以下非约束极大值问 题, 其中 r 为惩罚系数, 本文中 r 为负值 . f′( p) =f( p) +rmax 0, ∑ I i =1 cijxi( t) -Cj( t) + rmax 0, ∑ T t =1 xi( t ) +Ii - ∑ T t =1 Fi( t) 2 ( 12) 3.5 遗传操作 遗传算法遗传操作包括三个基本遗传算子: 选择 、交叉和变异.这三个遗传算子的操作都是 在随机扰动情况下进行的 . (1) 选择操作.本研究采用比例选择的方 法, 用正比于个体适应度的概率来选择相应的个 体, 选择概率为 : pi =fi ∑ I i =1 fi ( 13) 同时为保证算法的收敛性, 采用了最优保存 策略( elitist strategy ) , 即把第 n +1 代种群的适应 度值最差个体用上代最优个体替代 . (2) 交叉.根据个体的交叉概率 pc, 在上一 代群体中选择数对个体进行交叉操作, 这样就有 Npc 个个体参与交叉 .采用多点复合交叉操作, 如表 1, 首先根据交叉概率确定种群中个体是否 参与交叉, 然后选择单个或多个决策变量作为交 叉点, 实施基于决策变量的实数交叉运算, 最后将 各执行实数交叉运算的决策变量实行交换操作, 能保证决策变量的可行性 . 表 1 复合交叉的过程 Table 1 Process of complex crossover 个体 1 2 父代 P1 =( p 1 1 , p 1 2 , …, p 1 n ) P 2 =( p 2 1 , p 2 2 , …, p 2 n ) 子代 C1 =( c 1 1 , c 1 2 , …, c 1 n ) C2 =( c 2 1 , c 2 2 , …, c 2 n ) 复合交叉过程采用算术交叉的方法, 算术交 叉产生子代个体 C1, C2 的方式为 c 1 i =λp 1 i +( 1 -λ) p 2 i , c 2 i =λp 2 i +( 1 -λ) p 1 i , λ∈[ 0, 1] ( 14) 式中, p 1 i 为父代个体 1 基因, p 2 i 为父代个体 2 基 因, c 1 i 为子代个体 1 基因, c 2 i 为子代个体 2 基因 . 为了保证最优基因不被破坏, 受小生境遗传 算法的启发, 对上述交叉算子进行改进.如果交 叉得到的新个体 C1 或 C2 不差于原来的个体 P 1 或 P 2, 则替换原来的 P 1 或 P 2, 否则保留原来的 个体 . ( 3) 变异 .根据个体的变异概率 pm, 在上一 代群体中随机选择 Npm 个个体进行变异操作, 在 父代个体 P =( p1, p2, …, pi , …, pn ), 对其变异 元素 pi , 生成随机数 r ∈ [ 0, 1] , 产生变异个体 P′=( p1, p2, …, p′i , …, pn) 的过程为 : p′= pi +u ( a -pi) , r =0 pi -upi , r =1 ( 15) 式中, a 为 pi 的上限, 随机数 u ∈ [ 0, 1] , 变异操 作能保证决策变量的可行性. 3.6 终止条件 采用规定最大迭代次数为终止条件, 即迭代 次数达到规定的迭代次数 Gmax时停止计算. 遗传算法的流程如下 : 迭代开始 :t =0 ; 种群初始化:P( 0) ; 适应性评价:Fitness( P ( 0) ) ; While (迭代次数 t <Gmax ) do 选择:P′( t) =select( P ( t) , ps) ; 交叉:P″( t) =crossover( P′( t) , pc) ; Vol.28 No.7 陈超武等:ERW 钢管多阶段生产计划的编制及优化 · 693 ·

。694 北京科技大学学报 2006年第7期 变异：p"(t)=mutation(P"(t),pm; 表4单位产品i对阶段/的能力需求量c, 新种群：P(t十1： Table 4 Capacity requirement of product i in stage/ 适应性评价：Fitness(P(t+l); a (min't) End do =1 j=2 =3 =4 1 2699 3385 3067 3366 4计算实例和仿真结果 2 1321 1.660 1.501 1.645 41计算参数 3 1.018 1.285 1.291 1.457 设种群规模N为40，交叉概率p=075,变 4 1.105 1.189 1.127 1.379 异概率pm=0.05,迭代次数Gma=200,产品数I 1.051 L.081 1.094 L185 =5,阶段数J=4,计划期T=15d,惩罚系数c: =0.00L,3=00L,生产数据见表2~表4. 42算法分析 计算结果如图2.遗传110代以后，最大适应 表2客户合同需求量F() 度趋于平缓计算结果接近最优值.最大适应度 Table 2 Requirement of producti in time 值出现在第160代为950.197，最优解如表5. F(1)/t 4d 8d 12d 15d 1000 最大 0 0 186 53 900 适度 2 508 0 1702 0 800 平均 3 128 0 0 0 话度 700 4 0 675 0 0 5 841 1000 0 0 表3阶段能力限制G(1) 100 150 200 Table 3 Capacity constraint of stagej 选代次数 1 2 3 图2计算结果 C(t)/(min'd-)520 630 580670 Fig.2 Computing result 表5生产计划方案 Table 5 Optimized production planning t Id 2d 3d 4d 5d 6d 7d 8d 9d 10d11d12d 13d14d15d 0 53 0 0 0 0 0 0 14 0 0 0 77 6 0 0 0 379 0 0 379 209 189 3 331 0 3 243 283 3 0 0 0 0 71 0 0 0 0 6 0 5 0 0 190 0 0 0 0 0 0 155 106 10 174 0 85 0 5 0 0 332 0 494 231 312 67 35 288 38 185 308 46 29 结论 产品交货期的目的. 5 将提前/拖后惩罚问题扩展到了带有能力约 参考文献 束的ERW钢管多阶段生产计划中，建立了多阶 [1]Syarif A.Yun Y S.Gen M.Study on multi-stag:logistic 段制造系统的生产计划模型，采用遗传算法进行 chain metwork:a spanning tree-based genetic algorithm ap proach.Comput Ind Eng.2002,43:299 了求解.考虑到实际问题的差异，构造了惩罚函 [2]Hoquea M A,Goyallnt S K.On bt streaming in multistage 数，提高了算法求解效率，计算结果验证了模型和 production ystems.J Prod Econ,2005.95:195 算法的有效性.算法提高了企业生产计划编制的 【3到郑秉霖，胡琨元，常春光。一体化钢铁生产计划系统的研究 可行性和编制效率，减少了生产计划人员和工艺 现状与展望.控制工程，2003.10(1)：6 设计人员的工作量，达到了降低制造成本和保证 [4 Huang HJ.Xu G.Aggregate scheduling and network solving of multistage and multi-item manfacture system.Eur JOper

变异:P ( t) =mutatio n( P″( t) , pm) ; 新种群:P ( t +1) ; 适应性评价 :Fitness( P ( t +1)) ; End do 4 计算实例和仿真结果 4.1 计算参数 设种群规模 N 为 40, 交叉概率 p c =0.75, 变 异概率 pm =0.05, 迭代次数 Gmax =200, 产品数 I =5, 阶段数 J =4, 计划期 T =15 d, 惩罚系数 αi =0.001, βi =0.01, 生产数据见表 2 ～ 表 4 . 表 2 客户合同需求量 Fi( t) Table 2 Requirement of product i in time t i Fi( t)/ t 4 d 8 d 12 d 15 d 1 0 0 186 53 2 508 0 1 702 0 3 128 0 0 0 4 0 675 0 0 5 841 1 000 0 0 表 3 阶段能力限制 Cj( t) Table 3 Capacity constraint of stage j j 1 2 3 4 Cj( t)/ ( min·d -1 ) 520 630 580 670 表 4 单位产品 i 对阶段j 的能力需求量cij Table 4 Capacity requirement of product i in stage j i cij/ ( min·t -1 ) j =1 j =2 j =3 j =4 1 2.699 3.385 3.067 3.366 2 1.321 1.660 1.501 1.645 3 1.018 1.285 1.291 1.457 4 1.105 1.189 1.127 1.379 5 1.051 1.081 1.094 1.185 4.2 算法分析 计算结果如图 2 .遗传 110 代以后, 最大适应 度趋于平缓, 计算结果接近最优值.最大适应度 值出现在第 160 代, 为 950.197, 最优解如表 5 . 图 2 计算结果 Fig.2 Computing result 表 5 生产计划方案 Table 5 Optimized production planning t i 1 d 2 d 3 d 4 d 5 d 6 d 7 d 8 d 9 d 10 d 11 d 12 d 13 d 14 d 15 d 1 0 53 0 0 0 0 0 0 14 0 0 0 0 77 6 2 0 0 0 379 0 0 379 209 189 3 331 0 3 243 283 3 0 0 0 0 0 71 0 0 0 0 6 0 5 0 0 4 190 0 0 0 0 0 0 155 106 10 5 174 0 85 0 5 0 0 332 0 494 231 312 67 35 288 38 185 308 46 29 5 结论 将提前/拖后惩罚问题扩展到了带有能力约 束的 ERW 钢管多阶段生产计划中, 建立了多阶 段制造系统的生产计划模型, 采用遗传算法进行 了求解.考虑到实际问题的差异, 构造了惩罚函 数, 提高了算法求解效率, 计算结果验证了模型和 算法的有效性.算法提高了企业生产计划编制的 可行性和编制效率, 减少了生产计划人员和工艺 设计人员的工作量, 达到了降低制造成本和保证 产品交货期的目的. 参 考 文 献 [ 1] Syarif A, Yun Y S , Gen M .Study on multi-stage logistic chain netw ork:a spanning tree-based genetic algorithm ap￾proach.Comput Ind Eng, 2002, 43:299 [ 2] Hoquea M A, GoyalInt S K.On lot streaming in multistage production syst ems.J Prod Econ, 2005, 95:195 [ 3] 郑秉霖, 胡琨元, 常春光.一体化钢铁生产计划系统的研究 现状与展望.控制工程, 2003, 10( 1) :6 [ 4] Huang H J, Xu G.Aggregat e scheduling and netw ork solving of multi-st age and multi-it em manuf acture syst em .Eur JOper · 694 · 北 京 科 技 大 学 学 报 2006 年第 7 期

Vol.28 No.7 陈超武等：ERW钢管多阶段生产计划的编制及优化 ·695。 Rs.1998.105(1):52 问题中的应用.南京航空航天大学学报，2001,33(6)：544 【5黄海军，徐刚.多阶段制造系统调度模型与资源价格研究 [习王世进，吴立蜂，陶丽华，等.互替机床提前/延期惩罚调度 北京航空航天大学学报，1998.24(5)：579 问题的启发式算法.中国机械工程，2004,15(22)：2001 6 Charalambous C,Tahmaseli T.Hind K.Modeling multi [10]ChengT C.Optimal common due date with limited comple stage manufacturing systems for efficient scheduling.Eur J tion time deviation.Comput Oper Res,1988.5(4):91 0 per Res2000(122):329 【1】张涛，王梦光，唐立新.等.钢厂合同计划的模型与算法 【刀徐和平，王德国，孙林岩.多阶段制造系统的生产计划与调 控制理论与应用，2000.17(5)：711 度综合模型.兰州理工大学学报，2004,30(3)：127 【12林铿，黄元石.基于遗传算法的ERP生产计划排单模型. 【李秀，刘文煌，姜澄字，等.遗传算法在车间批量生产计划 福州大学学报：自然科学版，2002,8(4)：502 Optimization of multi-stage production planning in ERW pipe manufacturing CHEN Chaowu,DONG Shachua,DING Wenying Mechanical Engineering School,University of Science and Technology Beijing.Beijing 100083.China ABSTRACT Multi-stage production planning plays an important role in improving the production rate and energy saving in modern manufacturing industry.Based on the analysis of production flow and planning of an electric resistance welding(ERW)manufacturing enterprise,this paper proposes an advanced/delayed punishment mathematical model of multistage production planning.A local optimal solution for it is ob- tained by the real number-coding genetic algorithm.Simulation results indicate that the model and algo- rithm are feasible and efficacious.The presented solution has well applied to practical ERW product ion planning. KEY WORDS ERW pipe;multistage production;production planning:genetic algorithm

Res, 1998, 105( 1) :52 [ 5] 黄海军, 徐刚.多阶段制造系统调度模型与资源价格研究. 北京航空航天大学学报, 1998, 24( 5) :579 [ 6] Charalambous C , Tahmassebi T, Hind K .Modeling multi￾st age manufacturing systems f or efficient scheduling .Eur J Oper Res, 2000( 122) :329 [ 7] 徐和平, 王德国, 孙林岩.多阶段制造系统的生产计划与调 度综合模型.兰州理工大学学报, 2004, 30( 3) :127 [ 8] 李秀, 刘文煌, 姜澄宇, 等.遗传算法在车间批量生产计划 问题中的应用.南京航空航天大学学报, 2001, 33( 6) :544 [ 9] 王世进, 奚立峰, 陶丽华, 等.互替机床提前/ 延期惩罚调度 问题的启发式算法.中国机械工程, 2004, 15( 22) :2001 [ 10] Cheng T C .Optim al common due date with limited comple￾tion time deviation.Comput Oper Res, 1988, 5( 4) :91 [ 11] 张涛, 王梦光, 唐立新, 等.钢厂合同计划的模型与算法. 控制理论与应用, 2000, 17( 5) :711 [ 12] 林铿, 黄元石.基于遗传算法的 ERP 生产计划排单模型. 福州大学学报:自然科学版, 2002, 8( 4) :502 Optimization of multi-stage production planning in ERW pipe manufacturing CHEN Chaowu, DONG Shaohua, DING Wenying Mechanical Engineering School, University of Science and Technology Beijing, Beijing 100083, China ABSTRACT M ulti-stage production planning plays an important role in improving the production rate and energy saving in modern manufacturing industry .Based on the analysis of production flow and planning of an electric resistance welding ( ERW) manufacturing enterprise, this paper proposes an advanced/delayed punishment mathematical model of multistage production planning .A local optimal solutio n for it is ob￾tained by the real number-coding genetic algorithm .Simulation results indicate that the model and algo￾rithm are feasible and efficacious .The presented solution has w ell applied to practical ERW production planning . KEY WORDS ERW pipe ;multistage production ;production planning ;genetic algo rithm Vol.28 No.7 陈超武等:ERW 钢管多阶段生产计划的编制及优化 · 695 ·