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 chartV 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