基于DBR模型的生产排程研究

基 于D B R 模 型 的 生 产 排 程 研 究 口郑秋雁 江南大学 机械 工程学 院 口钱静 江苏无锡2 1 4 1 2 2 摘要 在有限资源条件下对企业生产进行 计划 需要 将重心聚焦在 限制产能产 出的资源上 在约束理论的基础上 将 D r u m B u f f e r R o p e模 型导八生产环节 基 于约束资源进行生产排程 以最小化最大生产时 间为 目标 通过遗传 算法得 到最优解 仿真结果表 明 在保证约束资 源不停工 的情 况下 排程 总时间为 5 2 6 rai n 与实际情况进行对比后证明该方法 切 实可 行 关键词 约束理论D B R模 型约束资源遗传算法 中图分类号 T H1 6 2 文献标识码 A 文章编号 1 0 0 0 4 9 9 8 2 o 1 4 o 5 0 0 4 5 0 4 生 产 排 程 作 为 生 产 管 理 的 核 心 问 题 一 直 受 到 广 泛 的 关 注 如 何 充 分 利 用 生 产 资 源 提 高 生 产 效 率 是 企 业 一 直 追 求 的 目标 对 于 目前 比 较 通 用 的 生 产 管 理 技 术 制 造 资 源 计 划 Ma n u f a c t u r i n g Re s o u r c e P l a n n i n g MRP 1 I 旨 在 合 理 利 用 资 源 降 低 库 存 通 过 集 中 式 的 计 划 方 式 按 无 限 能 力 编 排 各 个 工 序 的 生 产 追 求 能 力 的 平 衡 准 时 生 产 方 式 J u s t I n Ti me J I T 旨 在 消 除 一 切 浪 费 通 过 看 板 控 制 模 式 以 有 限 能 力 计 划 进 行 编 排 后 道 工 序 传 递 生 产 需 求 信 息 上 游 工 序 按 时 按 量 向下 游 工 序 传 递 所 需 的 产 品 不 考 虑 能 力 的 平 衡 l 2 MR P 和 J I T在 生 产 改 善 方 面 均 能 达 到 很 好 的 成 效 但 是 对 于 生 产 系 统 中 的 所 有 资 源 都 相 同 对 待 不 具 有 很 强 的 针 对 性 约 束 理 论 T h e o r y o f C o n s t r a i n t s T OC 将 企 业 在 实 现 其 目标 的 过 程 中 存 在 的 限 制 因 素 称 为 约 束 资 源 通 过 识 别 和 消 除 这 些 约 束 使 企 业 更 有 效 地 实 现 目标 具 有 很 强 的 针 x 性 和 快 速 性 1 D B R模 型的应用步骤 T0 C 理 论 由 E l i y a h u M Go l d r a t t 博 士 于l 9 8 6年 创 立 目前 已 广 泛 应 用 于 各 行 业 T 0C 的 基 本 思 想 源 于 局 部 系 统 的 最 优 不 一 定 是 全 局 最 优 和 优 化 是 一 个 持 续 改 善 的 过 程 D r u m Bu f f e r Ro p e模 型 简 称 DBR 是 T 0C 理 论 解 决 生 产 制 造 中 的 问 题 的 一 种 方 法 E 3 具 体 操 作 流 程 找 出 系 统 的 约 束 资 源 即 生 产 中 的 产 能 制 约 资 源 Ca p a c i t y C o n s t r a i n t Re s o u r c e s CC R 为 应 对 系 统 中 的 波 动 因 素 需 在 约 束 资 源 之 前 设 立 一 定 的 缓 冲 Bu f f e r 以保 护 生产 顺利 进 行 因约 束 资源 决定 整个 系 统 的 有 效 产 出 故 约 束 资 源 的 生 产 节 奏 Dr u m 决 定 了 系 统 的 生 产 节 奏 非 约 束 资 源 需 要 通 过 绳 子 Ro p e 收稿 日期 2 0 1 3年 1 1月 机械制造 5 2 卷 第 5 9 7 期 充分 配合 约束 资 源 的生 产节 奏 通过 增加 设备 等方 式 来 提 高 约 束 资 源 的 产 能 使 当 前 的 约 束 资 源 变 成 非 约束 资 源 回到 找 出系统 中新 的约束 资源 通 过 合 理 控 制 生 产 现 场 的 生 产 节 奏 缓 冲 量 和 投 料 节 奏 增 加 系 统 有 效 产 出 缩 短 生 产 前 置 时 间 并 减 少 在 制 品 库 存 从 而 保 证 生 产 环 节 的 顺 利 进 行 1 1 找 出 系 统 的 约 束 资 源 约 束 资 源 是 指 系 统 中 实 际 生 产 能 力 小 于 或 等 于 生 产 负 荷 的 资 源 这 类 资 源 限 制 了 整 个 企 业 的 产 出 一 般 确 定 约 束 资 源 是 通 过 比 较 系 统 中 所 有 工 序 的 产 能 负 荷 比 产 能 负 荷 比值 最 大 的 工 序 为 约 束 资 源 设 备 的 产 能 负 荷 比 为 X C 乙 C f x Af 1 L x De ma r t d 式 中 置 为 设 备 i 的 产 能 负 荷 比 C 为 设 备 i 所 能 提 供 的 产 能 L 为 设 备 i 的 负 荷 为 设 备 i的数 量 A 为 设 备 i 的 理 论 可 用 工 时 为 产 品 k在 设 备 i 上 的 实 际 加 工 时 间 De ma n d 为 经 过 设 备 i的产 品 k的 需 求 量 根 据 式 1 产 能 负 荷 比最 小 的 工 序 为 系 统 的 约 束 资 源 且 同 一 时 刻 系 统 中 只 存 在 一 个 约 束 资 源 在 挖 尽 打 破 约 束 后 约 束 便 会 转 移 至 其 它 工 序 此 时 需 要 进 行 新 一 轮 的改 善 1 2确 定 系 统 的 缓 冲 区 及 缓 冲 量 设 定 缓 冲 区 是 为 了保 护 约 束 资 源 避 免 系 统 中 的 不 稳 定 因 素 影 响 到 约 束 资 源 的 利 用 和 最 大 化 系 统 的有 效 产 出 缓 冲 区 设 置 在 约 束 资 源 和 交 期 之 前 分 别 称 为 约 束 缓 冲 和 出 货 缓 冲 缓 冲 时 间 的 大 小 包 含 在 制 品 的 加 工 和 调 整 准 备 时 间 系 统 的 不 稳 定 宽 裕 时 间 与 高 峰 的 宽 裕 时 间 等 为 了 简 单 估 计 一 般 会 设 置 与 总 加 工 时 间 成 某 种 比 例 的 关 系 比 较 稳 定 的 系 统 可 能 只 需 一 般 总 加 3 2 时 间 即 可 本 文 约 束 缓 冲 区 长 度 设 置 为 约 束 2 O1 4 5 工 序 前 加 工 时 间 的 1 2 出 货 缓 冲 时 间 设 置 为 约 束 工 序 至 末 道 工 序 加 工 时 间 的 1 2 1 3确 定 约 束 资 源 的 生 产 节 奏 在 基 于 DBR模 型 排 程 时 最 重 要 的 是 确 定 约 束 资 源 的 生 产 节 奏 由 于 本 文 仿 真 的 数 据 来 自库 存 式 生 产 企 业 故 需 要 确 定 适 合 于 此 类 企 业 的 生 产 排 程 计 划 因 库 存 式 生 产 不 存 在 严 格 意 义 上 的 交 货 期 问 题 在 排 程 时 重 点 考 虑 约 束 资 源 的 利 用 率 最 大 并 选 择 将 最 小 化 最 大 完 工 时 间 作 为 目标 函 数 1 4确 定 非 约 束 资 源 配 合 生 产 的 节 奏 根 据 T OC理 论 非 约 束 资 源 只 要 能 配 合 约 束 资 源 的 生 产 即 可 之 后 的 工 序 根 据 推 式 生 产 进 行 排 程 调 度 法 则 一 般 采 用 先 到 先 服 务 F i r s t I n F i r s t S e r v i c e F I F S 约 束 资 源 之 前 的 工 序 依 据 拉 式 生 产 进 行 排 程 即 以 该 作 业 在 约 束 资 源 处 的 开 始 时 间 来 确 定 前 道 工 序 的 完 工 时 间 得 到 各 工 序 的 加 工 时 间 2 基于 D B R模 型的生产 排程步骤 2 1 问 题 描 述 和 模 型 建 立 基 于 DB R 模 型 的 生 产 排 程 问 题 描 述 为 个 待 加 工 的 产 品要 在 台 设 备 上 加 工 具 体 定 义 如 下 给 定 非 约 束 资 源 设 备 集 F 表 示 第 台 设 备 j l 2 凡 约 束 工 序 的设 备 集 C C R j CC R CC R2 C C R C C R 表 示 约 束 工 序 的 第 台 设 备 1 2 n 产 品 加 工 集 P J 表 示 第 个 产 品 i 1 2 n 工 序 序 列 集 M1 3 M M 表 示 产 品 的 工 序 序 列 可 选 设 备 集 Mo 表 示 产 品 在 T 序 可 以 选 择 的设 备 对 于 约 束 工 序 的设 备 要 求 满 足 S i C C R S M c 2 式 中 5 是 Ti C 在 CRi 约 束 工 CR 序 第 J台设 备 上 第 i 个 产 品 的 开 始 加 工 时 间 是 在 约 束 工 序 第 J台 设 备 上 第 i 个 产 品 的 加 工 时 间 基 于 DB R 模 型 的 生 产 排 程 以 最 小 化 最 大 完 工 时 间 为 目标 即 rai n ma x S 其 中 是 产 品 在 第 道 工 序 上 的 加 T 时 间 S 是 产 品 在 第 道 工 序 上 的 开 始 加 工 时 间 为 建 立 作 业 车 间 排 程 问 题 的 数 学 模 型 假 设 下 列 条 件 成 立 8 3 1 当 同 一 工 序 有 2台 设 备 可 选 择 时 任 意 选 2 生 产 过 程 中 同 批 产 品不 拆 分 生 产 某 个 产 品 就 持 续 生 产 直 至 完 成 3 产 品 的 前 道 工 序 生 产 完 才 能 进 行 下 道 工 序 4 同 一 台 设 备 加 工 完 一 个 任 务 才 能 开 始 下 一 个 2 0 1 4 5 5 不 考 虑 加 工 过 程 中 的 换 线 时 间 基 于 DB R 模 型 的 生 产 排 程 问 题 可 表 示 为 在 满 足 如 上 条 件 的 情 况 下 求 解 最 小 化 最 大 完 丁 时 间 2 2排 程 计 算 2 2 1遗 传 算 法 流 程 遗 传 算 法 Ge n e t i c Al g o r i t h m G A 仿 效 生 物 界 中 的 物 竞 天 择 适 者 生 存 的 演 化 法 则 把 问 题 参 数 编 码 为 染 色 体 再 利 用 迭 代 的 方 式 进 行 选 择 交 叉 以 及 变 异 等 运 算 来 交 换 种 群 中 的 染 色 体 信 息 最 终 生 成 符 合 优 化 目 标的染色 体 遗 传 算 法 是 近 年 来 解 决 生 产 排 程 的 最 主 要 方 法 与 其它方 法相 Y 确定实际问题参数集 对参数进行编码 随 机 生 产 初 始 种群 P t 计算个体适应度值 评价种群 一 一 是否满 足 兰 N 二l删 遗传操 作 选择 交叉 变异 经过优化的参数值 种群 P t 一P 1 图 1遗传算法流程 比 遗 传 算 法 能 以较 大 概 率 找 到 全 局 最 优 解 非 常 适 合 于 大 规 模 并 行 分 布 处 理 其 流 程 如 图 1 9 所 示 2 2 2基 于 DB R模 型 的 生 产 排 程 问题 的 参 数 设 计 1 编 码 方 式 的 确 定 遗 传 算 法 在 求 解 问 题 之 前 必 须 把 解 空 间 的 解 数 据 表 示 成 遗 传 空 间 的染 色 体 或 个 体 本 文 采 用 双 层 编 码 方 式 第 一 层 是 基 于 工 序 的 编 码 以 确 定 工 序 加 工 的 先 后 顺 序 第 二 层 是 基 于 设 备 的 编 码 用 来 分 配 每 道 T 序 的加 工 设 备 通 过 这 两 层 编 码 得 到 一 个 可 行 解 以 图 2所 示 染 色 体 为 例 H o 前 六 位 为 基 于 工 序 的 编 码 尸l 为 产 品l的 第 一 道 T 序 尸 2 为 产 品 2 的 第 一 道 工 序 以 此 类 推 此 处 只 保 留 产 品 的 序 号 省 略 工 序 序 号 因 为 工 序 的 顺 序 不 能 被 改 变 后 六 位 为 基 于 机 器 的 编 码 代 表 机 器 的 选 择 选 择 此 台 机 器 为1 不 选 择 为 0 E 2 适 应 度 函数 遗 传 算 法 在 搜 索 过 程 中 使 用 适 应 度 值 表 示 个 体 的 优 劣 程 度 个 体 的适 应 度 越 高 被 选 择 的 概 率 越 高 反 之 越 低 本 文 染 色 体 的 适 应 度 函 数 为 目标 函 数 的 最 小 化 最 大 完 工 时 间 为 机械制造 5 2卷 第 5 9 7 期 F i t n e s s C f x 厂 C 3 式 中 F i t n e s s 为 适 应 度 函 数 C 为 一 个 适 当 的 较 大 的 数 F i t n e s s 越 大 该 染 色 体 越 好 3 选 择 算 子 从 当 前 种 群 中 按 一 定 概 率 选 择 出 优 良个 体 使 其 有 机 会 作 为 父 代 繁 衍 下 一 代 判 断 个 体 优 良 的 准 则 是 个 体 的 适 应 度 值 本 文 采 用 轮 盘 赌 选 择 方 法 此 方 法 根 据 每 个 染 色 体 适 应 度 值 的 比 例 来 确 定 该 染 色 体 的 选 择 概 率 产 生 一 个 随 机 数 落 入 轮 盘 的 哪 个 区 域 就 选 择 相 应 的 个 体 交 叉 适 应 度 值 高 的 染 色 体 被 选 入 下 一 代 的 概 率 高 较 易 继 承 较 好 的 染 色 体 l l I 4 交 叉 算 子 种 群 通 过 交 叉 操 作 获 得 新 染 色 体 从 而 推 动 整 个 种 群 进 化 本 文 对 于 工 序 和 机 器 分 别 采 用 选 用 单 点 交 叉 法 进 行 交 叉 运 算 即 在 染 色 体 中 随 机 产 生 一 个 交 叉 位 置 然 后 在 该 点 相 互 交 换 两 个 配 对 个 体 的 部 分 染 色 体 1 1 5 变 异 算 子 虽 然 种 群 发 生 变 异 的 可 能 性 比 较 小 但 也 是 产 生 新 物 种 的 一 个 不 可 忽 视 的 原 因 它 决 定 了 遗 传 算 法 的 局 部 搜 索 能 力 选 择 反 转 变 异 方 式 即 在 染 色 体 中 随 机 选 择 两 点 将 两 点 间 的 子 串 反 转 这 种 变 异 不 会 更 改 两 点 间 的组 合 次 序 两 点 间 的 内 部 长 度 不 会 改 变 只 会 改 变 两 点 与 外 邻 接 点 之 间 的 长 度 l l 6 约 束 条 件 的 处 理 为 达 到 约 束 资 源 上 设 备 的 加 工 时 间 不 间 断 性 采 用 罚 函 数 法 进 行 约 束 对 在 解 空 间 中无 对 应 可 行 解 的个 体 计 算 适 应 度 时 处 以 一 个 惩 罚 函数 从 而 降 低 个 体 适 应 度 使 该 个 体 被 遗 传 到 下 一 代 群 体 中 的 机 会 减 少 表 l 各产 品生产 工序及可 选加 工设备 2 3算 法 应 用 仿 真 及 试 验 结 果 某 食 品 生 产 企 业 生 产 模 式 为 库 存 式 生 产 根 据 式 1 确 定 生 产 中 的 约 束 资 源 也 称 作 产 能 限 制 资 源 CC R 约 束 工 序 的 设 备 集 C C R C C R1 C C R2 C C R3 非 约 束 资 源 设 备 集 F A1 A 2 l B 2 B3 Dl D2 El E F 2 产 品 加 工 集 P 2 P 4 P 7 P 8 工 序 序 列 集 A C C R B D EF 产 品 加 工 工 序 及 可 选 的 加 工 设 备 见 表 1 加 工 时 间 见 表 2 在MAT L AB 2 0 1 2 b环 境 中 对 本 文 探 讨 的 方 法 进 行 仿 真 实 验 实 验 计 算 机 配 置 C P U I n t e l C0R E i 5 3 3 1 7 U 1 7 Hz 内 存 4 GB 遗 传 算 法 参 数 设 置 种 群 规 模 4 0 最 大 迭 代 次 数 1 0 0 交 叉 概 率 0 7 5 变 异 概 率 0 3 2 3 1 原 排 程 方 式 仿 真 结 果 使 用 该 企 业 原 排 程 方 法 排 程 以 最 小 化 最 大 生 产 时 间 为 目标 将 个 待 加 工 产 品 排 到 台设 备 上 同 种 产 品 在 加 工 过 程 中 要 求 加 工 时 间 连 续 排 程 过 程 中 不 考 虑 系 统 约 束 资 源 的存 在 统 一 对 待 所 有 工 序 其 余 条 件 与 本 文 中所 选 用 的相 同 原 排 程 方 法 排 程 结 果 的 甘 特 图 如 图 3所 示 图 3中 横 轴 表 示 时 间 纵 轴 表 示 设 备 线 条 表 示 生 产 加 工 完 成 情 况 如 标 识 P 2 3落 在 日 纵 轴 上 代 表 产 品 的 第 三 道 加 工 工 序 在 机 器 上 完 成 线 条 长 度 表 示 加 工 时 间 线 条 第 一 道 工 序 的 最 早 加 工 时 间 至 最 后 一 道 工 序 的 最 迟 完 成 时 间 即 为 最 优 工 期 图 3最 优 工 期 为 5 4 4 mi n 2 3 2 基 于 D BR 模 型 排 程 仿 真 结 果 基 于 DB R 模 型 排 程 仿 真 结 果 的 甘 产 品 工序 Pl 只 只 P 8 A A 4 A4 z A A A A A A C C R1 C C R1 CC R1 C C R1 C C R1 C C R C C Rl C C R l GCR CCR2 C CR2 C CR2 CCR2 CCR2 CCR2 CCR2 CC R2 C C R 3 C C R 3 C C R 3 C C R 3 C C R C C R 3 C C R C C R3 B B B B 3 B 3 BlB 3 lB 3 占 B B1B 2 B 3 B1 3 D Dl Dl D2 D 2 E E E E E E E B E E F 表 2 单位产 品加工 时间 mi n 产品 工序 P 1 P 2 只 B 尸 6 P 1 A 3 6 3 6 3 6 3 6 2 4 2 4 2 4 2 4 CCR 1 0 0 8 0 1 0 o 8 0 1 2 0 9 0 1 2 0 9 0 B 8 0 8 0 8 0 8 0 8 0 8 0 8 0 8 0 D 9 0 6 0 9 0 6 0 l E 6 0 6 0 6 0 6 0 F 7 0 8 0 t 7 0 8 0 l 机械制造 5 2卷 第 5 9 7 期 特 图 如 图 4所 示 本 文 基 于 DBR模 型 进 行 排 程 根 据 式 2 需 保 证 图 中 C C R 工 序 的 设 备 加 工 时 间 不 间 断 根 据 上 述 甘 特 图 从 结 果 来 看 在 保 证 约 束 资 源 充 分 工 作 的 前 提 下 总 加 工 时 间 为 5 2 6 mi n 而 利 用 该 企 业 原 排 程 方 法 总 加 2 1 2 时 间 为 5 4 4 mi n 从 约 束 资 源 的 利 用 率 来 看 约 束 资 源 的 充 分 利 用 在 一 定 程 度 上 为 企 业 增 加 有 效 产 出 提 供 了 可 能 性 排 程 结 果 表 明 与 传 统 方 法 相 比 本 文 所 选 的 排 程 方 法 总 加 2 1 2 时 间 较 短 在 现 有 生 产 环 境 中 能 够 将 企 业 的 有 效 产 出 最 大 化 通 过 基 于 约 束 资 源 对 生 产 进 行 有 序 的 排 程 结 合 DB R 模 型 由 上 述 甘 特 图 可 知 加 工 起 始 时 间 将 此 时 间 减 去 缓 冲 区 域 长 度 以 及 前 道 工 序 的 加 工 时 间 可 以确 定 原 材 料 的 投 料 时 间 能 够 有 效 地 控 制 生 产 的有 序 进 行 2 0 1 4 5 圈l 3结论 本 文 针 对 库 存 式 生 产 企 业 生 产 排 程 问 题 通 过 对 比 MRPI I J I T和 T OC理 论 选 择 将 T OC理 论 作 为 解 决 排 程 问 题 的 理 论 依 据 通 过 DB R 模 型 的 导 入 结 合 多 层 编 码 的 遗 传 算 法 以 最 小 化 最 大 生 产 时 间 作 为 目 标 进 行 排 程 并 以 某 食 品 公 司 为 例 仿 真 结 果 表 明 采 用 本 文 方 法 在 保 证 约 束 资 源 不 停 工 的前 提 下 排 程 总 时 间 为 5 2 6 mi n 优 于 实 际 情 况 表 明 了 该 方 法 在 缩 短 总 加 工 时 间 以 及 约 束 资 源 的 利 用 率 上 具 有 可 行 性 对 优 化 排 程 具 有 积 极 作 用 参 考 文 献 1 龚华坪 基 于约束理论 的船舶敏捷制造企业生产运作与控 制研究 D 镇 江 江苏科技 大学 2 0 0 9 2 许 文昌 限制理论 与蚂蚁 演算法於 流程 型工厂排 程之研 究 以彩色滤光片厂为例 D1 台湾 元智 大学 2 0 0 7 3 高德拉特著 齐若兰译 目标 M 北京 电子工业 出版社 2 0 0 9 4 陈润泰 限制驱 导式排程方法在动态生产系统与 随机加工 时间环境 下的应用 D 台湾 南 台科技大学 2 0 0 7 3 吴鸿辉 李荣贵 限制驱导式现场排程 与管理技术 M 台 湾 全华科技图书股份有 限公 司 2 0 0 7 6 J r S J V S i m p s o n I I I W P C a r l s o n F o r m u l a t i o n a n d S o l ut i on o f t he Dr u m bu f f e r r o pe Co n s t r a i nt S c he d u l i n g P r o b l e m DB RC S P J I n t e r n a t i o n a l J o u r n a l o f P r o d u c t i o n Re s e a r c h 1 9 9 6 9 7 陈 国慧 基于约束理论 的航空复合材料生产计 划排 程系统 D 南京 南京航空航天大学 2 0 1 2