混合流水车间调度模型及其遗传算法

D0I:10.13374/j.issn1001-053x.2005.05.058 第27卷第5期 北京科技大学学报 Vol.27 No.5 2005年10月 Journal of University of Science and Technology Beijing 0ct.2005 混合流水车间调度模型及其遗传算法 崔建双李铁克张文新 北京科技大学管理学院，北京100083 摘要针对流程工业生产过程连续性的特点，从一种新的角度建立了工件等待时间受限的 混合流水车间调度模型.以总完工时间最小化和工件在各机器最早开工时间最小化为目标 函数，利用改进的遗传算法生成最优排序计划，并用模拟的实际生产数据对模型和算法进行 验证和分析， 关键词混合流水车间：调度模型：改进遗传算法 分类号TP273.1 钢铁生产核心流程包括炼钢一精炼一铸造 K道工序一一 一轧制四个主要工序阶段，阶段之间表现为有次 序的、连续的、紧密衔接的关系，若发生阶段中断 m台机器 将导致不必要的损失四.从炼钢开始到轧制成品 n个工件 入库，钢铁生产强调以整体流程的全局优化为目 标，称之为冶铸轧一体化调度问题.根据实际生 产需要，解决此类调度问题不但要获得最优生产 排序的结果，而且要能够实现动态、随机、实时性 的要求， 图1混合流水车间调度问题示意图 通过对问题实质的分析，将其归结为一类不 Fig.I Flexible flowshop scheduling model 可中断的、无等待的混合流水车间调度排程问 意两道工序间有无限的存储能力（即被加工工件 题.首先对生产流程作出合理的抽象，并据此建 在两道工序间可以等待任意时间).每个工件的 立一个工件等待时间受限的调度目标函数模型. 第k道工序可以在该道工序的任一并行机上被加 为了求解方便且不失一般性，对其中的某些约束 工，且已知每个工件在每台并行机上的加工时间 条件进行合理的简化，然后给出基于改进遗传算 tt20(i=1,2,,sj=1,2,",%k=1,2,,m,).这一问 法的求解步骤并编程，用实际生产数据对模型及 题通常记为： 算法进行评估 FFlm,h2,…,m.lEC (1) 1调度模型的建立 其中，∑C,是工件总完工时间的不减函数， 此类问题一般有如下假定：工件之间相互独 11混合流水车间调度问题的描述 立：每个工件是一个不可分割的整体；工件加工 混合流水车间作业调度也称为柔性流水作 不分先后：各工件在各工序的各台机器上的加工 业调度，是一类复杂的车间作业排序问题，见 时间是预知的，但不一定是相同的.所要解决的 图1，它相当普遍地存在于现代流程工业中， 问题是：在满足各项约束条件的基础上，确定各 设有n个工件(，，，J)按照方向一致的加 工件在各工序并行机上的加工排序，使得总的完 工路线在s道工序(Z,Z2,,Z)上顺序加工，每道 工时间最小化，即： 工序可能有m,≥1(r=1,2,,s)台同速并行机，任 minC(i=1,2,,s) (2) 收稿日期：2004-08-11修回日期：200504-20 基金项目：国家自然科学基金资助项日0No.70371057刀 文献[4]指出，上述问题只有极特殊情况下才 作者简介：崔建双(1961一)，男，副教授，博士研究生 有多项式最优算法，绝大多数情况下，在合理的

第 2, 卷 第 5 期 2 0 0 5 年 10 月 北 京 科 技 大 学 学 报 J o u r n a l o f U n iv e r s iyt o f S e i e n e e a n d eT e h n o l o gy B e ij i n g V d l 一 2 7 N 0 . 5 O C t 。 2 0 0 5 混合流水车间调度模型及其遗传算法 崔建双 李铁克 张 文 新 北京 科技 大学 管理 学院 , 北 京 10 0 0 8 3 摘 要 针 对流 程工 业 生产过 程连 续 性的特 点 , 从一 种新 的角 度建 立 了工件 等待 时 间受 限的 混 合流 水 车间调 度模 型 . 以总完 工 时间最 小化和 工 件在 各机 器最 早 开工 时间最 小化 为 目标 函数 , 利 用 改进 的遗传 算法 生成 最优 排序 计划 , 并用 模拟 的实 际生产 数据对 模 型和算 法进 行 验 证和 分 析 . 关键 词 混合流 水车 间 ; 调度 模型 : 改进 遗传 算法 分类号 T P 2 7 3 . 1 钢 铁 生 产 核 心 流 程 包 括 炼 钢一 精炼 一铸 造 一轧 制 四个主 要工 序 阶段 , 阶 段之 间表 现 为有 次 序 的 、 连 续 的 、 紧 密衔 接 的关系 , 若 发 生阶 段 中断 将 导致 不必 要 的损 失 `1] . 从 炼 钢 开始 到轧 制 成 品 入库 , 钢 铁生 产强 调 以整体 流 程 的全局 优化 为 目 标 , 称 之 为冶 铸 轧一 体 化调 度 问题 . 根据 实 际 生 产 需要 , 解决 此类 调度 问题 不 但要 获得 最优 生产 排序 的结 果 , 而且 要 能够 实现 动 态 、 随机 、 实 时性 的要 求 . 通 过对 问题 实质 的分 析 , 将 其 归结 为一 类 不 可 中 断 的 、 无等 待 的混 合 流 水车 间调 度 排 程 问 题 . 首 先对 生 产流 程 作 出合 理 的抽 象 , 并据 此 建 立一 个工 件等 待 时 间受限 的调度 目标 函 数模 型 . 为 了求解 方便 且不 失 一般 性 , 对其 中 的某 些约 束 条件 进行 合理 的简 化 , 然 后给 出基 于 改进遗 传 算 法 的求解 步骤 并编 程 , 用 实 际生产 数据 对模 型及 算法进 行评 估 . 1 调 度模 型 的建 立 L l 混合 流 水 车 间调度 问题 的描 述 混合 流 水 车 间作 业 调 度 也 称 为 柔 性 流 水 作 业 调度 , 是 一类 复 杂 的车 间 作业 排 序 问题 , 见 图 1 , 它相 当 普遍 地存 在 于 现代 流 程工 业 中 . 设有 n 个 工件 x(J , 关 , … , nJ ) 按 照方 向一 致 的加 工 路线 在 : 道 工序 忆 , 乙 , … , 乙) 上顺 序 加 工 , 每 道 工 序可 能有 mr 全 1(r = 1 , 2 , … , s) 台 同速 并行 机 , 任 收稿 日期 : 2 0 4 -() -8 1 修 回 日期 : 2 005 刁今 2 0 基金 项 目 : 国家 自然 科学基 金 资助项 目(N 认 7 0 3 71 0 5 7) 作者 简介 : 崔 建双 ( 19 61 一) , 男 , 副 教授 , 博 士研 究生 K 道工 序 一 , 一 - 一 n 个工件 l } m Z 口 口 码“ 势 器 令 图 1 混合流 水车 间调 度 问题 示意 图 F ig . l F le 五b l e fl ow s b o p s e h e d u il n g m o d e l 意两 道 工序 间有 无 限的存 储 能力 ( 即被 加 工工 件 在两 道 工序 间可 以等 待 任 意时 间 ) . 每 个 工件 的 第k 道工 序可 以在 该道 工 序 的任一 并行 机 上被 加 工 , 且 已知 每个 工件 在每 台并行 机上 的加 工 时间 ukt 全 0( i = 1 , 2 , … , 、 ;j 二 1 , 2 , … , ;n k = 1 , 2 , … , m J . 这一 问 题通 常记 为 : F F : } m , , m Z , … , m , }艺C ( l ) 其 中 , 艺C 是工 件 总完 工 时 间 的不减 函数 . 此类 问题一 般有 如 下假 定 : 工 件之 间 相互 独 立 ; 每个 工件 是 一 个不 可 分割 的整体 ; 工件 加 工 不分 先 后 ; 各工 件在 各 工序 的各 台机 器上 的加 工 时 间 是预 知 的 , 但 不一 定 是相 同的 . 所 要 解决 的 问题 是 : 在 满足 各 项约 束 条件 的基础 上 , 确定 各 工件 在 各工 序并 行机 上 的加 工排序 , 使得 总 的完 工 时 间最 小化 , 即 : m i n 艺C ( i = 1 , 2 , … , s ) ( 2 ) 文献 4[ 〕指 出 , 上述 问题 只有 极特 殊情 况 下才 有 多 项式 最优 算 法 , 绝 大 多数 情 况下 , 在 合理 的 DOI: 10. 13374 /j . issn1001 -053x. 2005. 05. 058

·624· 北京科技大学学报 2005年第5期 时间内难以获得问题的最优解， 各工序所在的并行机中，寻找加工时间最长的机 1.2无等待的流水车间调度模型 器并求和，得到最大流程时间，该时间与工件j在 以钢铁生产冶铸轧中的一个浇次排序为例， 工序i的机器k上加工时的开工时间st,加工时 一个浇次中每个炉次可视为一个工件.按照加工 间铁以及该工件在前一道工序机器r上的加工结 的先后顺序，炼钢炉、精炼炉、铸机、轧机分别视 束时间与et-w有关.在无等待的情况下，有st,F 为第1,2,3,4道工序加工用的机器.在铸坯工序 etu-r.因此通常T(=(st+t,). 中，一个炉次被分割浇铸成若干个铸坯，该炉次 式(3)第二项表示工件在工序各机器上的最 的全部铸坯完成时间被视为该工件在连铸工序 早开工时间之和，最小化该值意味着尽量减小工 的加工时间：同样，该炉次的全部铸坯轧制完成 件在工序之间的等待时间，以实现无耽搁地连续 时间被视为轧制工序的加工时间.这样就满足了 加工， 工件之间相互独立的需要， 设一个浇次内总炉次（工件）数为n,炼钢炉 2基于遗传算法求解 (并行机组1)为m,个，精炼炉（并行机组2）为m:个， 2.1染色体的设计 连铸机（并行机组3）为m台，轧机（并行机组4）m4 设计如下形式的染色体例： 台.则作业排序可以归结为组合优化问题中：n个 工件一 工件，4道工序，每道工序有m(r=1,2,3,4)台并行 g,g12,,84 机，各工件在各并行机上加工时间已知，工序间 工件82，g22,",g24 等待时间受到限制的准混合流水车间作业排序 …，,，… 问题. gi,ga,",gin 基本约束：(I)每个工件在每道工序只能被一 其中行表示工序过程，列表示工件序号，染色体 台设备加工：(2)同一设备前一工件加工完毕后 基因gi=1,2,…j=1,2,,n)携带第i道工序中 才能开始下一工件的加工：(3)同一工件前道工序 工件j在哪一台机器上被加工的信息.通常设计 结束后，才能开始下一道工序的加工；(4)每个工 g由整数和小数两部分组成，整数部分代表工序 件在工序之间的等待时间受限.工序之间以紧密 i加工用的机器序号，小数部分指示在同台机器 衔接为原则，即尽可能无耽搁地连续加工. 上加工发生冲突后的先后顺序.例如g=223,表 同时假定：(1)在所讨论的浇次中不考虑某台 示工件j由i工序的第2台机器加工，该台机器上 设备出现故障可能导致的断浇情况：(2)第一道工 可能存在需要加工两个或两个以上的工件的冲 序中首先开工的各设备开工时刻均计为0. 突，此时小数部分决定加工它们的先后顺序，较 为描述方便给出如下符号约定：为工序序 小的数先被加工， 号，j为工件序号，5为工序总数，n为工件总数， 2.2产生初始种群 k为工序内的机器序号，m,为工序i的并行机总 为了能够开始迭代计算，首先需要利用随机 数，st为工件j在工序i的机器k上的开工时间， 函数产生多组初始染色种群，其中基因g的大小 t为工件j在工序i的机器k上的加工时间，et为 变化范围与所在工序中并行机的多少有关.不失 工件j在工序i的机器k上的完工时间，wt为工 一般性，假设第i道工序有m,台并行机，则 件j在工序i和计1之间的最长允许等待时间，T 1≤g<m,+1.例如，m=3,产生一个范围在1≤g<4 为工序i的第k台机器加工总时长.很显然，etw= 之间（即有3台并行机）的染色体如下：rand0% stok+Imk. (3*100)/100.0+1.0:循环执行该语句可以得到多组 1,工件j被指定到工序i的第k台机器上 Xok= 初始种群 0,工件j未被指定到该机器上 基于以上约定，可建立如下优化目标函数： 23计算目标函数值和适应度值 周万 ()-min max[Ta(stata etsta ( 以式(3)作为目标函数.需要先计算工序i中 各台机器的总加工时间T,然后从中找出最大 其中，三x-1(基本约束1)，st之tw-(基本约束2)， 值，各工序的最大值求和：再计算各工序中各机 stm之etu-w(基本约束3)，stt一et-m≤wt基本约束 器上的最早开工时间之和. 4),st.-0(假定2). 在式(3)中，目标函数是使得)最小化.为了 式(3)第一项表示最大流程时间最小化.即在 符合遗传算法中计算目标函数最大值的习惯，对

一 6 2 4 - 北 京 科 技 大 学 学 报 2 0 0 5 年 第 5 期 时 间 内难 以 获得 问题 的最优 解 . 1 .2 无 等待 的流 水 车间 调度 模 型 以钢 铁 生产 冶铸 轧 中的一 个浇 次 排序为例 . 一 个浇 次 中每个 炉 次可视 为 一个 工件 . 按 照 加工 的先后 顺 序 , 炼钢 炉 、 精炼 炉 、 铸 机 、 轧机 分别 视 为 第 l , 2 , 3 , 4 道 工序 加 工用 的机器 . 在 铸 坯工 序 中 , 一个 炉 次被 分 割浇 铸 成若 干 个铸 坯 , 该炉 次 的全 部铸 坯 完 成 时 间被 视 为 该 工 件在 连 铸 工 序 的加工 时 间 ; 同样 , 该炉 次 的全 部铸 坯 轧制 完 成 时 间被视 为 轧制 工序 的加 工 时间 . 这 样就 满足 了 工件 之 间 相互 独立 的需 要 . 设 一 个浇 次 内总炉 次 ( 工件 ) 数 为 n , 炼 钢 炉 ( 并行机 组 l) 为m ,个 , 精炼 炉 ( 并行机 组 2) 为m Z个 , 连 铸 机 ( 并行 机 组 3) 为 m 3台 , 轧机 (并 行机 组 4) 札 台 . 则作 业排 序 可 以归结 为组合 优 化 问题 中 : n 个 工件 , 4 道工序 , 每 道工序 有脚(r = 1 , 2 , 3 , 4) 台并 行 机 , 各 工件 在 各 并行机 上 加 工 时 间 己知 , 工 序 间 等 待 时 间 受 到 限制 的准 混 合流 水 车 间作 业 排序 问题 . 基 本约 束 : ( l) 每 个 工件在 每 道 工序 只能 被 一 台设备 加 工 ; (2) 同一设 备前 一 工件 加 工 完 毕后 才 能开 始下 一工件 的加 工 ; (3) 同一 工件 前道 工序 结 束后 , 才 能 开始 下 一道 工序 的加 工 ; (4 )每 个 工 件在 工序 之 间 的等待 时 间受 限 . 工序 之 间 以紧密 衔接 为 原 则 , 即 尽可 能无耽 搁 地连 续 加 工 . 同 时假 定 : ( l) 在所 讨 论 的浇 次 中不考 虑某 台 设备 出现 故障 可能 导致 的断 浇情 况 ; (2) 第 一道 工 序 中首 先 开工 的各 设 备 开工 时刻 均 计 为 0 . 为描 述方 便 给 出如 下 符号 约 定 : i为工 序 序 号 , j 为工件 序 号 , ` 为 工序 总 数 , n 为 工件 总 数 , k 为工 序 内的机 器序 号 , m `为 工序 i 的 并行 机 总 数 , s坛 为 工件 j 在 工 序 i 的机器 k 上 的 开工 时 间 , 标为 工件j 在 工 序 i 的机 器 k 上 的加工 时间 , et , 为 工 件 j 在 工序 i 的机 器 k 上 的完 工 时 间 , w 粉为工 件j 在 工 序 i 和 +1 1 之 间 的最长 允 许 等待 时 间 , 几 为 工序 i 的第 k 台机 器 加工 总 时 长 . 很 显然 , e t夕户 s标十t沙 . 各工 序所 在 的并 行机 中 , 寻 找加 工 时 间最 长的机 器并 求 和 , 得 到最 大流 程 时 间 , 该 时 间与 工衔在 工序 i 的 机器 k 上加 工 时 的 开工 时 间 s标 , 加 工 时 间标 以及 该 工件 在 前 一道 工 序机 器 r 上 的加 工 结 束 时 间与 e 标 一 ,卜 有 关 . 在 无 等 待 的情 况 下 , 有 #st 行 氏 一 1* . 因此 通 常 几(…卜酬 s t夕汁标) . 式 (3 ) 第 二 项 表示 工 件在 工 序 各 机器 上 的最 早开 工 时 间之 和 , 最小 化 该值 意 味 着 尽量 减 小工 件 在 工序 之 间 的等 待 时 间 , 以实 现无 耽搁 地 连续 加 工 . 2 基 于 遗传 算 法 求解 .2 1 染色体 的设 计 设 计如 下 形式 的染 色体 `5] : 工 件~ 91 2 , ’ . ’ , 乡 2 , ` ” , , , 知 , “ ` , 9 14 1 竺 ` { 幽) 1, ,1 了 卜阔陈厂ó 工|件 X一 {; : 工 件 j 被指 定 到 工序 i 的第 k 台机器 上 工件 j 未被 指 定 到该 机 器上 基 于 以上约 定 , 可 建 立如 下优 化 目标 函 数 : f( )t =m in }全兽臀[兀( s `, ,彻 , e ” 卜 1* )] + 蓦乌 s `, 其 中 , 叠 x 广 `( 基 本约束 `), s标泛 et 。 一 试基 本约 束 2) , st , 之 e丸 一 碱基 本 约 束 3) , st , 一 e拓 一 1, ` wt 式基 本 约 束 4 ) , s t lj, = 0 (假 定 2 ) . 式 (3 )第 一项 表 示最 大流 程 时间最 小化 . 即在 其 中行 表 示工 序 过程 , 列 表 示 工件 序 号 . 染 色 体 基 因岛( i = 1 , 2 , … ;k j = 1 , 2 , … , n) 携 带第 i 道 工序 中 工件 j 在 哪一 台机器 上 被 加 工 的信 息 . 通 常 设计 肠 由整 数 和 小数 两 部分 组 成 , 整 数 部 分代 表工 序 i 加工 用 的机 器 序 号 , 小 数部 分 指 示在 同台机 器 上 加 工 发生 冲 突后 的先后 顺序 . 例如肠 = .2 23 , 表 示 工衔 由 i 工序 的第 2 台机 器 加 工 , 该 台机 器 上 可 能 存 在 需 要加 工 两 个 或 两 个 以上 的工 件 的 冲 突 , 此 时小 数 部分 决 定加 工 它 们 的先 后顺 序 , 较 小 的数 先 被 加工 . .2 2 产 生 初 始种 群 为 了能够 开始 迭代 计 算 , 首 先 需要 利用 随 机 函 数 产 生 多组 初始 染 色 种群 , 其 中基 因岛 的大 小 变化 范 围与所 在 工序 中并行 机 的多 少有 关 . 不 失 一 般 性 , 假 设 第 i 道 工 序 有 m ` 台 并 行 机 , 则 1` 肠< m +,l . 例如 , m 尸 3 , 产 生 一个 范 围在 1` 岛 < 4 之 间 ( 即有 3 台 并行 机 ) 的染 色体 如 下 : arn d o % (3 * 10 0) l/ 0 .0 0 十 1 . ;0 循 环执 行该 语句 可 以得 到 多组 初 始 种群 . .2 3 计 算 目标 函 数值 和 适 应 度值 以式 (3) 作 为 目标 函 数 . 需要 先 计算 工 序 i 中 各 台 机 器 的 总加 工 时 间 兀 , 然 后 从 中找 出最 大 值 , 各 工 序的最 大 值求 和 ; 再 计算 各 工序 中各 机 器 上 的最 早开 工 时 间之 和 . 在 式 (3 ) 中 , 目标 函 数 是 使得八)t 最 小化 . 为 了 符 合 遗传 算法 中 计算 目标 函 数最 大值 的 习 惯 , 对

VoL.27 No.5 崔建双等：混合流水车间调度模型及其遗传算法 ·625· 式(3)进行适当的变换，得到如下目标函数： 交叉 maxF()) (4) (3)变异.为了保证种群的稳定性，选择变异 针对种群中的各染色体，计算公式(4)的个体 发生概率P≤0.001.采用循环方式过滤种群的每 适应度值F,以及个体相对适应度值F,/∑F,p= 个基因，当产生的随机数值p<P时，将当前基因 1,2,…,P),其中P是种群的染色体总数量. 的整数部分随机增或减1，只要始终确保每个基 2.4选择、交叉和变异 因整数部分的变化在合法的范围内即可， (1)选择.为了确保适应度较大的一些个体能 3 仿真实现及结果分析 够被保留到下一代种群，采用确定式采样来选择 复制染色体.先计算每个个体在下一代种群中期 现假定一个浇次有12炉钢水（工件），经过炼 望生存的数月，=PF,/∑F,(p=1,2,…,P):然后取 钢一精炼一连铸一轧制4道工序，每道工序分别 各N的整数值作为该个体在下一代种群中出现 有3/322台并行机，则所解问题可表示为： 的数量，由此可确定出下一代种群中ΣN」 FF1z3,3,2,2,nwt,prmuΣC,(i=1,2,3,4) (=1,2,…,P)个个体，符号L」表示取整：最后按 nwt表示准无等待，即工序之间的等待时间 照各N(=1,2,…,P)的小数部分对个体降序排列， 受限：pmu表示流水作业含有不可中断之意. 顺序取前P-ΣLN个个体补充到下一代种群， 每个工件在每道工序中的加工时间已知，如 由此共得到P个新染色体组成一组新种群， 表1所示， (2)交叉.采用两两随机分组交叉方式.各对 取交叉概率P=0.60,变异概率Pm0.001,种群 染色体产生交叉的概率P设为一个固定值，比如 规模为30，经过600轮迭代（普通P℃机约70s)后 P.=0.60.当产生0-1之间的随机数值p<P.时，发生 得到较满意的目标函数值.排序过程如图2的甘 交叉.交叉只发生在同一工序的染色体之间，以 特图所示.其中，P的取值是一个经验值，在实际 确保基因变化的合法性.交叉点随机选择在1~n 运行中P的变化范围可在0.40.8之间.实践表 之间的任意一点，交叉点之后的全部基因进行 明，P的变化选取对运算结果影响不大， 表1工件、工序、机器与加工时间表 Table I Working piece/procedure/macbine and process time table min 工件 工序 机器 3 4 6 7 8 9 10 11 12 1 5 45 50 50 45 45 47 50 48 45 46 48 2 50 牙 48 6 牙 50 45 A6 47 50 50 3 5 48 48 45 47 46 47 45 47 35 35 35 34 30 30 31 32 33 33 34 35 35 36 36 38 35 35 30 30 34 33 30 31 3 30 35 36 35 50 50 35 34 30 50 35 1 30 35 31 32 34 33 35 34 34 35 30 32 34 34 33 之 32 31 30 30 35 30 25 25 30 之 28 30 29 24 25 32 31 25 26 30 31 26 25 27 3 26 25 30 50 100 150 185 250 300 350 机器1 工序I 机器2 93 10 11 机器3 4☐87 单位：oin 机器1 53 2 工序I 机器2 10 4☐25 42 机器3 322 机器1 工序Ⅲ 8010 59822 机器2 81 4☐2 机器1 1586口▣ 工序IV 115 C27 机器2 1075 工4☐343 图2甘特图 Fig.2 Gantt chart

V bl . 2 7 N o . 5 崔建 双等 : 混合 流 水车 间调 度模 型及 其遗 传算 法 一 6 2 5 . 式 (3 ) 进 行适 当的变 换 , 得 到如 下 目标 函 数 `7] : m a 沁到t) 一 共J Lt) ( 4 ) 针 对种 群 中 的各染 色体 , 计 算 公式 ( 4) 的个 体 适 应 度 值凡 以及 个 体 相 对 适 应 度 值 凡泛凡勿= l , 2 , … , )P , 其 中尸是 种群 的染 色体 总 数量 . .2 4 选择 、 交 叉和 变 异 ( l) 选 择 . 为 了确 保适 应度 较大 的一些 个体 能 够 被保 留到下 一代 种群 , 采用 确定 式采 样来选择 复制染 色体 . 先计 算每 个 个体在 下 一代 种群 中期 望 生存 的数 目拟 = .P 凡泛凡 勿= 1 , 2 , …乃 ; 然 后取 各拟 的 整 数 值 作为 该个 体 在 下 一 代 种 群 中 出现 的 数 量 , 由此 可 确 定 出 下 一 代 种 群 中艺 卜N ) J (=1 1 , 2,. 二 乃个 个 体 , 符 号 L J 表 示 取整 ; 最 后按 照 各茂 (=1 1 , 2 , … 乃的 小数 部分 对 个 体 降序 排 列 , 顺 序取 前尸一 艺 仁脚; J 个个 体 补充 到 下一 代种 群 , 由此共 得 到尸个 新 染色 体 组成 一 组新 种 群 . (2 ) 交 叉 . 采 用 两两 随机 分 组 交 叉方 式 . 各 对 染 色体 产生 交 叉 的概率 cP 设 为 一个 固定值 , 比 如 cP = .0 60 . 当产 生 O一 1 之 间 的随机 数值尸 <只 时 , 发 生 交叉 . 交 叉只 发 生在 同一工 序 的染色 体之 间 , 以 确保 基 因变 化 的合 法 性 . 交 叉 点 随机选 择 在 1一n 之 间 的任 意 一 点 , 交 叉 点 之 后 的全 部 基 因进 行 交叉 . (3) 变 异 . 为 了保 证 种群 的稳 定性 , 选 择 变异 发生 概率 mP ` .0 0 0 1 . 采用 循 环 方式 过滤 种 群 的每 个 基 因 , 当产 生 的随 机 数值尸切 m 时 , 将 当前基 因 的整 数部 分 随机 增 或减 1 , 只 要始 终确 保 每个 基 因整 数部 分 的变 化 在合 法 的 范 围 内即可 . 3 仿 真 实 现及 结 果 分 析 现 假 定 一个 浇 次有 12 炉 钢水 (工 件 ) , 经 过炼 钢一精 炼一连铸 一轧制 4 道 工序 , 每 道 工序 分别 有 3 3/ 2/ 2/ 台 并行 机 , 则 所解 问题 可表 示 为 : F F , 2 13 , 3 , 2 , 2 , n wt , p mur }艺C (=1 1 , 2 , 3 , 4 ) 11 v 八 表 示准 无等 待 , 即工 序之 间的 等待 时 间 受 限 ; pmr u 表 示 流水 作 业含 有 不可 中断之 意 . 每 个 工件 在每 道工 序 中的加 工 时间 已知 , 如 表 1 所 示 . 取 交叉 概率 cP 二.0 60 , 变异 概 率几= .0 00 1 , 种 群 规 模 为 30 , 经过 6 0 轮 迭代 (普 通 P C 机 约 70 5) 后 得 到较 满 意 的 目标 函 数 值 . 排 序过 程 如 图 2 的甘 特 图所 示 . 其 中 , 只 的取 值 是一 个经 验值 , 在实 际 运 行 中cP 的变 化 范 围可 在 .0 小.0 8 之 间 . 实践 表 明 , cP 的变 化 选取 对运 算 结 果影 响 不大 . 表 1 工 件 、 工序 、 机 器 与加工 时间表 aT b l e 1 W o r址 n g P i e c e l P er c ed u er/ m a c h i n e a n d p功c e s s it m e t a b l e 工 序 机 器 工件 么 , 门 兰旦不一洲丝气一节 旦 , , 18, 2 5。 。 0 工一 薰 一 , 二可一了一可一下产一厂二尸 9, 二二互二〔 二互二二〔 二1 二1 二 , 8 7 单位 : m , 4匕口 仁 1 二工二 , ~ 2 2。 工 序 n 机器 1 4 7〔 立口 二工〕 〔 口 〔 三二习 2 2, 2 4 2 咒厂 , 一门 l布 , .丁-下一丁气了门 机器 2 8 0二1二亘〕 广了 , 广下门尸下 - 下飞厂丁下了丁 2 2 7 8〔二艺习 「宝二了二了二〕 『一节一门 , - 犷 , 2 7 5 机器 3 ` , 8 1二二二」〔 二〔 卫二习二正习 已j 4 7 日币一丁- r 下共尸1 1二三习 厂飞一 T- 下 ~ 下不门妈 , 工序 nI 机器 1 机器 2 工序 W 机器 1 机器 2 图 2 甘特 图 F i g . 2 G a n t e h a rt

·626· 北京科技大学学报 2005年第5期 图2中每个时间段代表一个工件，其中标明 结构.东北大学学报（自然科学版），1996(12)：663 了工件序号，每台机器加工的结束时间标注在每 [2]Goldberg D E.Genetic Algorithms in Search,Optimization,and Machine Learning.New York:Addison-Wesley Publishing 行的尾部，从图可见，各工序设备的加工任务比 Company Inc,1989 较均匀，获得了充分利用.优化排序后的最大流 [3]Srinivas M,Patnaik LM.Adaptive probabilities of crossover and 水时间为347min,此值并非是最优值，而是一个 mutation in genetic algorithms.IEEE Trans Syst Man Cybern. 近优值.利用遗传算法得到的结果往往是近优 1994,244):656 [4)唐恒永，赵传立.排序引论.北京：科学出版社，2002,6：115 值，但相对于人工经验排序来说，利用智能优化 [5】吴云高，王万良.基于遗传算法的混合Flowshop调度，计 的数学方法所得到的结果，一方面准确度得到了 算机工程与应用.2002,12：82 改进，另一方面也大大提高了排序效率，是当代 [6]Sriskandarajah C.Performance of scheduling algorithms for no- wait flowshops with parallel machines.Eur J Oper Res,1993, 智能调度排序理论和实践的热门课题. 70:365 参考文献 []周明，孙树栋.遗传算法原理及应用.北京：国防工业出版 社，2000 [1】唐立新，杨自厚，王梦光，炼钢一连铸生产的计划与调度 Hybrid flowshop scheduling model and its genetic algorithm CUI Jianshuang,LI Tieke,ZHANG Wenxin Managemnent School,University of Science and Technology Beijing,Beijing 100083,China ABSTRACT With the non-breakable feature in steel product making,an integrative scheduling model was pre- sented.The object was to minimize the flow span time and the wait time between working steps.One furnace was counted as one working piece and several furnaces were regarded as one cast.By using the improved genetic algo- rithm,a cast scheduling table and a subsequent Gantt chart described the results.A group of typical testing data va- lidated the results. KEY WORDS hybrid flow shop;integrative scheduling model;improved genetic algorithm

一 6 2 6 - 北 京 科 技 大 学 学 报 2 0 5 年 第 5 期 图 2 中每 个 时 间段代 表 一 个 工件 , 其 中标 明 了工件 序号 , 每 台机器 加工 的结 束 时 间标 注 在每 行 的尾 部 . 从 图可 见 , 各 工 序 设备 的加 工 任 务 比 较 均匀 , 获 得 了充 分 利用 . 优化 排 序 后 的最 大流 水 时 间为 3 4 7 m in , 此 值 并 非是 最优 值 , 而 是 一个 近 优 值 , 利用 遗 传 算 法 得 到 的结 果 往 往 是 近优 值 , 但 相 对 于人 工 经 验排 序 来说 , 利用 智 能 优化 的数学 方法 所 得到 的结 果 , 一方 面 准确 度得 到 了 改 进 , 另 一 方 面也 大 大提 高 了排 序 效率 , 是 当代 智 能调 度 排序 理 论 和 实践 的热 门课 题 . 参 考 文 献 【l] 唐立 新 , 杨 自厚 , 王 梦光 . 炼 钢一连 铸生 产 的计划 与调度 结 构 . 东北 大学 学报 ( 自然 科学 版) , 19 9《 12) : 6 63 [ 2 ] G o ldb e r g D E . G e n e ti e A lg o n th m s in S e批h , O Pt im i atZ i o n , 阶d M a c h in e L e arn ign . N ew oY rk : A d is o n 一 We sl ey P ub ils h吨 C o m P an y I n e , 19 8 9 [ 3 ] S irn i v as M , P aht a ik L M . A 山印ti v e P r o b ab i lit i e s o f c or s s o v er an d m u iat 皿 in g e n e ti e a lg o ir ht m s . IE E E I 丫a n , S y . t M a . C y b e r . . 19 9 4 , 2 4 (4 ) : 6 56 14 』唐恒 永 , 赵 传立 . 排序 引 论 . 北京 : 科 学出版 社 , 2 002 , :6 1 15 5[] 吴 云 高 , 王万 良 . 基 于遗 传 算法 的混合 lF ow s b 0 P 调 度 . 计 算 机工 程 与应用 . 2 0 02 , 12 : 82 汇6 ] S ir s k an d ar aj ah C . P e r of rm an e e o f s e h e d u l i n g al g ior tl zm s ofr n o - W a i t fl o w sh o P s w i th P ar ll e l m a e h ine s . E u r J 0 p e r R . , 19 9 3 , 7 0 : 3 6 5 7[ 1 周明 , 孙树 栋 . 遗传 算法 原理 及应用 . 北京 : 国防工业 出版 社 , 2 0 0 0 H y b r i d fl o w s h o P s e h e du li n g m o d e l an d it s g e n e t i c a lg o ir th m C UI 涌沁n s h u a 矛 19, Ll iT e ke , 刀去咬刃 G M助ag e m e nt S c h o o l , U n i v e rs ity o f s e i e n c e an d eT e hn o l o gy B e ij in g , B e ij in g l 0 0 0 8 3 , C h i n a A B S T R A C T iWht ht e n o n 一 b r e a k a b l e fe a h 叮e in s t e e l Por d cu t m ak i n g , an I n t e gr iat v e s e h e du lign m o de l w as P r e - s e n t e d . hT e obj e e t wa s t o m i n im i z e ht e fl o w sP an it m e an d ht e wa it tim e b e 妇刀 e e n w o lr 石gn s t eP s . On e fu rn ac e w as e o u n t e d a s o en w o r k l n g P i e e e an d s e v e ar l fu m a e e s w er e er g ar d e d as o n e e a s t . B y u s ign t h e lm P r vo e d g en e t i e a lg o - ir th m , a c as t s c h e d u li n g t ab l e an d a s ub s e q u ent G a n t ch art de s icr b e d het er s ult s . A gr o uP o f yt Pi e a l t e s t i n g d at a v a- li d at e d ht e er s u lt s . K E Y W O R D S hy ibr d fl o w s h oP ; i n t e gr a t iV e s c h e du l i n g m o d e l: im rP o v e d g en it e al g o ir th m