柔性制造系统生产调度中的运筹学模型及方法
年 月
第 卷第 期
庆 大 学 学 报 地
。
柔性制造系统生产调度 中的
运筹学模型及方法 ‘
杨 丹
应 用数学 系
梁 锡 昌
传动 实验 室
胡 立 德 王 时 龙
机械工 程 一 系
摘 要 在讨论 柔性 制造 系统概 念 的墓础 上 , 提 出 了按 三 维体 系结构 描 述 生产调
度 问题 的概 念 建 立 了柔性制造 系统 生 产调 度 问题 的四 层 结构 模型 系统地分 析 了运 筹 学模
型 及方 法 在柔 性制造 系统运 行 管理 的静 态调度及 动 态调 度 各个 问题 中的应用 现 状 , 指 出 了
存在 的困难 最 后 简略地分 析 了人 工 智 能技 术和 人 工 神 经 元 网络方 法在 生产调 度 中应
用 的新 趋 势
关键词 运 筹学 柔性 制造 系统 生产规划
中国图 书资料分类 法分类号 仪 “
叹打 , 刀泊女刁 曰 石 扭 吐 祠 ,
馏 比 扭
姗 , 一 时 和从 , 比
, 已记么
曰 , 石 , 让 ‘
卯 , , 址
山 口 , 曰 一
牙
、 已沈 书 劝 七 比 扭
己卜 侣旨
二二
柔性 制造 系统 限石 碗 , 是 由 自动物 料运 贮 系统连接 的 一组
加 工 中心和 或 其它 生 产设 备组 成的 , 其生 产过 程 由计 算机进 行计 划 , 实施和 控 制的 中 、 小
批量 机械加工 系统 。 自世界上 第一 条柔性制造 系统于 年在 英 国 建立 后 , 从 七 十年 代 中 、
后 期 开 始 , 在 西 方 各 主要 工 业 国家 引起 了极大 的 重 视 , 并 得 到 了迅 速 的发 展 。 目前 , 它
, 收文 日期 一 一
重 庆 大 学 学 报 年
已成 为机 械 制 造业 中一 个 重要 研 究领域 。 柔 性 制 造 系统 及 其 所 应 用 的技术 同 以 前 的刚性 生
产 系统相 比较 , 在增 加设 备 利用率 , 减 少库 存 , 提 高 产 品质量 , 缩 短 制造 周期等方 面取 得 了 巨
大 的 效益 。
虽 有 很 多 优点 , 但 专 家 们指 出 的 优点 是 潜在 的 这 就 意 味着 , 只 有 简单地 将
先进 的设 备组 成 一 个新 的生产 线 , 即 只有硬 件 , 不能发 挥 的 生产效 益 。 而 只有 在 合理 地
设计 的基础 上 , 借 助 于 计算机 对 的生 产过 程进行 科学 地 规 划 和 管理 , 即必 须配 备
足软 件才能 使 的潜 在效 益得 以发挥 。 因此 , 生产调度 方 法 的研 究成 为 目前 领
域 中众 多学者 关注 的关 键 技术之一 。
运 筹学 的 理论 和 方 法 自本 世 纪 四 十年 代 产 生 以 来 , 一 直 是 人 们在 进行 决 策分 析 时所 依
据的强 有 力的科学 方法 之 一 。 在柔性 制造 系统 生 产计划和 调 度领域 中 , 也应 用 了众 多的运 筹
学调 度模 型 和 方 法 。 笔 者 在 提 出 生产 调 度 模 型 的基础 上 , 深 入 地 分 析 了柔性 制 造 系统
生产 调度 各领 域 中 所应 用 的运 筹学 模 型 和 方法 。
生产调度模型
的概 念
对 于 柔性 制造 系统 的 定义 , 目前 尚无统一 的描 述 提 出了关于 一种广 义
的 定 义 。 此外 , 还有 其它 一 些 关 于 的定 义 。 这 些 定 义 往 往强 调 某方 面 的特 征 我 们
认 为 一个 的定 义 应 包 含其在功能和 结 构上 的 全 部特 征 , 即
的结 构特 征 柔性 制造 系统 是 由多台数控加工 设 备 , 物料 自动运 储系统 及 刀
具 自动传输 系聋兔为主体 , 在 多级 计算 机 的 统 一 控制 和 管 理 下运 行 的 自动化机 械加工 系统 。
从 计 算 机 集 成 制 造 系统 司 , 的 观 点 看 , 它 是
路 一 , 关于 五 层结 构 中位 于第 三 层 的子 系统 。 的
功能特 征
主 要 针 对 中 、 小批 量 的零 件加 工 。 它 可 以 按 零 件 工 艺要 求 的顺 序进 行 随机地 加
工
它具有 加工 时间 , 加工零 件 , 加工工 艺 , 加 工 批 量 , 运 行操 作 , 系统容 错 和 系统扩 充等
方 面 的柔性
它具 有 开 放 式 的 系统 结构 , 既 可以 将 作 为一 个 独立 的 系统运 行 , 也 可 以 将 其放
在 的集成 环 境中 , 同 的 , 以 及 子 系统 等集 成 。
飞 柔性制造 系统生产调 度 的三维体 系结构
在结构和 功 能 方 面 的特 征 , 的运行 方 式 同传统 刚性 自动化 系统 之 间有 本质 区
别 要使 能 充分体 现 其柔性 等特 点 , 必 须 在 的运 行 和 生产 调度方 面 引入 新 的方 法
和手 段 , 使 的 运 行 能 达 到 设 计的 目标 。 由于 运 行管理 和 生产 调度 问题的 复 杂
川 一 ‘声 一
在 解决 该 问 题 时通 常 采 用分 解协 调 控 制 咖卿 一 的 思 想 。
的运 行管 理 和 生产 调度 问题 可 以 由图 所示 的三 维体 系结构 来 刻划其三 方 面
,
挽、 。,
认川征一们河持?称的叼
图 中 调 度的 传 统 方 法 是 指 基 于 运 筹 学 技 术 的方 法 , 如 数学 规 划 , 动 态 规 划 , 各 种
启发 式算 法 等 调度的现 代方 法 是 基 于 人 工 智 能技 术 、 离 散 事件仿 真 、 离散 事件 动态 系
第 卷 第 期 杨 丹 等 柔性例造 系统 生产调度 中的运 络 学模型及 方 法
统理 论 以 及 人 工 神经 元 网 络理论等 , 并 包括这 些方法 同运 筹学 综 合应 用的技术 。
行度度划执调调规
方法 维
资源维
图 材 生产调度间题 的三维体系结构
综 合图 中时间维 和资源维 的各 因素 , 我 们得到 图 所示 的 生产调度分层递 阶控制
模型 中 。 在该 四 层模型 , 第 一 、 二 层的 运 行是 离线方式 , 余下 两层 以在线方式运行
图 中第一层的 主要功 能是 接受上级 系统 或 由人一机界 面 输 入 的柔性制造系统生 产
任务 , 通 过 系统运行仿真等方 法 , 在 系统 资源 所承受的 加工 容量 内 , 对 日从 生产
任务进行 可行性分析 , 制定 班次 作业 计划 。 同时 , 根 据生产 任务及 班次作业计划的历史数据 ,
对班次作业计 划做 自适 应 修正 。
第一层
州 运行规 划 制造
订 货需求分析
班次作业计 划制造
班次计 划 自适应调整
静 态
衡平
组荷序分负排化工态优加静件床件工机工第二 层
第三 层
动态调度
尸 中进入机 床的工 件选取
多个工 件流动管理
第四 层 刀 具管理
管理
托盘 、 卡具
人 力资源管理
程序管理
理 机器 人控 命
图 生产调度四 层模型
第二 层 是根 据第一 层输 入 的班 次 作业 计划 进行 生 产 运行 的静 态调度 详 细功能
工 重 庆 大 学 学 报 年
见
第三层 是 祠阴 生产管理 的动态调度 见 。
第四 层 是 讥 系统 资源管理 层 , 该 层 中的各资源管理 器根 据上 层 下 达 的指令调 度各 种
资源 。
在上述 尸 四 层递 阶调度模型 中 , 第二 、 三 层是 起决定作用的 。 本文 以 下部分关 于
生产调度 中模型和 方 法 的讨论 主要 以 二 、 三 层为 对象
运筹学模型和方法在 静态调度及动态调度 中的应 用
·
静 态调度 中的运 筹学模型 和方法
么 工 件 的优化 分 组 和 机 床 的负荷平 衡
工件 优化分 组 是 为 了减少工 件在加 工 过 程 中 的额 外 开 销 。 机 床 负荷 平 衡 是 为 了提 高机
床的平均利 用率 工件 优化分组追求 的优化 目标 是 极 大化 机 床的平均 利 用 率 , 或 极 小化 优
化分 组 后得 到 的 工件 组 数 。 极 小化 工 件 组 数 的 优 化 目标 等价 于极 小 化 运 行 中刀 具 、 托
盘 和卡 具交换 次数 直 观地看 , 这是 由于机床 刀 具 箱容量 的限 制 , 机床 不 能 一次将 加工所 有
工 件所 需 的 刀 具 放 入 刀 具 箱 , 只能 保 证 在 加 工 同 一分 组 内的 工件 时 尽 可 能 不 换 刀 , 当
曰 由一 组 工件换 到 另一 组 工件进 行 加工 时 , 常常伴 随 着较 大 批 量 地 更 换 刀 具 , 托 盘 和 卡
具 每次 更换 刀 具等时 , 系统有 一个 重 新 装载 、 启动 过程 。 最优 生 产 调 度中的 工 件
分组应 使得 装载和 启动次 数降到 最低 限度 。 过 多的 装载 、 启动过 程 就 是 运 行 中的
额 外开 销 的 装 载 、 启动过 程可分 解成 机 床及 刀 具 等 的装 载 、 启 动两 部 份 ‘ “ 门 口
孤丈冶 , 因此 , 一 些讨 论 调 度的 文 章 常将工 件 的优 化分 组 同机 床 或 刀 具 装载 及 系统
启 动间 题 一 并 讨 论 · 〕。 设 在 一个 班 次 计 划 中有 ‘ ‘ , , ? , 次 刀 具 交换 或 次 系
统 白动 、, 则 以 刀 具交换 次 数最 小 为优 化 目标的 数学 规划 模 型 可表达 为
, 云 ‘ ·
· , , ,
其 中 如存在第 次 系统 启动 , 或 不存在 第 ‘次 系统 启动
‘一 每次 换 刀 所需 时间
艺一 第 ‘次 系统 启 动完成 所需 时 间
一 中其它决 策变量
一 之 约 束集 , 通常 包括 机 床刀 具箱 容量限制 , 刀 具 寿 命约 束 , 工 件正 常
完成 时 间限制 等 。
对 于工 件 优化分 组 及其等 价 问题 及 机 床 负荷平 衡 问题 , 目前 已 有 一 些 研 究报首 。
达 在 〔 中报 道 了 他 在 年 发表 的 求解 机 床装 载 问 题的结 果 。 建
立 了同 时考虑 机床 负荷 平衡 的装 载 模 型 。 闭 报 道 了应 用非 线性 混 合整 数规 划 方
法求解机床分组 和 加载 问题的 数学 模型和 方 法 。 的 工作 , 引 出 随 后 一 系列应 用 数
学 规 划 方法 求 解工 件优 化 分 组 及 其等价 问题 的 研 究 。 归 川 应 用 线 性 整 数规 划 方
法建立 了工件分 组 和刀 具 装载 问题 的数学 模 型 , 并 设 计 了相应 的启发式 算法 求解 。
〔‘」应 用 非 线性 整 数规 划 方 法 研 究机 床装 载 、 负 荷平 衡 间题 , 但 他 应 用 了分 枝定 界法 求 解 。
第 卷 第 期 杨 丹 等 柔性制造 系统 生产调 度 中的运 筹 学模型及 方 法
〕通 过 数值仿 真 方法研 究 了在制 品数量 , 缓 冲站容量对 机 床 负荷 平衡 问题 的影
响 趁 等 应 用 数学规 划建立 了机 床装 载和刀 具配置 的数学 模 型 , 以 其在考虑 加 工
工件 刀 具需求约 束的同时 , 确 定工件在机 床间的流 向 , 他应 用 了 。 松弛法求解 。
等 代表了应 用 数学规划方法求解工件分组 , 刀 具分配问题 的最新研究成 果之一
在应用运筹 学 技术研究 工件分组及 机床负荷平 衡的工 作 中 , 数 学模型的构造颇为
相似 , 但不 同的研 究者应 用 了不 同的方法 求解所 建立 的模 型 上述研究成 果 并不 十分理 想 ,
这 是 由两方 面 原 因导致 的 一方面 由于 生 产调度 问题 的复杂性 , 使得 根据 实际 问题 构
造的 数学模型 规模过大 , 引起 了“ 维 数灾难 ” 另一方面 , 在 运 筹学 中的组 合优化领域 中 , 尚缺
乏 求 解 对 于 大规 模 问题 的有 效方法 , 建 立的 工件 分 组及机 床 负荷 分 配 模 型 , 大 都难 以
使 用现有的有效算法 在 合理的 时间 内求得 问题 的 最优 解 。 据 等分 析 , 当应 用混 合整
数规 划 对 于 一个有 台机 床 , 把 刀 具 , 个 以 上 加工 工 件 , 道 工序的 认 建立工 件分
组 和 刀 具 配置 的数学 模 型 时 , 其变量数 为 , 个 , 约 束 条件数 目为 , 个 。 如此 规 模
的 问题 , 其求解 的复杂性 是很 高的
尽管如此 , 应用运 筹学 方法研究 工件优化分 组 、 机床负荷平衡 问题仍有重 要意 义
因 为接近 于 实际 问题 的运 筹学 模型深 化了对 所解 决 问题 的认识 , 研究 者 由此 可 以 设计有 效
的 启发式算法 , 以求 得问题 的近似最 优解 , 作为参 考
么 工 件 静 态排 序
静 态调 度 中的 工 件排 序 是 指 当工件最 优分 组 以 后 , 根据 工 件 交 货期 先后次 序 及
其 它 条 件 , 排 定 工 件 进 入 的 先 后 顺 序 。 故 也 称 之 为 进 入 点 排 序
现 ,
受 工件 加工 工艺 的限 制 , 的生 产方式分 为流 水线 一 叩 和 混 流方式 扣 一 叩
两 类 , 前者是指 和工 件的加工工序是相 同的 , 因而 工件 在系统 中有 相 同的流动路 径 , 在
混 流方式中各工 件 的流动路径 不同
在运 筹学 领域 中 , 对应 于 尸 流 水线 和 混 流 方式 有 一 叩 调度 和 一 叩 调 度 两
类 组 合优化 问题 。 早 在 柔性 制 造 系统 出现 之 前 , 一 叩 和 卜 叩 调 度 问题 就 成 为运 筹
学 工作者的研究课题 , 因 为它代表 了极 广泛 的一 类组 合优化 问题川 但这 些 研 究 偏重 于 寻 找
有 效的算法 并研 究算法的 复杂性 , 收 敛性 等 〔 」 比 帅 〕系统地 总结 了机 床调度 问题在
算法效率方面 的研 究工作 , 并指 出对于 和 卿 在 年所 建立 的 台机 床 , 个
工 件混 流生产方式模型 一直没 能圆满解决 。 由此 可 见该 问题 的难度 随着 的发 展 , 一些
应 用 于 祠讨 的工 件排 序模 型和 方 法相继 出现 。 这 些 方 法 虽然 没有在 理论 上求得 最 优解 , 却
着 眼于减 小 问题的规 模 , 追 求算法 的效 率 如 砂 。〕在 应 用整 数规 划 方 法 求解工 件排
序 问题 时 , 将同 一分组 中的工件看成 了一个 “ 虚拟 ”的工 件 , 这样有效地 降低 了 问题 的规模
到 现 在 为止 , 几 乎在运 筹学 中所 有能 用 于求解组 合优化 问题 的方法 都被用 于求解 一
和 卜 叩 调度 问题 , 表 中列 出部分结 果
迄 今为 止 应 用 于 实际工 程 的方 法 , 大都 是 启发 式 算法 。 如我 国 第一 条 国 产 柔性 制造 线
一 一 亦 采用 启发式算法 对工件静态排序 。
动态调度 中的运 筹学模型和方法
么 工 件 的动 态调 度
工 件的 动态调度 是 指在 运行过 程 中 , 根 据 系统 资源的实际状 态 , 实时动态地
重 灾 大 学 学 报 年
决定 工件 在 内的 流 动 , 它包 括
· 决 定机 床加 工工 件 的 先 后顺 序 动 态排 序或
· 在工 艺条 件允 许 的情 况 下 , 决 定 工件在 系统 内的流 动路线 。
由 节 分析 可 知 , 一 叩 和 卜 叩 调度 间题 的解 能相应 地 确定工 件 的动 态调
度策 略 。 由于工 件 动态 排 序 , 实时性 要 求很高 , 故较 为成 功 的 动 态 排序算法 大都是 基 于 规 则
的启 发式算 法 “ 〕, 或 者 是 启发式 算法 同其 他方 法 例 如 川 的 结 合 。 对 于 启发 式 算 法 的
设计 既可采用 建立 模 型 的 方法 , 也 可用数值仿 真来试验 。
表 一 卜 , 一 的部 分 成 果
方 法 作 者及发表 时 间
整数或混 合整 数规划
图论 及混 合方 法
排队论
动态 规划
对 策论
启发 式算法
人工神经 元 网络
比 , 等
远 , 油
,
和
脚
即 , 巨忱沁 切山 山
, 记眼
张长 水 一
自动 导 引小 车 的 调 度
在有 多 台 的 中 , 的 调度 包括
· 小车对工 件的 优 先服 务问 题
· 需运 送 工 件对 小 车选 取问题
· 小车在 中运 行 的 交通 管理
· 小车在 运 行 中最短 路 径选 取
年 以 前 , 关 于 调度 的文 章很 少 川 , ’ 〔‘ ”采用 图 论模 型 研 究 了有
。 台加 工 中心 , 台 的 中 , 最 优 任务 分 配 问题 , 问题 求解采 用 了 人 工 智能 中
状 态 空 间搜索 方 法 , 即 ’ 算法 比腼 ‘’ 建立 了开 环 排 队网 络模型
研 究包 括 在 内的物 料 传送 系统 的特性 。
〔“ 〕研 究 了小车 交通 管理 问题 。 此 外还 有用 仿真 方 法 〔, ‘ 〕研 究 调度 问题 的
报道 。
从 运 筹学 的 角 度 看 , 调 度 问 题 属 组 合优 化 问 题 。 对 于 有 个 , 台机 床 的
, 调度 算法 的 复杂性 比组 合优化 领 域 中著 名的 多 个旅行 推销 员问 题
山 一 的 复杂性 还 高 , 而 尚属难 以求 解 的 完 备问 题 。
结 论
本文 研究 了运 筹学 模 型 和 方法和 在 静态 调 度 和 动态 调度 中的应 用现状 。 从上 述 结
果 可 以 看 到
生 产调 度 领 域 中面 对 的 问 题 大 都 属 于 组 合优 化 领 域 里 被 称 为 一 完 备类 问
题 。 对 于 该 类 问题 , 目前在 数学 上 尚无 有 效 解 法 。 因 而 调 度 方 法 的研 究应 用 集 中在 寻
第 卷第 期 杨 丹 等 柔性 制造 系 统 生产调度 中的运 筹 学模 型及 方 法
找 减 小问题规模 为 目标 , 并 能求到 问题 近似最 优解的新模型 和 方法 。
基 于组 合优化领 域 研 究 现状 据 加 等 称 要 解决 一 完 备类 问题 , 尚
需 几 代数学 家的 努 力 , 人 们开 始应 用 除 运 筹 学 方 法 以 外 的 其 他 方 法 , 如 技 术 等 , 研 究
调度 问 题 , 并取 得 了一 些 成果 , 技术 对 于 解决 不 存在 解析模 型 , 或虽 有 解析 模型 , 但
解析 解的求取有 困难的问题 , 能 有 效地 利用 人 的知识 。 但据 分 析 , , 技术在 加
中的应用并 不十分 成功 , 根 本原 因在于 领域 中 尚缺 乏解决 间题 的有 效 工 具 , 如状态 空 间
搜索方法 。
除 技 术 以 外 , 近 来也 开 始 有 用 人 工 神 经 网络 等 方 法 解 决 一 调 度 问题 的报
道 〕 这 些研 究 尚属理 论探 索 阶段 。
组 将离散事 件 动态 系统 以 , 理 论 应 用于 生产
调 度 问题是 国 内外 领 域 包 括 调度 问题 理 论研 究 的 热 点 , 南开 大学 等广泛开 展
了 应用 研 究 , 这 为 解决 调度 问题 开拓 了新路 。
此外 , 我 们认 为 , 有机地综 合应 用各种方 法 , 是从工 程 角 度 解决 生 产 调度 问题的
重要 途径 。
参 考 文 献
加 详 司 火泊 吹 创卫 叮始 , 沐 盯
,
咫 。四 巨 址 她石 阵巾 名 闭 枷 劝 吐 咖 加
川史化 比 咫 伪 介 份 一石 侧池 ” 妞叫 叩 , 比 压 ‘饱
如 , 。 叻 , 比 山 , 扭 , 七 往山 ,
目 砒吮 】 如 七 如 ” 难爬 ,
氏 , ,
加 加 】 如 习 加 , 爬 ,
即 段 , ,
比 户 石 目 坦 比 名 ‘
石 活 如 扭 , , 犯 书刁 说 幻 湘 详
如 , 眯 , 血 , , 七姆 沁 倪 妇 ,
,
」 劝 卜一 她 一 , 亡 , 地
七 , , ,
改以 , 治七 吠 喇 如 目 幻 , 纽以 你 , ,
‘ , 。 找 川 站‘ 仃以 就 雌 , , , 一
场 出 阵 , ,
价 帕 目 中留叼睡 】 户 , 钧 耸加日 晚如 , ,
水由 司 劝 吐 仁 , · 。 饮 〕“ 。 。。
, ,
决 加 名 ” 一 , 。
侧甩 , 名 ,
记 曰 一如 伪 匕 卿 比 , 伪 ” ·
重 庆 大 学 学 报 年
吸曰,山且‘月
我 吮 沈 ,
张长 水等 用 神经 网络方法求 卜劝 。 调度间题 , 年中国神经网络学 术大会
川 目 , 一 如 时 山阵忱加 押 叮坦 , , ,
城 叮以水 介 侧目一 一 廿 石心 一 加 场
沁川 愧 地 , 助 伪 幻 吐 ” 已 均 详 ‘
即垃之如 , 奴一 乙 爬沈 因的 , 七 切 山 , 肠山 ,
堪 自 脸 石 ,
知 如 , ,
加加 」 出 即 闭 恤 如 , ,
比 川 诩 访 比 司 , 至 , ,
匕 吐 侧泊 咖 , 化 , ,
订 习 名 山 份 , 加 , 切 一 叱 , ,
公,且
柔性制造系统生产调度中的运筹学模型及方法.pdf
