资源描述:
日_一 一 龌 煎 .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 维普资讯
展开阅读全文