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