·242 北京科技大学学报 2005年第2期 单班生产计划 根据每个工位处理各炉次的处理顺序对各 可 不个轧铜革位成品材 炉次编码进行排序，组成工位链码.如1LF工位 的倒种、宽度 上的工位链码为1,2,3,4.所有工位的工位链码 各轧制批的厚度、重 组成一个大的链码，即染色体.根据各个工位的 量，质量级别和坯单 堂 第一包钢水开始处理时刻（从初始调度计划中获 规则库 山 得)和各个工位上各炉次的处理顺序及各炉次的 轧制顺序 处理周期，可以确定各次在各个工位上的处理开 进行规程检验 始、结束时刻，即得到一个完整的调度计划. 假设1“电炉治炼3个炉次，2电炉治炼3个炉 检验通过？ 次，分别编号为1,2,3和1'，2'，3'.则一条染色体如 是 图4所示 轧制计划 123"23123231231!23 炼钢、连铸、轧钢 1”电炉 2电炉11F21F1连铸2连铸 体初始调度计划 图4一条只包含炉次号的染色体 图2初始调度计划生成流程图 Fig.4 Chromosome with heat number only Fig.2 Flow chart of the initial schedule plan (2)适应度函数确定. 优)算法，它是模拟自然界中的生命进化机制，在 假设N个炉次分别用L,(=1,2,,)表示，M 人工系统中实现特定目标的优化剧.为了提高搜 个工位分别用m0=1,2,,M0表示，L在工位m上 索效率，在动态调度遗传算法的交叉、变异等操 的处理时间为P,L在m上的开始处理时刻为t, 作中引入薄板坯连铸连轧流程的调度规则，具体 结束处理时刻为C,C为连铸工位上单位断浇时 操作如下. 间的惩罚费用，C2为炉次L在工位m的单位等待 (1)编码. 时间的惩罚费用，C,为调度计划中工位m,上出现 将初始调度计划编码生成遗传算法的初始 前后两个炉次处理时间重叠时的单位重叠时间 种群，若是以每个炉次在每个工位的处理开始、 惩罚费用，Cc表示连铸工位的集合， 结束时刻编为基因链码，那么遗传算法将很难运 适应度函数由下式构成： 行.一般的Job-Shop调度问题采用顺序编码.对 F=HG (1) 于薄板坯连铸连轧流程的调度，对顺序编码进行 式中，F为适应度函数，J为目标函数，G为惩罚函 扩充，具体如下：对1电炉和2电炉计划生产的 数. 每炉钢水分别进行编号作为炉次号，如1“电炉有 目标函数取决于如下几个方面. 1,2,3,…;2电炉有1,2,3….对每炉钢水在每 ①连铸机断浇的损失费用最小，计算公式： 个工位上的基因取如图3的形式 人点ecu一Cmm (2) Begin Time End Time ②炉次在各工位的等待损失费用最小，计算 If Begin If End 公式： Heat Number he8n3C-C,）-mim (3) 图3基因图 ③炉次的处理总时间最小，计算公式： Fig.3 Chart of gene J=Σ∑Pg→min (4) 1010 图3中，Begin Time表示在某工位该炉次的处 惩罚函数根据约束条件构成，当违反工位设 理开始时刻；End Time表示在某工位该炉次的处 备的惟一性约束（即两个炉次在同一工位上的处 理结束时刻；f Begin表示该炉次在某工位是否 理时间出现重叠时)，引入惩罚函数，计算公式： 已经开始处理，若已经开始取“Y”,否则取N”.If J=∑∑C(Cg-t4) (5) EiIN-1]JE[1M End表示该炉次在某工位是否已经处理完毕，若 则适应度函数F为： 己经处理完毕取“Y”,否则取“N”.Heat Number表 F=C-(5J1+52+J)-5G (6) 示炉次号. 式中，C为一个足够大的整数，保证F>0:点，点，，点一 2 4 2 - 北 京 科 技 大 学 学 报 2 0 0 5 年 第 2 期 各 轧 制 批 的 厚 度 、 重 量 、 质 量 级 别 和 坯 单 重 轧 制 计 划 炼 钢 、 连 铸 , 轧 钢 一 体 初 始 调 度 计 划 根 据 每 个 工 位 处 理 各 炉 次 的 处理 顺 序 对各 炉 次 编码 进 行 排序 , 组 成 工位 链 码 . 如 1 “ L F 工位 上 的工 位链 码 为 1 , 2 , 3 奄, 4 . 所 有 工 位 的工 位 链码 组 成 一 个大 的链码 , 即染 色 体 , 根 据 各个 工 位 的 第 一 包钢 水 开始 处 理 时刻 ( 从 初始调 度 计划 中获 得 ) 和 各 个工 位 上各 炉 次 的处 理顺 序 及 各炉 次 的 处理 周期 , 可 以确定 各 次在 各个 工位 上 的处理 开 始 、 结 束 时刻 , 即得 到 一 个完 整 的调度 计 划 . 假 设 1 “ 电炉冶 炼 3 个 炉 次 , 2 ” 电炉 冶炼 3 个 炉 次 , 分别 编 号为 1 , 2 , 3 和 1 ’ , 2 , , 3 ’ . 则 一条 染色 体 如 图 4 所 示 . 1 2 3 1 “ 电炉 1 , 2 , 3 , 1 2 3 1 , 2 ` 3 , 1 2 3 2 “ 电炉 1气 F Z “ L F I ”连 铸 图 4 一条 只包 含炉次 号 的染 色 体 iF .g 4 C h or m o s o m e w iht h e a t n u m b e r o n ly 1 , 2 , 3 , 2 ” 连铸 图 2 初始 调 度 计划 生成 流程 图 F ig . 2 F l o w e h a r t o f ht e i n i it a l s c h e d u l e lP a n 优 )算法 , 它 是模 拟 自然 界 中 的生命 进 化机 制 , 在 人 工系 统 中 实现 特定 目标 的优 化 ` 8, . 为 了提 高搜 索 效率 , 在 动态 调度 遗 传 算法 的交叉 、 变 异等 操 作 中 引入 薄 板坯 连铸 连轧 流 程 的调度 规则 , 具体 操作 如 下 . ( 1) 编码 . 将初 始 调度 计 划 编 码 生成 遗 传 算 法 的初 始 种群 . 若 是 以每 个 炉 次在 每 个工 位 的处 理 开始 、 结束 时刻 编 为基 因 链 码 , 那 么 遗 传算 法将 很 难运 行 一 般 的 oJ 卜S ho p 调度 问题采 用顺 序编 码 , , , 对 于薄 板 坯连 铸连 轧流 程 的调度 , 对顺 序编 码 进行 扩 充 , 具 体 如下 : 对 1 # 电炉和 2 “ 电炉计 划 生产 的 每炉 钢 水分 别进 行 编 号作 为炉 次 号 , 如 1 “ 电炉有 1 , 2 , 3 , … ; 2 “ 电炉有 l ’ , 2 , , 3 , , · … 对每 炉 钢水 在 每 个工 位 上 的基 因 取如 图 3 的 形式 . (2 ) 适 应度 函数 确 定 . 假 设 N 个 炉 次 分别 用 L ` i( = l , 2 , … , 川 表示 , M 个 工 位 分 别用 巩 仃= 1 , 2 , 一 , 娜表 示 , 几在 工 位码 上 的 处理 时 间 为几 , L ,在 琳上 的 开始 处 理 时刻 为#t, 结束 处 理 时刻 为 G , C , 为连 铸 工位上 单位 断浇 时 间 的惩 罚费 用 , Q , , 为 炉 次么在 工位 mj 的单位 等 待 时 间的 惩罚 费用 , 已 、 为调 度计 划 中工 位 mj 上 出现 前后 两 个 炉 次 处 理 时 间 重 叠 时 的单 位 重 叠 时 间 惩 罚费 用 , cC 表 示连 铸工位 的集 合 . 适 应 度 函 数 由下 式构 成 : F 二 +J G ( l) 式 中 , F 为适应 度 函数 , J 为 目标 函数 , G 为 惩 罚函 数 , 目标 函 数刀仅决于 如 下几 个 方面 . ①连铸 机 断浇 的损 失费 用最 小 , 计 算 公式 : 了任 I一万一 z } , J 〔 Q C l (t, 、 一 几 )一 m in B e g in T nU e El l〔 I Ti m e e g in } H e at N Un l b e r ②炉 次在 各 工位 的等待 损 失 费用 最 小 , 公式 : (2 ) 计 算 I f E n d 图 3 基 因 图 F i会 3 C h a rt o f ge n e 图 3 中 , B e ig n T im e 表 示在 某 工位 该炉 次 的处 理 开始 时刻 ; E n d iT m e 表 示在 某 工位 该炉 次 的处 理 结束 时刻 ; f B eg in 表 示 该炉 次在 某 工位 是否 己经 开 始 处理 , 若 已经 开始 取 “ Y ” , 否 则取 ` ,N ” . fI Edn 表 示 该炉 次在 某 工 位是 否 己经 处 理 完毕 , 若 已经 处 理完 毕 取 “ ’Y , , 否 则取 “ N’ , . H e at N u m b er 表 示炉 次 号 . 关一 艺。 。晨 1」了。 「急 ,」G ) 。 ( “ 、二 1一 q ) 一 im n ( 3 ) ③ 炉 次 的处 理 总 时 间最 小 , 计 算 公 式 : 珑 一 ; 鼎 , 。 悬声一 m ` n (4 ) 惩 罚 函数 根 据约 束 条件 构 成 , 当违 反工 位 设 备 的惟 一性 约束 ( 即 两 个炉 次 在 同一 工位 上 的处 理 时间 出现 重 叠 时 ) , 引入 惩 罚 函 数 , 计 算公 式 : 泥 一 ,。 怎 一 ljJ 。 忌已式几 一 +it 动 (5) 则 适 应度 函数 F 为 : F 二 C 一 (吞成十藻决十曝泥) 一 氛G ( 6 ) 式 中 , C 为 一个足 够 大 的整数 , 保证卢卜O ; 吞 , 条 , 吞 , 吞