（机械制造及其自动化专业论文）智能车间作业调度问题研究.pdf

摘要 车间调度问题是现代制造业中共存的问题。随着制造业的发展，出现了大量复杂 的制造系统，如柔性制造系统、计算机集成制造系统，为车间调度问题的研究增加新 的难度和要求，迫切需要研究与之相适应的车间调度方法，因此开展这方面的研究具 有重要的理论与应用意义，并将产生巨大的经济与社会效益。近年来，智能优化理论 与技术发展很快，已经广泛地应用于科学与技术的许多领域，为解决较大规模的优化 问题提供了新的途径。本文着重研究了基于蚁群算法和基于人工神经网络方法的车日j 调度理论与技术，开发了车间调度优化系统。本文主要研究内容如下： 首先概述了车间调度问题的研究历程，总结了车间调度问题的研究现状，指出了 车问调度问题研究存在的问题以及发展趋势，介绍了车间调度问题的描述和分类，给 出了车间调度问题的数学模型、图模型、结果表示方法、调度性能评价指标和一些常 用的启发式规则。 以t s p 问题为例介绍了蚁群算法的基本原理及其理论模型，定义了其基于弧模 式的信息素分布的解构造图。然后基于j o bs h o p 调度问题，将j o bs h o p 调度问题构 造为类似于j s s p 析取图的图模型，在文献瞵0 j 提出的改进蚁群算法的基础上，本文在 信息素更新规则上加以改进，利用信息素局部更新策略和全局更新策略来进行信息素 的更新，提出了一种改进混合蚁群算法求解j o bs h o p 问题，并且用b e n c h m a r k s 问题 做了实例的仿真，实验结果证明了改进算法的可行性和有效性。 提出了一种新的约束满足自适应神经网络模型。针对车间调度问题的特点，提出 了强约束和弱约束的概念，针对不同的约束类型采用不同的约束满足机制。网络在运 行过程中，针对问题的不同误差来源，自适应调节神经元连接权值，逐步消除出问题 的约束冲突带来的网络误差。为了改进约束满足自适应神经网络求解车问调度问题的 性能，提出了一些启发式算法，这些启发式算法可以分别或者组合起来嵌入到神经网 络中，神经网络在不同阶段可有选择地使用。最后，基于b e n c h m a r k s 问题进行了实 验仿真，实验结果表明，这种神经网络可以很快地找到较优解。 最后介绍了本文所开发的车间调度系统。在前面章节研究的基础上，酋先介绍了 车间调度实验系统的软件结构和设计思想，然后利用v i s u a lc + + 6 0 开发工具和s q l s e r v e r2 0 0 0 等编程工具，基于组件技术和多线程技术，分析和设计了车白j 调度系统。 关键词：车间调度蚁群算法自适应神经网络 a b s t r a c t j o b s h o ps c h e d u l i n gp r o b l e m ( j s s p ) i st h ec o e x i s t i n gp r o b l e m i nm o d e m m a n u f a c t u r i n gi n d u s t r y w i t ht h ed e v e l o p m e n to fm a n u f a c t u r i n gi n d u s t r y ，m a n yc o m p l i c a t e d m a n u f a c t u r i n gs y s t e m ss u c ha sf l e x i b l em a n u f a c t u r i n gs y s t e m ( f m s ) a n dc o m p u t ei n t e g r a t e d m a n u f a c t u r i n gs y s t e m ( c i m s ) a p p e a r , w h i c ha d dt ot h ed i f f i c u l t i e sa n dt h ed e m a n d so ft h e r e s e a r c ho nj s s p , a n dt h ec o r r e s p o n d i n gm e t h o d st os o l v ej s s pa r eu r g e n t l yn e e d e dt o r e s e a r c hf u n h e r c o n s e q u e n t l y , t h er e s e a r c hi n t oj s s pi so fg r e a ts i g n i f i c a n c eo ft h e o r ya n d a p p l i c a t i o n ，a n dw i l la c h i e v eg r e a te c o n o m i ca n ds o c i a lp r o f i t s i nr e c e n ty e a r s ，i n t e l l i g e n t o p t i m i z a t i o na l g o r i t h m sh a v eb e e nd e v e l o p e dr a p i d l ya n du s e de x t e n s i v e l yi nm a n yb r a n c h e s o fs c i e n c ea n dt e c h n o l o g y , t h u st h e s ea l g o r i t h m so f f e rn e ww a y st os o l v er e l a t i v e l yl a r g e s c a l e o p t i m i z a t i o np r o b l e m s t h ed i s s e r t a t i o nc o n c e n t r a t e so nt h er e s e a r c ho ft h et h e o r i e sa n d t e c h n i q u e so fj o bs h o ps c h e d u l i n gb a s e do na n tc o l o n ya l g o r i t h m ( a c a ) & a r t i f i c i a ln e u r a l n e t w o r k ( a n n ) ；a n dr e a l i z e st h e j o bs h o ps c h e d u l i n go p t i m i z a t i o ns y s t e m t h ed e v e l o p m e n th i s t o r yo f j o bs h o ps c h e d u l i n gp r o b l e mi so u t l i n e db r i e f l y i na d d i t i o n t ot h i s ，t h ec u r r e n tr e s e a r c hp r o g r e s so ft h ej o bs h o ps c h e d u l i n gp r o b l e mi ss u m m a r i z e d ，t h e p r o b l e m sa n dt h et r e n d si nr e s e a r c ho ft h ej o bs h o ps c h e d u l i n gp r o b l e ma r ep i o n t e d t h e d e s c r i p t i o na n dt h ec l a s s i f i c a t i o no fj o bs h o ps c h e d u l i n gp r o b l e ma r ei n t r o d u c e da n dt h e m a t h e m a t i c a lm o d e l 、t h eg r a p hm o d e l 、t h ee x p r e s s i v ew a y 、t h ec r i t e r i ao fe v a l u a t i n g s c h e d u l i n gp e r f o r m a n c ea n ds o m ec o n v e n t i o n a l l yh e u r i s t i cr u l e so fj o bs h o ps c h e d u l i n ga r e d i s c u s s e d f i r s t ，o nt h eb a s i so ft h et s p , t h eb a s i cp r i n c i p l e sa n dt h et h e o r e t i c a lm o d e lo ft h ea n t c o l o n ya l g o r i t h m a r ei n t r o d u c e d ，a n dt h es o l u t i o ns t r u c t u r a lg r a p ho ft h ep h e r o m o n e d i s t r i b u t i o ni sd e f i n e db a s e do nt h eg l o b o i d a lm o d e l t h e nb a s e do nt h ej o bs h o ps c h e d u l i n g p r o b l e m ，t h et h e s i sc o n s t r u c t sag r a p hm o d e la n dp u t sf o r w a r dai m p r o v e m e n th y b r i da n t c o l o n ya l g o r i t h mt os o l v et h ej o bs h o ps c h e d u l i n gp r o b l e m ，a n dg i v e st h ee x p e r i m e n t a l s i m u l a t i o nb a s e do nt h eb e n c h m a r kp r o b l e m s ，t h ee x p e r i m e n t a lr e s u l t sd e m o n s t r a t et h e f e a s i b i l i t ya n dv a l i d i t yo f t h ei m p r o v e m e n ta l g o r i t h m t h en e wm o d e lo fc o n s t a i n ts a t i s f a c t i o na d a p t i v en e u r a ln e t w o r ki sp r e s e n t e d a c c o r d i n g t ot h et e c h n i c a lc h a r a c t e r i s t i co fj o bs h o ps c h e d u l i n g p r o b l e m s ，t h ec o n c e p t so fs t r o n g c o n s t r a i n ta n dw e a kc o n s t r a i n ta r ep r e s e n t e d c o n s i d e r i n gt h ed i f f e r e n tc o n s t r a i n e dt y p e s ，t h e c o r r e s p o n d i n gc o n s t r a i n ts a t i s f a c t i o nm e c h a n i s m sa r eg i v e n a tl a s t ，ae x p e r i m e n t a ls i m u l a t i o n b a s e do nt h eb e n c h m a r kp r o b l e m si s g i v e n ，t h ee x p e r i m e n t a lr e s u l t ss h o wt h a t t h en e u r a l n e t w o r ki sa b l et of i n do u tab e t t e ro rs a t i s f a c t o r ys c h e d u l i n gp a t hq u i c k l y i nt h ee n d ，t h ej o bs h o ps c h e d u l i n gs y s t e mi si n t r o d u c e d o nt h eb a s i so ft h er e s e a r c ho f t h ef o r ec h a p t e r s ，f i r s tt h es o f t w a r ec o n s t r u c t i o na n dt h ed e s i g nt h o u g h ta r ei n t r o d u c e d t h e n u s i n gp r o g r a m m i n gt o o lo fv i s u a lc + + 6 0a n ds q ls e r v e r2 0 0 0 b a s e do nt h et e c h n i q u e so f t h r e a da n dc o m p o n e n t ，t h i sp a p e ra n a l y s e sa n dd e s i g n st h ej o bs h o ps c h e d u l i n gs y s t e mu s i n g t h eo b j e c t o r i e n t e da n a l y s i sm e t h o d k e yw o r d s ：j o bs h o ps c h e d u l i n g ，a n tc o l o n ya l g o r i t h m ，a d a p t i v en e u r a ln e t w o r k 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中 不包括其他人已经发表或撰写过的研究成果，也不包含为获得河南工业大 学或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对 本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 论文作者签名：囟坠拯琴 日期：旦：望 关于论文使用授权的说明 本人完全了解河南工业大学有关保留、使用学位论文的规定，即：学 校有权保留送交论文的复印件，允许论文被查阅和借阅；本人授权河南工 业大学可以将学位论文的全部或部分内容编入有关数据库进行检索，可以 采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的论文在解 密后应遵守此规定) 论文作者签名_ 垒越肄 日期： 导师签名：i3111 至 日期：导师签名：1 f ，l 日期： ! i ! ! 望! ! 翌 智能车间作业凋度问题研究 第一章绪论 1 1 课题的背景及意义 随着科学技术的发展，生产规模越来越大，复杂性越来越高，市场竞争也越来 越激烈，因此对企业的管理和对生产过程的监控都提出了更高的要求。近几十年来， 各类生产过程都已经发生了显著的变化，其主要特征是生产规模的大型化和生成过 程的连续化。在激烈的市场竞争中，为了保证生产的高效稳定运行，以获得最大的 经济效益，原来简单的、局部的、常规的控制和仅凭经验的管理已经不能满足现代 生产的要求了，企业管理者和控制工程师们面临的问题是：如何根据市场一卜原料供 应和产品需求的变化进行经营决策和组织生产；如何在生产计划改变的情况下对生 产过程进行控制，以便最大限度地发挥生产的柔性；如何在生产工艺不作大的改变 的前提下进行管理、决策，使企业产生最大的综合经济效益。为了解决上述问题， 1 9 7 3 年h a r r i n g t o n 博士提出了计算机集成制造( c i m ) 的概念，c i m 是一种组织、管 理与运行企业生产的新哲理，它借助计算机软件、硬件，综合运用现代管理技术、 制造技术、信息技术、自动化技术、系统工程技术，将企业生产过程中有关人、技 术、经营管理三要素及其信息流与物质流有机地集成并优化运行，以实现产品的高 质、低耗，从而使企业赢得市场竞争。计算机集成制造系统( c i m s ) 是基于c i m 哲 理而组成的实际系统。在这种自动化程度较高的系统中，使生产过程合理、高效运 行的调度问题变得非常复杂，需要建立有效的计算机调度控制策略，才能使各种生 产资源的利用率达到最优，使企业在激烈的市场竞争中获得最大的经济效益。 而目前在我国一般企业中，生产调度的工作主要还是由老技工来完成，他们完 全靠经验来安排。如今，随着企业之间的竞争越来越激烈，产品的寿命周期变得越 来越短，产品的品种变得越来越复杂多样，以往的大批量小品种的生产模式渐渐变 成了小批量多品种的生产模式；不仅每天的生产品种在不断地改变，而且在客户就 是上帝的口号下，已经安排好的调度计划会突然由于客户需求的改变而改变，于是 调度工作也逐渐变成一项纷繁复杂的日常性工作。面对着这些变化和随时可能发生 的生产加工环境的改变，如机床设备的突然损坏等等情况，要使企业的生产能力和 效率始终保持较高的水平，仅仅依靠经验是不能胜任的。在技术装备较为先进的企 业中，它们一般拥有企业资源规划生产管理软件，但这些软件都不具备对生产车问 级的调控管理功能，所以同样面临着与一般企业相同的问题。如何较好地解决这 问题是当前企业界与学术界都十分紧迫的任务之一。因此，对车间作业调度问题的 河南业人学硕士学位论文 研究，吸引了国内外许多学者和实际车间作业调度人员的关注。 车间作业调度问题( j o bs h o ps c h e d u l i n gp r o b l e m ，j s s p ) 的研究不仅具有重要 的现实意义，而且还具有相当大的理论意义。这是由于：一方面，车问作业调度问 题的解决本身具有很大的现实意义。一个好的车间作业调度方案，不仅可以降低企 业的生产成本，而且还可以提高企业的按时交货能力，从而能够增强企业的竞争力； 另方面车间作业调度问题作为生产管理中最困难的问题，而且也已证明属于n p 一 难问题i i l l 2 ，目前尚无有效的求解策略，而对车间作业调度问题进行研究才i 仅可以 寻找有效的求解策略，推进相关算法的研究，如遗传算法、神经网络、蚁群算法等， 而且还能在此基础上提出新的算法，这为其它领域类似问题的解决提供了条件和手 段。因此对车间作业调度问题进行研究，也具有重要的理论意义。 1 2 车间调度问题的研究历程 自从2 0 世纪5 0 年代初期，应用数学、运筹学、工程技术等领域的专家学者就 丌始对调度问题进行了大量的研究。在研究的初期阶段，调度问题是作为一个纯粹 的数学问题来加以研究的。特别是5 0 年代早期，j o h n s o n 提出了解决n 2 g c m ，。( ” 个工件2 台机器的f l o ws h o p 型调度的最小流程周期问题) 和部分特殊的 n 3 g g 。问题的有效的优化算法【3 】，标志着调度理论研究的开始。由于调度问题 本身的复杂性，后来人们逐渐着手寻找有效的求解策略，到了6 0 年代初期，车间 调度理论围绕着整数规划、动态规划、分枝定界等优化方法，研究并解决了一系列 有代表性的调度问题【4 】【5 1 ；6 0 年代中期，人们逐渐认识到调度问题的复杂性，并着 手研究这个问题，到了6 0 年代后期，人们开始研究用启发式算法来解决复杂的调 度问题【6 1 17 1 1 8 1 ，至此调度理论的主体结构基本建立起来。7 0 年代初期，随着复杂性 理论( c o m p l e x i t y t h e o r y ) 和p - 完全问题( n p c o m p l e t e ) 研究的兴起”j ，人们丌 始重视对调度问题的复杂性研究，证明许多调度问题是p 一难问题，即使简单的j o b s h o p 和f l o ws h o p 调度问题也是p 难问题，不存在有效的多项式求解方法，因此 只好寻找有效的启发式算法来解决。针对不同的问题，人们提出了大量的启发式算 法“1 1 1 2 1 1 3 】【1 6 】：p a n w a l k e r 等回顾了二十年来调度理论的研究情况，总结和归纳 出1 1 3 条调度规则，并对其进行了分类【1 7 1 ；我国学者越民义等也开始研究调度问题 f 18 1 。到七十年代后期，随着对调度问题研究的深入，调度问题的研究已经成为应用 数学的一个分支，经典调度理论已经逐渐趋于成熟 1 9 】【20 1 。 经典调度理论虽然取得了重大进展，但实际调度问题比经典调度理论研究的问 题要复杂得多。因此，经典调度问题的研究结果往往都难以应用到实际调度问题中， 2 智能车间作业凋度问题研究 经典调度理论与实际调度问题还有相当大的差距。于是，自八十年代初期，人们就 直尝试解决实际调度问题，调度问题的研究开始转向应用研究阶段【2 ”。 到了九十年代以后，对车间调度问题的研究进入了高潮，各种研究手段得到了 充分发挥，同时还不断有新的研究工具被应用到调度研究当中。比较有代表性的技 术有：遗传算法、人工神经网络、蚁群算法等，智能调度已成为车间调度问题研究 的主流，其中蚁群算法等智能优化技术在调度问题研究中的应用成为浚领域的个 新的发展方向。 近几年来，随着软件技术及其它相关技术的发展和计算机硬件性能的提高，丌 发智能化生产计划与控制系统的时机已经成熟。目前，国外许多科研机构和软件公 司都研究和开发了针对各种生产实际的生产作业计划和调度系统。在国内，许多高 校和科研机构如清华大学、中科院沈阳自动化研究所和东北大学等单位参与了该领 域的工作，有些成果已经在国家的c i m s 示范工程中得到了一定程度的应用。但多 数企业的车间生产作业计划与调度软件都是针对某生产车间定制的，它只能应用于 特定的场合，而当前无论是开发者还是使用者，都迫切需要实现通用性好、适用面 广、智能化程度高的生产作业计划及资源优化利用智能支撑系统。 1 3 车间调度问题的研究现状 1 3 1 车间调度问题的研究方法 车间调度问题是典型的组合优化问题之一。当前，为了解决车间调度问题，常 用的调度方法大致上可以分为两大类 2 3 】：一类是基于模型的生产调度，也就是基于模 型的优化方法，即在定义调度问题的基础上建立调度模型( 常用的有数学规划模型、控 制模型等) ，然后基于模型运用一定的调度算法进行求解；另一类是基于规则的调度， 也就是基于规则的启发式方法，这种调度方法是应用最早、也是目前应用最为广泛的一 种制造系统调度方法。它是根据一定的规贝q 和策略来确定生产系统中的下一步操作。在 对于车间调度问题进行研究的方法上，最初是集中在整数规划、仿真和简单的规则 上，这些方法不是调度结果不理想就是难以解决复杂的问题。随着各种新的相关学 科与优化技术的建立与发展，在调度领域也出现了许多新的优化方法，比如人工神 经网络( a n n ) 、模拟退火法( s a ) 、遗传算法( g a ) 、禁忌搜索算法( t s ) 以及蚁群算法 ( a c a ) 等，使得调度问题的研究方法向多元化方向发展。下面分别对这些方法进行 总结： ( 1 ) 基于运筹学的方法 3 河南r 业大学硕士学位论文 基于运筹学的调度方法是将生产调度问题简化为数学规划模型，采用基于枚举 思想的分枝定界法或动态规划算法来解决调度最优化或近优化问题。文献 【2 4 】【2 5 】等提出了改进的分枝定界法，其不同点主要在于分析规则、定界机制 和e 界的产生这三方面存在差异。另外，文献 26 j 讨论了单件车间调度问题的整数规 划( i p l 模型，文献【2 7 】则更完整的讨论了l p 描述，i p 描述依赖于指示变量来指定工序 的顺序：文献 28 】提出一种新的整数规划模型，用一个线性不等式系统给出一个表达 先后约束的更好的方法；文献【2 9 】讨论了调度的线性规划模型。这类方法虽然从理论 上能求得最优解，但由于其计算复杂性和搜索效率低下，难以解决大规模的调度问 题，因而不能获得真正的实用。 总之，采用这种纯数学方法求解车间调度问题，虽然表达清晰，易于在计算机 上求解。但对于复杂的问题，具有模型抽取困难、运算量大、算法难以实现的弱点， 对于生产环境中的动态调度实现复杂，解决不了动态及快速响应市场的问题。 ( 2 ) 基于规则的方法 基于规则的调度是对车间调度问题进行研究的一种最传统的方法。因其调度规 则简单、易于实现、计算复杂度低等原因，并且能够用于动态实时调度系统中，许 多年来一直受到学者们的广泛研究，并不断涌现出新的调度规则。许多学者在这方 面已进行了探索并做了大量工作【1 7 】 2 3 1 【2 4 1 【3 0 】【3 “。 基于规则的调度直观、简单、易于实现，但它是局部优化方法，难以得到全局 优化结果。当系统规模较大，规则较多时，规则匹配速度很慢，而且产生规则系统 自适应能力差，很难适应动态调度环境，并且不能对得到的结果进行次优性的定量 评估。此外，近十年的研究表明并不存在一个全局最优的调度规则，它们的有效性 依赖于对特殊性能需求的标准及生产条件。即：规则具有全局敏感性，利用不同的 规则町产生不同的调度方案，而且规则在不同的场合所起的作用也不同，调度系统 的性能取决于规则的选取。因此，规则的选择成为基于规则调度方法的主要障碍。 ( 3 ) 基于系统仿真的方法 基于仿真的方法不单纯追求系统的数学模型，侧重对系统中运行的逻辑关系的 描述，能够对生产调度方案进行比较评价，分析系统的动态性能，并选择系统的动 态结构参数。出于制造系统的复杂性，很难用一个精确的解析模型来进行描述和分 析。而通过运行仿真模型来收集数据，则能对实际系统进行性能、状态等方面的分 析，从而，能对系统采用合适的控制调度方法。仿真方法最早被用来作为测试调度启 发式规则及分派规则的工具。后来，人们发现，通过将简单的优先权规则进行组合，或 用个简单的优先权规则将一些启发式规则进行组合，这样的调度优于单独的优先权规 4 智能乍间作业调度问题研究 则。于是，仿真方法逐渐发展为一种人机交互的柔性仿真工具，并用来进行车间凋度。 这样，就能通过仿真而动态地展现j o b s h o p 车间的状态，分析在不同的调度方法下的系 统性能，并运用知识和经验去选择合适的调度方法( 规则) ，从而改善调度性能。k i r a n 等回顾和总结了在动态环境下基于纯仿真模型j o b s h o p 调度问题的研究状况：文献 【1 0 l 提出了基于纯仿真模型的调度方法，即在一个较短的时问段内用仿真来评价一个 分派规则集，选取最小代价的规则，以适应系统状态的变化：文献 3 0 1 运用纯仿真模 型，同时解决f m s 中作业调度和搬运小车及刀具的资源分配问题：文献1 3 2 1 提出了一 种混合的仿真解析模型，用于分析和设计具有缓存的不可靠生产线问题。 基于纯仿真的方法虽然可以包含解析模型无法描述的因素，并且可以提供给使 用者一个调度性能测试的机会，但其不可避免地存在以下问题：a ) 缺乏理论意义； b ) 应用仿真进行生产调度的费用很高；c ) 仿真的准确性很大程度受编程人员的判断 和技巧的限制。 ( 4 ) 邻域搜索方法( 1 0 c a ls e a r c hm e t h o d ) 邻域搜索方法是基于模型的一类方法，属于近似算法。该方法是先有一个可行 的加工顺序，然后才确定每个操作的开工时间，并对这个顺序进行优化，最后有可 能得到最优的调度方案。邻域搜索方法在车间调度领域得到了相当广泛的应用，在 探索解空间时，仅对选定的成本函数值的变化做出响应，因而通用性强。这类方法 主要包括禁忌搜索( t a b us e a r c h ，t s ) 、模拟退火算法( s i m u l a t e da n n e a l i n g ，s a ) 、进化计 算( e v o l u t i o n a r yc o p u t a t i o n ，e c ) 等。 1 ) 禁忌搜索( t s ) 对于复杂的组合优化问题，禁忌搜索也是一种通过领域搜索以获取最优解的方 法，g l o v e r 叙述了它的基本原理。禁忌搜索是一种迭代方法，它开始于一个初始可 行解s ，然后移动到领域n ( s ) 中最好的解，即对于目标函数f ( s ) 在领域n ( s ) 中 是最优的。然后，从新的开始点重复此法。为了避免死循环，禁忌搜索把最近进行 的t 个移动( t 可固定也可变化) 放在一个称作t a b ul i s t 的表中( 也称短期记忆) ，在目 前的迭代中这些移动是被禁止的，在一定数目的迭代之后它们又被释放出来。这样 的t a b ul i s t 是一个循环表，它被循环地修改，其长度t 称作t a b us i z e 。最后，还须 定义一个停止准则来终止整个算法。由于t a b ul i s t 的限制，使其在搜索中有可能跳 出局部极小。其中，文献【3 3 】【3 4 1 分别用禁忌搜索对不同的车间调度问题进行了求解。 禁忌搜索算法作为一种全局优化方法，虽然在调度领域得到了广泛应用。但由 于禁忌搜索算法的搜索过程是串行搜索，因此，如何提高算法的优化效率也是t s 面临的重要课题。 5 河南【：业人学项士学位论文 2 ) 模拟退火算法( s a ) 模拟退火算法是将组合优化问题与统计力学中的热平衡问题类比，它模仿了晶 体结晶的冷却过程，在较高温度下，系统状态为s ，能量( 即目标函数) 为e ，选择s 的一个领域，如果e ( s ) - p t 曲。或s t 蛔一s t 曲p t f l q 、 ，i , j e p ，q e 1 ，m s l ，i e p , q e 1 ，嘲 ( 2 - 1 ) ( 2 - 2 ) ( 2 - 3 ) 从以上定义可知，车间作业调度问题求解的实质是求出符合某些约束条件的 s 。( k = l ，m ) 。性能指标c + 是所有工件中最后一道工序的最大完工时间，对应问题 的制造周期。 ( 2 - 1 ) 式表示同一工件的不同工序不能同时加工，即工序顺序约束；f 2 2 ) 式表示每台机器同一时刻只能加工一个工件，即资源约束；( 2 3 ) 式表示工件的町获得期 限约束。对于一个经典的n m g c m 。调度问题，共有”( 肌一1 ) 个式( 2 1 ) 表示的工序顺序 约束m n ( n 1 ) 个式( 2 2 ) 表示的资源约束不等式，m 行个式( 2 3 ) 表示的可获得期限约束 不等式6 7 1 1 6 8 】【6 9 】【7 0 】。 上述问题作了以下假设：所有的任务在零时刻都是可用的，并且无设备故障。任务 在机器上执行的时间事先已知。 2 3 2 车间作业调度问题的圈模型 车间作业调度问题可以用非连接图来表示【7 ，非连接图g = ( ，a ，e ) 定义为：n 包含代表所有工序的节点，4 包含连接同一工件的邻接工序的边，e 包含连接同个机 1 5 河南l 业人学硕仁学位论文 器上加工工序的非连接边，非连接边是可以有两个可能方向的边。调度是固定所有非连 接边的方向，以确定同机器上的工序顺序，一旦某台机器上的顺序确定下来，连接l 序的非连接边将被带优先箭头的连接边取代。非连接边集e = e u eu u e 。，每台机 器用子集e 。表示。图2 - 2 是3 工件3 机器的非连接图实例，其中每个j ：件包含3 道工序， 节点n = f o ，1 ，2 , 3 ，4 ，5 ，6 ，7 ，8 ，9 ，l o 对应工序，其中0 和1 0 是虚设的起始工序和终止工序。 连接边a = ( 1 ，2 ) ，( 2 ，3 ) ，( 4 ，5 ) ，( 5 ，6 ) ，( 7 ，8 ) ，( 8 ，9 ) 对应同一工件的工序前后约束。非连接边( 虚 线表示) e 。= ( 1 ，4 ) ，( 4 ，8 ) ，( 8 ，1 ) 1 对应机器1 上加工的工序，非连接边e ：= ( 2 ，6 ) ，( 6 ，7 ) ，( 7 ，2 ) ) 对应机器2 上加工的工序，非连接边e = ( 3 ，5 ) ，( 5 ，9 ) ，( 9 ，3 ) 对应机器3 上加工的工序。 车问作业调度问题是找出每台机器上工件的加工顺序，即确定非连接边的方向，使 得产生的结果图是非循环的( 2 1 2 序间无先后冲突) ，并且使起始点到终止点的关键路径的 长度最小。关键路径的长度对应于工件最大流程时间。 图2 - 23 工件3 机器的非连接图 2 4 车间作业调度问题的结果表示、评价性能指标和启发式规则 通常用甘特图表示调度的结果，有两类甘特图：面向机器的甘特图和面向工件的甘 特图。用下标驴来命名每一道工序，这罩i 表示工件，表示工件的加工工序。下图2 3 机器甘特图表示3 工件3 机器问题的一个可行解。 m j2 11 1 3 2 m ： ! ! ! 兰一上一! ：! j m l 二二互二二： 二二 互二 1 6 791 01 2 图2 - 33 工件3 机器调度问题的机器甘特图 车间作业调度问题的评价性能指标很多，这里给出几个基于加工完成时间常用的评 价指标。首先引入几个相关变量和符号。 1 6 智能车间作业调度问题研究 1 ) p t 工件i 的第j 道工序的加工时间。 2 ) m t 在机器- ，上加工工序的加工时间a 3 ) e ，：_ r = 件f 的加工完成时间。 4 ) m ，：机器，的加工完成时间。 5 ) f ：工件i 的流经时r f i j ( f l o w - t i m e ) ，即f = e ，一。 6 ) e ：工件i 的流通时间。 基于此，我们给出调度问题常用的一些典型性能指标： 1 ) 平均流程时间f ：i 。吉善最，。 2 ) 作业流通率的平均值万：万= 吉( 古p o ) 1 0 0 。 1 n 1 7 j = ll ，；t 3 ) 作业流通率的标准差巧：巧= i 1 缶n 百1 蔷mp t ! - 丐) 2 。 4 ) 机器利用率的平均值瓦：瓦= 土m 蔷( 了m 善肼1 0 0 。 百，百 5 ) 机器利用率的标准差瓦：瓦m 荟赤m 善舢厂一) 2 。 百，、百 6 ) 机器均衡率m e ：m 。2 1 翼野( m ( ，) 7 m a ) 【 ? 搿( 善”) ，：搿( 善删一 1 0 0 。 在车间作业调度问题中会发生多个工件在一台机器前排队的现象，于是就面临着如 何选择一个工件优先加工的问题，这也是影响调度结果的关键所在。学者们已经提出许 多启发式规则，各种规则大多是针对所提出的特定问题的一种解法。目前常用的启发式 规则有以下几种： 1 1 s p t 规则；最短处理时间的工序先加工。 2 ) l p t 规则：最长处理时间的工序先加工。 3 ) f c f s 规则：先到先加工。 4 ) m o p n r 规则：最多剩余工序数的工件先加工。 5 ) f o p n r 规则：最少剩余工序数的工件先加工。 1 7 河南1 业大学硕十学位论文 6 ) l r t 规则：最多剩余处理时间的工件先加工。 7 ) s r t 规则：最少剩余处理时白j 的工件先加工。 8 ) p r o c e s st i m er a t i o ：选择具有最小f 加工时间总加工时问) 的下件先加f 。 9 ) p r o c e s st i m er e m a i n i n gr a t i o ：选择具有最小( 加工时间剩余加l ：时间) 的零件先加工。 1 0 ) r a n d ：随机选择加工工序。 以上的优化规则都有一个共同的缺陷，即只考虑了工件的信息，而没有考虑加工工 件的机器的加工信息，也没考虑所选加工工件的下一道工序的机器的繁忙程度。这样有 可能造成空闲的机器更空闲，繁忙的机器更繁忙。 2 5 本章小结 车间作业调度问题是一类很复杂的生产调度问题，本章对车间作业调度问题进行了 描述，给出了车间作业调度的定义、数学模型、图模型和结果表示方法，并对常用的调 度评价性能指标、启发式规则进行了总结。 1 8 智能午间作业调度问题研究 第三章基于人工蚁群算法求解车间调度问题 3 1 蚁群算法概述 蚂蚁算法最初由m d o r i g o 在其博士毕业论文中提出，现在已经发展了1 0 多年，分 为几个研究阶段，有蚂蚁算法、蚂蚁系统、蚂蚁种群搜索算法以及蚂蚁种群优化算法 等。无论怎么发展，这些算法思想都基本相同，侧重于蚂蚁怎么走，怎么留下信息素， 利用正反馈来最终找到最佳的食物源。蚁群算法是继模拟退火算法、遗传算法、禁忌搜 索算法、人工神经网络算法等启发式搜索算法以后的又一种应用于组合优化问题的启发 式搜索算法。 3 1 1 蚁群算法的基本原理 蚁群算法是一种群体智能算法，是模仿真实的蚁群行为而提出的。经过生物学家大 量细致的观察研究，发现蚂蚁个体之间是通过一种称之为信息素的物质进行信息传递 的，起到一种正反馈作用，能很好的协调蚁群的活动。蚂蚁在运动过程中，能够在它所 经过的路径上留下该种物质，而且蚂蚁在运动过程中能够感知这种物质，一条路上的信 息素踪迹越浓，其它蚂蚁将以越高的概率跟随此路径，从而该路径上的信息素踪迹会被 加强，因此，由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象：某一路 径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。蚂蚁个体之间就是通过这种 间接的通信机制达到协同搜索食物最短路径的目的。下面引用文献【_ 乃l 所举的例子来具体 说明基本蚁群算法原理。如图3 1 所示，假设蚂蚁以l 单位长度单位时间的爬行速度往 返于食物源a 和巢穴e ，其中d 为距离，每过一个单位时间各有3 0 只蚂蚁离开巢穴和食物 源( 图3 1 ( a ) ) 。 假设t = 0 时，有3 0 只蚂蚁在b 点和d 点( 图3 1 ( b ) ) 。由于此时路上没有信息素，蚂蚁就以相 同的概率走两条路中的一条，因而1 5 只蚂蚁选择往c ，其余1 5 只选择往f 。t = l 时， ( 呻鲁育3 0 只准备离开b - d巾) g - 搴i1 - 4 旯奄辟c f仁) 2 0 只硅母c , t o 旯酶嚣f 图31 蚂蚁群觅食行为示意图 1 9 河南r 业人学硕士学何论文 经过c 的路径被3 0 只蚂蚁爬过，而路径b f ；f h d f 只被1 5 只蚂蚁爬过，从而b c d 上的信息素 踪迹的浓度是b f d 的2 倍。此时，又有3 0 只蚂蚁离开b 和d ，于是各有2 0 只蚂蚁选择往c ， 另外的1 0 只蚂蚁选择往f ，这样更多的信息素被留在更短的路径b c d 上，这个过程一直 重复，短路径b c d 上的信息素踪迹的浓度以更快的速度增长，于是越来越多的蚂蚁选择 这条短路径，最终蚂蚁完全选择b c d 这条最路径来觅食( 如图3 1 ( c ) ) 。从而找到由蚂蚁 巢到食物源的最短路径。由此可见，蚂蚁个体之间的信息素交换是一个下反馈过程。 通过上例可知蚂蚁觅食协作方式的本质是：( 1 ) 路径概率选择机制：信息素踪迹越 浓的路径，被选中的概率越大；( 2 ) 信息素更新机制：路径越短，在上面的信息素踪迹 浓度增长越快；( 3 ) 协同工作机制：蚂蚁之间通过信息素来进行信息传递。 蚁群算法的机理可以抽象为以下过程： 在蚁群优化算法中，作为分布智能体( d i s t r i b u t ea g e n t ) 的人工蚁( a r t i f i c i a la n t s ) 的 行为可以如卜描述：一群人工蚁相互协作在问题的解空间中搜索好的解，这些人工蚁按 照人工信息素踪迹和基于问题的启发式信息的指引在问题空间移动以构造问题的解。在 此，信息素( p h e r o m o n e ) 类似于一种分布式的长期记忆，这种记忆不是局部地存在f 单 个的人工蚁，而是全局地分布在整个问题空间。当人工蚁在问题空间中移动时，它们在 其经过的路径上留下信息素踪迹，这些踪迹反映了人工蚁在问题空间觅食( 即构造好的 解) 过程中的经历。亦即，信息素在蚁群的协作和通信中起到一种间接媒介的作用。人 工蚁在解空间中一步一步地移动从而构造问题的解，同时，它们根据解的质量在其路径 上留下相应浓度的信息素，蚁群中其它蚂蚁倾向于沿着信息素浓的路径前进，同样这些 蚂蚁也将在这段路径上留下自己的信息素，这就形成了一种自催化强化学习机制，也就 是正反馈。这种正反馈机制将指引蚁群找到高质量的问题解。 除人工蚁的觅食行为外，蚁群优化算法还包括另外两个机制：信息素挥发和后台行 为。遗忘是一种高级的智能行为，作为遗忘的一种形式，路径上的信息素随着时间不断 挥发将驱使人工蚁探索解空间中新的领域从而避免求解过程过早的收敛于局部最优解。 后台行为包括领域( 局部) 搜索( l o c a ls e a r c h ) 过程以及问题全局信息的收集。蚁群优化是 种基于种群的构造型自然启发式优化方法，这种构造性方法如果与改进型的迭代方法 相结合，其效果将更好。 3 1 2 蚁群算法模型 8 0 l 31 2 1 蚁群算法的理论模型 蚁群优化算法可以看作为一种基于解空间参数化概率分布模型的搜索算法框架。在 蚁群算法中，解空间参数化概率模型的参数就是信息素，因而这种参数化概率分布模型 智能车间作业调度问题研究 就是信息素模型。在基于模型搜索算法框架中，可行解通过在一个解空间参数化概率分 布模型上的搜索产生，此模型的参数用以前产生的解来进行更新，使得在新模型上的搜 索能集中在高质量的解搜索空间内。这种方法的有效性建立在高质量的解总是包含好的 解构成元素的假设前提下。通过学习这些解构成元素对解的质量的影响有助于找到一种 机制，通过解构成元素的最佳组合来构造出高质量的解。一般来说，一个基于模型的搜 索算法通过以下两步迭代来解