先进制造系统运行控制理论中调度问题综述.pdf

日_一 一 龌 煎 ．1 口 专题 综述 目 文章编号 1 0 0 3 ． 0 7 9 4 2 0 0 2 0 6 - 0 iO 1 4 2 先进制造系统运行控制理论中调度问题综述 王勇‘ ，马承翰 。马光锋‘ 1 ． 辽宁工程技术大学 机械工程学院 ．辽宁 阜新 1 2 3 4 30 ；2 ． 阜新市煤气公 司，辽宁 阜新 I O G O 摘要 综述了先进制造 系统运行控制理论 中调度问题的研究进展情况 ， 指出其研 究思路 、 方 法与发展方向。 关键词 调度 问题 ；调度方法；发展方向 中图号 T B 4 9 ；F 2 7 3 文献标识码 A 1 先进制造系统及其运行调度问题概述 先进制造 系统， 通常认为是以先进制造技术支 持企业的生产经营活动、 以先进制造技术的哲理和 思想组织企业运行 的由人员 、 组 织、 技术 、 机 器等要 素组成的有机系统⋯。柔性制造系统 F M S 是它的 典型代表模式， 它的核心在于对柔性好 、 自动化程度 高的设备进行柔性的运行控制。运行控制的优劣是 一 个 F M S设计能否成功的重要 因素 ， 其主要 内容就 是对有限资源的调度以及其信息的电子化。调度问 题可以说是生产管理的核心问题 ， 调度的成功与否 ， 对保证生产 目标的最佳实现 、 对在制品库存 、 交货期 限满意率、 缩短供 贷周期、 提高生产率都有重要作 用， 特别还关系到先进 制造系统大量投资的收益 问 题 2 调度问题的基本分类 调度问题按生产方式 的类型分为“ 开环车 间型 o p e n s h o p ” 和“ 闭环车 间型 c l o s e d s h o 口 ” J ， 前者 面对顾客， 后者面对库存 ； 而开环下 J o b ． S h o p 任务 作业 和 F l o w - S h o p 流水作业 是最重要也是 目前研 究较多的两类基本调度问题 3。 1 9 5 7年， J a c k s o n把调度问题分为静态和动态两 种 。静态调度基于以下的假设 1 待加工工件集 合确定 ； 2 加工时间确定 ， 且作计划时全部待加工 工件 已到位 ； 3 用到的机器可以连续运转。也就是 说 ， 静态调度要求利用整个生产系统的全部信息 ． 是 信息完全的调度。Y a n g等人 系统地总结 了静态调 度的发展历程及具体方法。动态调度则是信息不完 全的一类调度⋯， 它的特点 ①能在线产生实时调 度； ②对随机扰动能在线识别 ， 并快速重新调度。实 际生产中， 工件的到达和机器故障的发生常是随机 的， 生产系统的各种信息也不可能完全获得 ． 所以动 态调度是我们追求的 目标 ， 但 由于计算 速度等条件 的限制 ， 当时还是以静态调度为主。近十几年来 ， 随 着计算机技术的飞速发展， 专家系统 、 人工智能技术 A I 、 人工神经网络 A N N 、 系统仿真技术的研究 B 益高涨 ， 也为动态调度理论 的研究与应用开辟 了新 的思路 3 解决调度问题的方法综述 调度问题的研究思路如图 1 所示。 垫 堕 图 1 调度 问题 的研究思路 Fi g ． 1 P r t l,c e d u o f嘲 d 唱 t o 叫 I l g 从图 I中可 以看 出， 调度问题的研究是一个闭 环的、 不断反复优化 的过程 ； 建模与算法研究是核 心。模型的结构、 输入与输 出完全由实例和决策者 决定 ， 模拟仿真可以利用 c语 言等计算机编程语 言 实现 ， 而研究算法则是相对独立于实例的纯数学的 优化问题 ， 也是我们研究的重点。 按照方法产生的时间， 大体上分为传统与现代 智能两类。传统的调度方法有 1 优化方法， 包括数学规划 动态规划、 混合整 数线性规划等 、 分支定界法 、 消去法等， 它们基于某 些假设 ， 并能产生一个较优的调度方案 2 启发式法， 它针对调度问题常为 N P问题 的 特性 ， 不要求在多项式时间内求得最优解， 而是在计 算时间和调度效果之间折 中， 以最小计算量来得到 近优解。因此它虽然快 ， 但 对整体性能缺乏有效 的 把握与预见能力 ， 实践中需要与其他方法结合使用； 董明将启发式法与 P N相结合 6， 用来调度 F M S取 得了较满意的结论， 韦有双等总结 了启发示算法的 研究情况 ， 还提出了一种改进方案。 3 仿真法通过对实际系统建模 ， 直接试用各种 调度方案， 避开了理论研究的困难 ， 但它事先的假设 多， 且依靠于如随机分布等模型的选择 ， 使结论常因 模型而异。佩特里网 P e t r i №【 s 是在逻辑屡次上对 离散事件动态 系统进行建摸和分析的主要方法之 一 ，它以图形形式研究系统组织结构和动态特性， 尤 其适合异步并发系统的建模与分析 ， 十几年来． 用 P N来研究 F M S一直是先进制造系统运行控制理论 的热点之一 1 , 2 。 现代智能方法有 1 专家系统 E S ， 将领域与现场知识集合成知 识库 ， 然后按现场实际情况从库中产生调度方案． 国 外在这方面的研究 8 o年代就已经开始， 如 R o b e r r 等 维普资讯 2 煤 矿 机 械 2 0 0 2 年第 6期 x E 5 】 。 2 人工神经网络 A N N 用于解决调度 问题有 十几年的历史 ， 主要在 2个方面 1 将调度问题看 成一类组台优化问题 ， 并利用其并行处理能力来降 低计算复杂性 ； 2 利用其学习和适应能力将它用于 调度知识的获取 ， 以构造调度模型。使用最多 的是 反 向传播 B P 网络。 3 智能搜索 ， 诸如遗传算法 E ； A 、 模 拟退火算 法 s A 、 禁忌搜索算法 S A 、 蚁群 算法等 ， 其 中遗 传算法用得较多， 它的优势是可从一个调度随机跳到 另一个， 避免陷入局部最优解 ． 且计算速度快， 易于同 其他算法结合。模拟退火算法是在物理学中“ 退火原 理” 思想的基础上形成的， 将寻优过程与金属退火时 分子能量趋于最小相类 比， 是能在概率意义下收敛到 全局最优解的一种随机优化方法 ， 在避免陷人局部最 优解的能力上几乎是 目前为止最佳的 一 。 另外 ， 起源于 6 o年代 的模糊理论， 可用来解决 一 些不确定的或用精确的数学方法无法表达的问题 的求解 ， 对研究对象系统 中各种变量与参数的大量 模糊状态， 适于用模糊理论进行优化、 分析， 这也是 对系统由传统的确定性分析 向更加科学的非确定性 分析发展的重要方向。 启发式方法计算量小 、 得到次优解的速度快； 仿 真法使用普遍、 效果直观． 虽然它们属于传统方法 ， 但在多数情况下 ， 仍是好 的调度方法 ； 现代智能方法 也有其不足 ， 专家系统在知识的获取上难度大 ， 扩展 性差， 当要解决的问题偏离专家领域较大时， 系统性 能下降很快 ； 遗传算法的适应函数难取 ， 有时不能满 足被控系统对实时性与效率的要求 ； 人工神经网络 所需的训练时间长 ， 对结构缺乏解释能力， 针对具体 问题时不易确定最合适的网络类型 、 结构与参数。 4 调度问题解决方法的研究热点与发展方向 调度 问题是 制造 系统运行控制理论 的重要内 容， 而运行控制的能力叉决定着现代先进制造系统 自身发展的速度。正是 由于调度 问题的重要性， 人 们从来没有放弃过对它的研究。 专家系统、 人工智 能技术、 神经 网络 、 智能搜索 算法等本质上就是最优化技术 ， 广泛用于以控制系 统为代表的各个科研领域， 而制造系统的运行调度 历来是它们典型的研究课题 ． 且这个问题早 已被证 明是 N P难题 ， 更引起国 内外众多学 者的注意。 由 于优化问题的无止境性 ， 目前的所有方法都只能说 是在一定范围内、 一定条件下是最优 的， 确切地说是 次优的， 所以， 挖掘现有方法的不足、 使各种方法互 相结台取长补短， 以及探索新方法和算法 。 已成为理 论研究 的两大 热点， 特 别是将 它们与实 际 问题 如 J o b ． s } 1 0 p调度问题结合起来 研究， 更具有针对性和 实际价值。部分国内外专家学者研究取得成果 ， 如 S ． H a 等人用模 糊逻 辑来确定遗传算法 中交叉 与 变异概率 ， 使 G A更符台 自然界的生物进化规律 ， 性 能得到了提升； S u 等人为了解决工程中参数设计优 化的难题， 使用神经网络确定 目标函数 ， 用 s A搜索 最优解 ， 通过 N N与 s A的结合取得 了较好的效果 ； 值得一提的是台湾学者 1 “a i ． Y u eWa n g等人 ． 1 9 9 9年 改进 了模拟退火算法的搜索机制 ， 通过实例证明 丁 效果， 但仅 1 a 后 ， 他们叉分析了它的不足， 将 S A再 次改进 ， 从而使 J o b - s h o p调度 中求总拖期最小的问 题得到了更好的解决。 优化问题是理论研究中的难题 ， 它的研究必须 是在综合系统科学、 信息论 、 控制论、 运筹学特别是 数学与计算机技术等多 门学科 的基础之上 ． 而且优 化的本质就是在不断发现 自身缺陷的同时不断改进 的过程 到目前为止， 依靠计算机技术 ． 将现有的各 种算法组台应用 ， 再利用编程进行仿真验证 ． 是解决 制造系统中各种条件下调度 的主要思路 。 参考文献 I ] 许怡如． 等 ． 先进缶 4 遗系统规划设计[ M ] 北京 兵器工业H j 船 杜 ． 2 O O O ． [ 2 ] 揶火钟， 赵千川 ． 离散事件动态系统[ M ] 北京 清华太芈出版 社 、 2 0 0 1 ． [ 3 ] 李秀， 等 ． 用遗传算法解决生产线调度 J s I I叩 问题[ J ] ． 系统仿 真学报， 2 0 0 1 ． 6 1 7 3 27 3 9 [ 4 ] 饯晓龙． 等动态调嚏的研究 法综述[ J ] ． 控制与 策， 2 0 O r ， 2 [ 5 ] m k【 F ． R e y a n ] d l J a m e s A M c M a ] a F M S S c h u ] i n g m⋯ E x s 帅 [ c ] ． 1 k C A S A S M E n u M m u f m r i n g s 。 8 7 C Ⅲ1 咖e ． Oc t dr 1 9 8 “／ ． ] 董明 ． 基于时间P e a l 陶和启发示控常的F M S 调度方法[ J ] ． 模式 识别与』 、 工智能 ， 1 9 9 7 2 作者简介王 勇 1 9 7 7一 ． 江 j ’ 赫』 、 、 辽宁工程挂求大学机械 学 院礤士研究生． 主要研究方向为制造系统扰化 、 工业工程。 收藕 日期 2 0 0 2 - 0 3 ． 0 4 S u r v e y t o s c h e d u l i n g p r o b l e m o f a d v a n c e d ma n u f a c t u r i n g r unm ng s y s t e m s WANG Yo n g t ， MA 0 m h ． 1 L 4 ． Gu m f mg 。 1 ． M e c h a n i c a l S c h o o l o f L i a o n l n g U n i v e r s i t y o f E n g l n e e d n g a n d％c h n d o - F u x l n 1 2 3 1 3 0 0 - C l fi n a ； 2 F u x i n G a s S e x d e e C o m p ff- F u x i n 1 2 3 0 0 0 C h i n a Ab s t r a c t T h i s p a p e r mm。 d u p t h e r e o e n Ⅱ y r e s e a r c h o f s c h e d u l i n g p rob l e m f o r run n i n g c o n t r o l i n a d v a n c e d ma n u f a c t u r - i n g s y s t e ms ， p o i n t e d o u t t h e s t u a y p r o c e d u r e ， me t h o d s a n d th e d e v e l o p me n t o r i e n t a t i o n． Ke y w o r d s s c h e d u l i n g p rob l e m； s c h e d u l i n g me t h o d s ； d e v e l o p me n t o r i e n t a t i o n 维普资讯