·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 最 小化 . 为 了 符 合 遗传 算法 中 计算 目标 函 数最 大值 的 习 惯 , 对