（机械制造及其自动化专业论文）基于知识的实时调度决策支持平台研究.pdf

中文摘要中文摘要摘要：随着制造业竞争的加剧，生产调度研究已经从理论探索转移到实际应用阶段，如何在有限合理的时间内获得满足要求的调度方案成为制约车间生产效率的重要因素。另一方面，在实际生产中，生产状态的复杂性与不可预见性使通过传统方法得到的预调度方案失去了意义。因而，能够快速响应生产状态变化的重调度成为生产调度研究的重点。为对动态调度进行决策支持，本文在对生产调度问题分析的基础上，提出了基于知识的生产调度决策支持平台框架，该框架基于l p k i 结构；借助人工神经网络的学习、记忆功能，以人工神经网络作为学习推理机，建立了基于规则的适应规则调度模型( r b s ) ；研究了确定性生产调度理论中的调度问题表示与推理，提出了一种基于案例的生产调度模型( c b s ) ；最后在v c 抖6 0 环境中建立了基于包含r b s 和c b s 的实时调度平台。本文主要研究内容和取得的研究成果表现在以下几个方面。( 1 ) 建立了基于规则和人工神经网络相结合的适应规则调度模型( r b s ) ，该模型以人工神经网络作为学习推理机，具有快速响应，瞬时计算的特点，能够适应动态调度的实时性要求。其中人工神经网络的输入为制造车闻的生产状态参数，输出为当前采用的调度规则。( 2 ) 提出了一种基于案例的调度模型( c b s ) ，知识的表示采用确定性生产调度中的面向对象的三域模型，推理机制建立于确定性生产调度计算复杂度归结关系。该模型将知识的表示和推理与调度领域紧密结合，建模简单方便。( 3 ) 提出了基于知识的生产调度决策支持平台框架，并建立了由前述r b s和c b s 模块构成的基于知识的决策支持调度系统( k b s s ) ，设计了平台的工作流程，知识库，给出了c b s 模块中案例搜索的计算机算法。关键词：经网络分类号：基于规则的调度；基于案例的调度；动态实时调度；决策支持；人工神t h l 6 5 ：t p l 8a b s t r a c t_ 一a b s t r a c ta b s t r a c t ：w i t ht h ei n c r e a s i n gc o m p e t i t i v e n e s so ft h em a n u f a c t u r i n gi n d u s t r y , h o wt oo b t a i nas a t i s f i e ds c h e d u l i n gs e q u e n c ei nr e a s o n a b l et i m eb e c o m e sak e yf a c t o ri np r o d u c t i o ne f f i c i e n c y o nt h eo t h e rh a n d ，d u r i n gt h ea c t u a lp r o d u c t i o np r o c e s s ，t h ep r o d u c t i o ns t a t ei ss oc o m p l e xa n du n p r e d i c t a b l et h a tt h ea d v a n c e ds c h e d u l i n gs e q u e n c em a vl o s ei t sf u n c t i o na f t e rs o m eu n k n o w ni n c i d e n t s h o wt or e s p o n dq u i c k l yt ot h o s ec h a n g e sa n dr e s c h e d u l eh a sb e c o m et h ef o c u so f t h es t u d yo f p r o d u c t i o ns c h e d u l i n g i n t h i st h e s i sas c h e d u l i n gs u p p o r ts y s t e mb a s e do nl p k im o d e li sp r e s e n t e di n c l u d i n gc b s ，r b s ，m b sa n do t h e rm o d u l e s a r t i f i c i a ln e u r a ln e t w o r ki su s e df o ra ni n f e r e n c ee n g i n eb a s e do nt h ef u n c t i o no fl e a r n i n ga n dm e m o r yo fi ta n da na d a p t i v er u l e b a s e ds c h e d u l i n gm o d e l ( r a s ) i se s t a b l i s h e d w h a t sm o r e ，t h er e p r e s e n t a t i o na n dr e a s o n i n go fd e t e r m i n i s ts c h e d u l i n gp r o b l e m sa r es t u d i e da n dan e wk i n do fc a s e - b a s e ds c h e d u l i n g ( c b s ) i sp r e s e n t e d f i n a l l y ，ar e a lt i m es c h e d u l i n gp l a t f o r mi se s t a b l i s h e db a s e do nr b sa n dc b si nt h ee n v i r o n m e n to fv c + + 6 0 t h em a j o rc o n t r i b u t i o n so ft h i st h e s i sc a nb es u m m a r i z e da sf o l l o w s 1 a na d a p t i v er u l e - b a s e ds c h e d u l i n gm o d e l ( r b s ) i ss e tw i t ht h ea r t i f i c i a ln e u r a ln e t w o r ka st h ei n f e r e n c ee n g i n e t h i sm o d e lc a nr e s p o n dq u i c k l yt ot h ec h a n g e si np r o d u c t i o np r o c e s sa n dc o m p u t ei n s t a n t l yt oa d a p tt ot h er e a l t i m er e q u i r e m e n t so fd y n a m i cs c h e d u l i n g t h ei n p u t sa n do u t p u t so fa r t i f i c i a ln e u r a ln e t w o r ka r et h es t a t ep a r a m e t e r so ft h em a n u f a c t u r i n gw o r k s h o pa n dt h ec u r r e n ts c h e d u l i n gr u l e st ob eu s e d 2 ac a s e b a s e ds c h e d u l i n gr c b s ) m e t h o di sr e p r e s e n t e d t h es c h e d u l i n gp r o b l e m sa r er e p r e s e n t e db yam o d e li nd e t e r m i n i s t i cs c h e d u l i n gt h e o r yw h i c hc o n s i s t so f3o b j e c t sa n di t sr e a s o n i n gm e c h a n i s mi sb a s e do nt h ec o m p u t a t i o n a lc o m p l e x i t yi ns c h e d u l i n g t h ek n o w l e d g er e p r e s e n t a t i o na n dr e a s o n i n ga r ec l o s e l yi n t e g r a t e dw i t hs c h e d u l i n gt h e o r y , t h ew a yo fw h i c hm a k e sm o d e l i n gs i m p l ea n dc o n v e n i e n t 3 t h ef r a m e w o r ko fk n o w l e d g e b a s e dp r o d u c t i o ns c h e d u l i n gp l a t f o r mi se s t a b l i s h e d ，w h i c hc o n s i s t so ft h em e n t i o n e dm o d u l e sr b sa n dc b s ，t h e nt h ew o r k f l o wa n dd a t a b a s ea r ed e s i g n e d ，f i n a l l yc o m p u t i n ga l g o r i t h mf o rs e a r c h i n gc a s e si nc b sm o d u l ei sg i v e n k e y w o r d s ：r u l e b a s e ds c h e d u l i n g ；c a s e b a s e ds c h e d u l i n g ；r e a lt i m es c h e d u l i n g ；d e c i s i o ns u p p o r t ；a n nv l l北京交通人学硕十学位论文c l a s s n o ：t h l 6 5 ；t h l 8独创性声明独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示了谢意。学位论文作者签名私易签字日期：卅年6月日7 lj 瓢学位论文版权使用授权书本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索，提供阅览服务，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和磁盘。( 保密的学位论文在解密后适用本授权说明)学位论文作者签名：签字聃：1 年导师签名：5 ，m 丐签字同期：必哆年多月形日互日是锄研朋致谢本论文的工作是在我的导师刘阶薄副教授的悉心指导下完成的，刘阶萍副教授严谨的治学态度，科学的工作方法和平易近人的风范给了我极大的帮助和影响。在此衷心感谢两年来刘阶萍老师对我的关心和指导，并致以我最崇高的敬意!在研究过程中，我的师姐马丽梅博士给了我很大的帮助与支持，她深厚的理论基础，广博的知识帮我克服了众多的难题，在此向她表达我内心的感谢!在实验室工作及撰写论文期间，陈彦飞同学对我论文中的研究工作给予了众多宝贵的意见，在此向她表达我的感激之情。同时感澍本文引用文献的作者们，他们的探索精神与劳动成果是本文得以成文的重要动力与基础，在此向他们致以衷心的感谢。另外也感谢家人，他们的理解和支持使我能够在学校专心完成我的学业。最后，谨向百忙之中抽出宝贵时间评审论文的各位专家、学者表示我最诚挚的感谢。作者：郭玉兵2 0 0 9 年6 月引言1 1 研究背景与意义1 1 1研究背景1 引言制造是人类最基本的生产活动之一，制造自动化是人类提高劳动生产率，提高企业竞争力，降低生产成本，缩短生产周期，获得更多利润的重要手段。从2 0世纪初，以泰勒科学管理为指导的自动生产线大大提高了大批量生产的效率，它具有固定的生产节拍，因面称为刚性生产自动线。随着二战后日本的崛起，人们才渐渐认识到，大批量生产活动只占整个制造活动的1 5 2 5 ，而中小批量生产占整个制造活动的7 5 8 5 【l , 2 1 。另一方面，随着计算机的发展，数控机床在制造自动化领域丌始逐步取代机械或液压式机床，它可以方便的完成不同的加工操作，非常适合多品种，中小批量产品的生产，因而被称为柔性加工设备。进一步的研究发现，零件在机床上的加工时间仅占零件全部生产时问的5 ，毛坯和半成品的运输、存放、准备时间占零件全部生产时间的9 5 【l 捌。为了进一步提高劳动生产率，必须对零件整个生产过程的各个环节实现自动化，由此产生了柔性制造系统f m s 。生产调度问题是生产管理的关键环节，它主要用于解决工件在机器上的调度和资源分配问题，能够合理安排任务与资源，保证目标的最优性，提高生产效率，减少产品的提前和拖期，尽可能获得最大的利润【3 】。由于f m s 的物料流过程复杂，生产方式灵活，其生产调度对现有的调度理论与实践提出了巨大考验。传统的基于运筹学的调度方法因为建模困难、耗时，以及难以求解，无法及时有效地解决f m s 中的生产调度问题；而在实际生产中广泛应用的基于规则的调度方法往往只是一种单一的调度规则，难以获得较好的结果；专家系统调度受到知识获取瓶颈问题；计算机仿真方法则侧重于f m s 模型的评价及简单调度规则的评价。因此现有调度方法一般不能直接用于f m s 生产调度。1 1 2研究意义一般认为，生产车间调度是n p 完全问题中最困难的问题之一【4 1 。即使车间调北京交通大学硕士学位论文度问题中比较简单的流水车间调度问题( f l o ws h o ps c h e d u l i n gp r o b l e m ，f s s p ) ，也是与城市距离不对称情况下的货郎担问题( t r a v e l i n gs a l e s m a np r o b l e m ，t s p )难度相当的同一类问题，所以一直以来调度算法的研究与应用都是车间调度理论中主要的研究方向。根据决策活动的特征，可以将决策问题分为结构化与非结构化问题【5 】。基于运筹学的经典理论旨在解决结构化的问题：其决策目标是明确的，用户对问题清楚，可以利用标准的数学建模语言来描述该问题，能够根据一系列决策准则得到特定的解。然而对于调度领域中的问题，由于其本身的复杂性，描述这种问题本身通常就是不现实的；或许能够描述问题，但是因为问题多变，没有一个固定的准则来解决此类问题。生产调度问题是非结构化或半结构化问题，直接求解最优解是困难的，人们往往需要的不是某个确定的准则，而是辅助决策者进行决策活动的系统。虽然目前生产调度领域已经有了比较成熟的智能调度方法，并且众多学者仍然在寻求更有效的调度算法，但由于调度问题的复杂性，单一的调度算法对制造企业的用途不大，往往更多的仅限在理论研究中。同时因为实际中的调度经常是随机发生的，如在机械加工中，新工件的到达，加工机床的故障等随机事件，使生产调度不能按预调度进行。可见，一个辅助决策者进行调度、能够及时处理随机事件的决策系统的意义远远大于研究单一的调度算法。而这种集各种算法及决策支持于一体的系统，目前还少有人去进行尝试。所以我们拟建立一个通用的决策支持平台，它不只针对某一类特定问题的求解，。而是能够提供各种常规问题的解决方案( 0 - 7 以使用调度理论中的经典方法) ，充分利用决策支持能力和计算机快速计算能力，及时响应制造车间的需求，进行快速调度决策支持。1 2研究现状调度理论产生于生产制造车间，具有很强的实际背景。事实上，调度理论已经广泛应用于编制生产计划、企业管理、交通控制、医疗卫生、服务业等各个领域。一般认为，j o h n s o n 于1 9 5 4 年对流水车间两台机床排序问题的求解是调度理论产生的标志( 6 】。此后5 0 年来，在运筹学，工业工程和计算机控制等领域它得到了理论界和工程技术人员的广泛关注。2 0 世纪7 0 年代后期，经典调度理论取得了重要进展，并形成了一门科学。但2引言是经典调度理论与实际应用之间存在着巨大的脱节，虽然计算机的出现在一定程度上缓解了这种状况，但在求解大规模问题时仍会出现求解耗时长，效率低等缺点。调度问题属于组合优化问题，属于n p 问题，寻找调度的最优解是非常困难的。人们渐渐认识到，最有工程意义的方法不是去寻找最优解，而在合理有限的时f 日j范围内寻找满意解，并对生产计划制定人员进行调度决策辅助，而不是替决策者调度。因此，从2 0 世纪8 0 年代丌始，人们便丌始尝试并致力于解决实际生产调度问题，调度的研究从理论研究转到实际应用研究阶段。在这样的背景下，人工智能，计算智能便走上了历史的舞台。2 0 世纪8 0 年代，以c a r n e g i em e l l o n 大学的m f o x 为代表的学者们开展了基于约束传播的智能调度和信息系统( i n t e l l i g e n ts c h e d u l i n ga n di n f o r m a t i o ns y s t e m ，i s i s ) 的研究【7 】，开辟了人工智能在调度领域中的应用，它是第个旨在解决j o bs h o p 调度问题的专家系统。基于人工智能的调度方法分两大类：智能调度专家系统与基于m u l t i a g e n t 技术( m u l t i a g e n ts y s t e m ，m a s ) 的合作求解方法等捧j 。( 1 ) 智能调度专家系统专家系统在2 0 世纪8 0 年代初期非常流行，它将领域和现场约束表示成知识库，再按现场实际情况从知识库中产生调度方案，并能对意外情况采取相应对策。上面提到的i s i s 基于3 类约束：组织上的目标，物理限制和临时约束，并使用有关约束来保证调度知识的一致性。黎志成等人提出了一种基于专家仿真系统的生产重调度方法【9 】。但专家系统普遍存在调度知识获取瓶颈问题。( 2 ) 基于m a s 的合作求解方法为了解决专家系统知识获取困难的难题，人们使用“分而治之( d i v i d ea n dc o n q u e r ) 的方法来开发分布式调度系统。典型研究和应用有：g r a c e y u h - j i u n 等人在其提出的m a s 框架中将制造系统中各功能和实体( 机器设备、任务、数据库等) 一都予以a g e n t 化，并采用基于价格机制的市场模型实现a g e n t 之间的协商【l 叫；王艳红等人研究了敏捷制造环境下制造车间生产过程的动态调度问题，提出了综合运用m u l t i a g e n t 技术与规则调度解决这一动态调度问题的方法【l l 】；赵博在调度算法分类的基础上，提出用m a s 技术实现种调度算法的集成【1 2 1 ，主要方案是针对不同类别算法的不同结构，定义不同的a g e n t ，它们本身是通用的，但是在不同的环境中，它们可以运用相应的知识进行协作来解决具体的调度优化问题等等。研究表明，m a s 技术特别适用于解决复杂问题，尤其是那些经典方法无法解决的单元间有大量交互作用的问题。其优点是速度快、可靠性高、可扩展性强、能处理带有空间分布的问题、对不确定性数据和知识有较好的容错性。m a s 的不3北京交通人学硕+ 学位论文足之处就是在理论上有待进一步完善，标准化工作不够，导致重复劳动。可见，在以实际应用为导向的今天，专家系统开辟了面向用户需求的辅助决策思想，为用户提供决策支持，在调度领域中才刚刚起步。1 3研究内容与创新点1 3 1研究内容本文在前人工作的基础上，完成了以下工作：( 1 ) 总结了目前生产调度领域中的求解方法，分析各种方法的优劣。着重将生产调度问题分为静态调度和动态实时调度两类，总结目前存在的求解思路。( 2 ) 在对决策支持系统结构分析的基础上，首次提出了基于l p k i 结构的生产调度决策支持平台的框架，建立平台的功能结构。( 3 ) 建立了基于规则与人工神经网络相结合( a n n + r b s ) 的动态调度模型。运用静态调度算法的求解结果对人工神经网络进行训练，以人工神经网络作为学习推理机，运用此模型对一个实际算例进行了仿真对比。( 4 ) 提出了基于确定性调度分类模式的知识表示方法( c b s ) 。将调度知识表示成一个包含三个域的模型，并通过计算复杂度中的归结关系进行推理。( 5 ) 建立了包含a n n + r b s 与c b s 两个子单元的实时调度平台。给出详细设计及工作流程。1 3 2论文创新点本论文首次提出了一种基于l p k i 结构的通用的生产调度决策支持平台，该平台融合了多种有效的调度算法，其目的在于向调度决策人员提供决策支持，而不是代替决策人员进行调度。将人工神经网络用作基于规则调度的推理机并将调度过程中的意外情况看作决策点，在各决策点进行动态调度，有效地包含了重调度机制。将确定性调度领域的知识与c b r 理论紧密结合，提出了基于调度问题分类模式的面向对象的知识表示方法和基于计算复杂度归结关系的案例搜索方法。开发了包含r b s 和c b s 两个模块的调度决策支持系统，将本文中的理论用于工程实践。4引言1 4论文结构全文一共分七章：第一章为引言，介绍本文的研究意义、现状和内容，指出本文的工作内容。第二章对生产调度问题进行概述。根据不同的指标对生产调度问题进行分类，并着重对静态调度和动态调度的求解方法进行总结。第三章提出基于l p k i 结构的生产调度决策支持平台构架，设计了该平台的功能结构。第四章建立基于规则和人工神经网络相结合的动态调度模型。详细阐述人工神经网络的工作原理和过程，以遗传算法的求解结果作为教师数据对人工神经网络进行训练，并将其应用于动态实时调度。第五章提出基于确定性调度分类模式的知识表示和基于归结关系的推理方法。介绍确定性生产调度理论中的三域模型和计算复杂度中的归结关系，以此为基础进行调度问题的表示与推理。第六章建立基于上面两种模型的实时生产调度平台。在第三、四、五章理论的基础上，基于v c + + 6 0 和s q ls e r v e r2 0 0 0 建立动态实时调度平台的基本框架并实现基本功能。第七章对本文进行了总结与后续工作展望。指出本文所建平台的不足与后期工作的方向。论文的总体结构如图1 1 所示。5北京交通人学硕士学位论文引言( 研究意义与内容)，7 、。、牛产调度问题概述生产调度决策支持甲台框架( 生产调度及其求解方法)( 基于l p k i 结构，功能结构) o ，对于任意的连续函数厂，存在一个三层b p 神经网络，其输入层有珂个神经元，中间层有2 n + 1 个神经元，输出层有m 个神经元，它可以在任意占平方误差精度内逼近厂。定理1 不仅说明了映射网络的存在，而且说明了映射网络的结构。即总存在一个结构为n f 2 n + 1 ) m 的三层前向神经网络能够精确地逼近任意的连续函数 o第二，如何调整b p 神经网络的权值，使b p 神经网络的输入输出关系逼近函数f 。b p 学习算法给出了具体方法。基于规则推理的动态实时调度4 2 2 2b p 学习算法b p 学习算法最早由r u m e l h a r t 等在1 9 8 6 年提出【4 5 1 ，下面只推导三层神经网络的学习算法。设第二层的第_ ，个神经元的输入总和为“；，输出为j ，；，非线性函数为正；第三层第k 个神经元的输入总和为，输出为戎，非线性函数为五，输入层节点f 到隐层节点，的权值为吻，隐层节点到输出层节点尼的权值为，输入层各输入为咒1 ，则有：y ；= 以( “；)y ：= 六( 甜；)吁2 = 如一( 4 - 1 )f“：= 巧jb p 学习算法通过反向学习过程使误差最小，因此选择目标函数为m i nj = 昙羔( 蚝一) 22 )厶七= 1即选择神经网络的权值使期望输出与神经网络的实际输出坛之差的平方和最小，实际上是求在式4 1 约束下，目标函数，的极小值。利用非线性规划中的“最速下降法 使权值沿着目标函数的负梯度方向改变可以求得的最小值。最终b p 算法可归纳为：awj k = 一sdk 3y j= ( 1 一成) ( 戎一)一曲q = 一s d ：试巧= 巧( 1 一巧) k = l( 4 - 3 a )( 4 - 3 b )( 4 - 3 c )( 4 3 d )可见，要求得两个层间权值的改变量，需要先求得后面两个层间的权值改变量，即这种学习算法是反向进行的，所以称作b p 人工神经网络( b a c k p r o p a g a t i o nn e u r a ln e t w o r k ，反向传播神经网络) 。4 2 2 3b p 算法的实现b p 算法的学习过程如图4 4 所示。2 7北京交通大学硕+ 学位论文 鸯应、7人、一，7 7y一、y图4 _ 4b p 算法学习过程f i g u r e4 - 4l e a r n i n gp r o c e s so fb p经过训练的人工神经网络可以认为已经具备了由输入到输出的一定模式的映射，并且认为这种映射是稳定的、有效的。这样，我们就可以将一定的输入加到输入结点，经过人工神经网络的计算得到输出。4 3人工神经网络动态调度建模如前所述，b p 神经网络是最广泛应用的a n n 学习算法，可实现输入和输出间的任意非线性映射。本文选用三层b p 神经网络。习习圃延磊一赢一恙竺赢一丫竺型竺基于规则推理的动态实时调度输入参数要根据调度目标进行选择，输入参数应该选择对调度目标有较大影响的生产状态参数。i ) 输入层神经网络的输入是动态调度系统中的生产状态参数，输入层神经元的个数由生产系统状态参数个数决定。本文选定了一些有代表性的对最小化延期损失有较大影响的4 个状态参数【4 6 】：( 1 ) 机床待加工队列任务数所有等待在某台机床上加工的操作构成了机床的可操作集合。如假设z 的加工工序依次是p i i ，p 。：。则当工件在机床l 上加工时，机床2 上没有任务。此时机床2 的可操作集合为空，待加工队列任务数为0 。而p 完成后，机床2 的可操作集合为 p 。： ，机床2 的待加工队列任务数为1 。机床待加工队列任务数反应了机床的负荷情况，任务数越多，机床负荷越大。在调度时应尽量将新到工序安排到其他机床上加工。( 2 ) 机床利用率秒从可操作集合中选取交货时间最大的操作，设交货期为d 一，设t 为当前时间。则：机床利用率口：堡堡堡坠型! 塑三三堕d 。一t机床利用率反应了从当前到交货一段时间内机床的繁忙程度。由于当前d 一可能等于f ，所以通常使用机床利用率的倒数作为神经元的输入，即：!：望塑丛二!机床利用率y 待操作队列中加工工时( 3 ) 平均操作松弛时间r对每一个操作既，其松弛时问为：喀一f 一( 既及该工件剩余操作时间和) 。其中，谚为该操作的交货期。操作松弛时间反应了该操作离交货期的远近，松弛时间越小，任务越有可能延期，其平均值则反应了机床可操作集合中的任务整体离交货期的远近。( 4 ) 平均惩罚率肜平均惩罚率矿= 至磲篙篆吕要需付川u _ lp 八夕u ，| 工分烈平均惩罚率反应了机床可操作集合中惩罚率的平均大小。2 ) 输出层输出层神经元数目决定于所使用的调度规则数目。本章选用3 种典型的调度策略，相应的，输出层神经元数目有3 个。2 9北京交通大学硕十学位论文( 1 ) w s p t ( w e i g h t e ds h o r t e s tp r o c e s s i n gt i m ef i r s t ，加权最短加工时间优先)m s p 巧j = 兰( 4 4 )p qw s p t 越大，操作的优先权越高。( 2 ) w s l a c k ( w e i g h t e dl e a s ts l a c kf i r s t ，加权最小松弛时间优先)d i 一- 一t p 幻w s l a c k u2 2w s l a c k 越小，操作的优先权越高。( 3 ) e d d ( e a r l i e s td u ed a t ef i r s t ，最早交货期工件优先)交货期越小，操作优先权越高。4 4基于规则的人工神经网络调度仿真在应用前述人工神经网络进行动念调度仿真前，有两个问题需要解决：( 1 ) 学习样本的获取；( 2 ) 隐层神经元个数的确定。4 4 1学习样本的获取( 4 5 )由于人工神经网络是有教师学习过程，所以提供一套准确可靠的训练样本可以获得较稳定的神经网络映射模式。神经网络代表了输入与输出问复杂的非线性映射，有一定的输入就有一定的输出。反过来，有一定的输出必然有一定的输入。所以，我们可以根据一些静态调度算法计算出调度问题的近似最优解，求得此时神经网络的输入状态参数，并计算此时的调度规则，这样我们就获得了神经网络的一套学习样本。s h i j i ec h e n 在文献 4 4 】中对不同任务惩罚权重互不相同的调度问题进行了分析，给出了一个基于多因素的调度规则m f ，试验证明在大多数情况下m f 调度规则比w s p t ，e d d ，f c f s 调度规则都要有效。在文献 4 4 1 中s h i - j i ec h e n 给出了一个例子，如表4 2 所示。表4 - 2 文献 4 4 中的例子t a b l e4 - 2e x a m p l ef r o ml i t e r a t u r e 【4 4 】基于规则推理的动态实时调度表中m 表示机床设备，此问题的目标是最小化延期损失。设这5 个随机任务在某天很短时间内时到达，对上面例子运用遗传算法进行调度，结果如图4 5 所示。m l!l!l ! i m 2 ! 二二三二二 二：三：二二二 二二二二二二】二! 二 一m j 团一 卫 二二二二 二二工j 一- - - - j 一- - t - - - - - - - - - - - - - - - - - - - - i - - - - - - - - - - - - - - - - - - - - - - - j - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 】- - - - - - - - - - - - - - - - - - - - - l - - - - - - - - - - - - - - - - - - - - 】- - - - - - - - 一一一51 01 52 02 53 0图4 5 应用遗传算法求解结果的甘特图f i g u r e4 5g a n t tc h a r tc o m p u t e db yg e n e t i ca l g o r i t h m下面，我们就根据这个结果来计算相应的神经网络的输入与输出，作为人工神经网络的学习样本。其中输入x = n ，秒，丁，w ，输出y = w s p t ，w s l a c k ，e d d 。输出向量中各分量为：f o ，若调度规则不谶咒2 1 1 ，若调度规则选用咒( 1 ) 对于m l ：。在t = 0 时刻，1 1 可加工集合为 4 ，无需进行调度，直接加工任务4 。在t = 8 时刻，搬1 可加工集合为 1 ，2 ，3 ，n = 3 ，0 = - 1 8 8 9 ，t = - i ，w = 1 3 3 3 ，即x = 3 ，1 8 8 9 ，- 1 ，1 3 3 3 ；此时w s p t = o 2 ，0 2 8 6 ，0 2 ，w s l a c k = 2 ，- 2 5 ，0 ，e d d = 1 5 ，1 3 ，1 7 。由上述调度结果可知，在实际调度时选择任务2 优先加工。然而，按三个规则都应该选择任务2 ，则选择差距最大的一个规则，即认为w s l a c k 规则最合适，所以y = 0 , 1 ，0 。在t = 1 5 时刻，m l 可加工集合为 1 ，3 ) ，n = 2 ，0 = - 5 ，r = 一6 ，w = i ，即x = 2 , 5 ，一6 ，1 ) ；此时w s p t = o 2 ，0 2 ，w s l a c k = - 5 ，- 7 ，e d d = 1 5 ，1 7 ) 。由上述调度结果可知，在实际调度时选择任务1 优先加工，只有按e d d 规则才能选择任务1 ，所以y = 0 , 0 ，1 l 。3 l北京交通大学硕+ 学位论文在t = 2 0 时刻，m l 可加工集合为f 3 ，无需进行调度，直接加工任务3 。( 2 ) 对于m 2 ：在t = 0 时刻，m 2 可加工集合为 1 ，2 ，5 ) ，n = 3 ，0 = 0 9 4 7 ，t = 2 ，w = 1 3 3 3 ，即x = 3 , 0 9 4 7 ，2 ，1 3 3 3 ；w s p t = o 5 ，0 3 3 3 ，0 1 ) ，w s l a c k = 5 ，- 1 5 ，0 4 ，e d d - - 1 5 ，1 3 ，1 9 。由上述调度结果可知，在实际调度时选择任务1 优先加工，而只有按w s p t才选择任务1 ，所以y = 1 , 0 ，0 j 。在t = 2 时刻，m 2 可加工集合为 2 ，5 l ，n = 2 ，0 = - 0 9 4 1 ，丁= 1 5 ，w = i 5 ，即x = 2 ，0 9 4 1 ，- 1 ，5 ，1 5 ；w s p t = o 3 3 3 ，0 1 ) ，w s l a c k = - 2 5 ，2 ) ，e d d = 13 ，19 ) 。由上述调度结果知，在实际调度时选择任务2 优先加工，而按三个规则都应该选择任务2 ，则选择差距最大的一个规则，即认为适应w s l a c k 规则，所以y = o ，l ，0 。在t = 8 时刻，m 2 可加工集合为 5 j ，直接加工任务5 。在t = 1 8 时刻，m 2 可加工集合为 4 l ，直接加工任务4 。( 3 ) 对于机床m 3 ：在t = 0 时刻，m 3 可加工集合为 3 l ，直接加工任务3 。在t = l 时刻，m 3 可加工集合为空。在t = 2 时刻，m 3 可加工集合为 1 l ，直接加工任务l 。在t = 5 时刻，m 3 可加工集合为空。在t = 8 时刻，m 3 可加工集合为 4 ，直接加工任务4 。在t = 1 6 时刻，m 3 可加工集合为 2 ，直接加工任务2 。在对于机床m 3 的调度中，、没有用到人工神经网络的功能，因此并不能根据机床m 3 产生训练样本。综上所述，我们得到了如表4 3 所示的4 个训练样本。为了减少训练时间，输出结果中用0 1 和0 9 分别代表0 和1 。表4 3 人工神经网络训练样本t a b l e4 - 3a r t i f i c i a ln e u r a ln e t w o r kt r a i n i n gs a m p l e s3 2基丁规则推理的动态实时调度4 4 2隐层神经元个数的确定由上述可知，本章中的人工神经网络有4 个输入，3 个输出。按照k o l m o g o r o v定理可知，最佳隐层神经元个数在9 个左右。下面运用m a t l a b 进行仿真，确定使均方误差最小的隐层神经元个数。在具体进行人工神经网络学习时，需对输入做归一化处理，将各输入乘以0 1后再输入神经网络。仿真结果如表4 4 所示。表4 _ 4 不同个数隐层神经元时的训练误差t a b l e4 - 4t r a i n i n ge r r o rw i t hd i f f e r e n tn u m b e ro fh i d d e nn e u r o n s不同个数神经元的训练误差曲线如图4 6 所示。磐7 5图4 6 不同数目隐层神经元时的训练误差曲线f i g u r e4 6t r a i n i n ge r r o rc u r v ew i t hd i f f e r e n tn u m b e ro fh i d d e nn e u r o n s北京交通大学硕士学位论文根据表4 4 和图4 - 6 ，我们选择隐层神经元数目为1 0 。4 4 3仿真结果实例对比如前所述，选择隐层神经元个数为1 0 ，则这个人工神经网络是一个4 x1 0 x3的结构。4 4 3 1 人工神经网络的训练根据表4 3 中的训练样本，采用4 xl o x 3 结构的神经网络，训练后的输入一隐层权系数矩阵v =l o 7 2 5 3 一1 5 0 1i2 0 9 1 00 8 2 5 90 6 8 0 0i _ 4 4 4 2 61 9 3 7 6- 1 0 8 3 56 6 1 5 02 1 7 2 97 9 7 6 2- 1 7 1 4 92 5 9 5 5- 8 2 7 9 3 - 0 5 3 4 7i 一0 7 8 0 8 - 1 5 6 6 41 7 7 9 11 5 6 1 5- 0 7 0 2 4隐层输出权系数矩阵w =2 0 7 6 8- 0 7 1 1 51 5 4 6 0- 3 4 7 2 7- 0 6 9 9 l0 0 0 7 40 5 0 7 80 2 6 4 70 8 7 5 3- 1 4 6 5 0学习误差曲线如图4 7 所示。3 1 3 8 81 8 6 1 40 。6 8 5 91 7 9 2 8- 0 3 5 9 8- 1 3 1 8 4 - 0 6 4 5 4 - 0 3 11 4 _ o 3 3 2 81 6 0 8 23 1 5 3 02 7 8 1 0l ，5 6 2 63 0 4 2 9- 1 2 3 2 92 2 9 9 61 5 6 8 40 5 0 4 41 1 0 6 80 1 1 0 l- 6 5 2 0 9- 5 3 7 5 91 9 3 7 67 0 0 9 1- 4 5 8 9 92 7 6 5 51 6 9 7 10 0 7 8 11 3 1 4 2- 3 5 4 9 7_ 4 2 6 8 01 6 9 8 4- 3 3 0 3 12 9 4 6 7一o 2 0 2 1- 3 9 8 4 7- 2 6 2 3 21 6 1 9 3- 3 4 5 7 31 7 7 9 8基于规则推理的动态实时调度：嘲蝼粪迭代蓝线迭代次数一0 )，一一一。；、j l ，：j | ：f 。一”一? 。s - ? “僦图4 7 学习误差曲线f i g u r e4 - 7l e a r n i n ge r r o rc u r v e4 4 3 2 利用人工神经网络进行动态调度在文献 4 7 中给出了个例子【翎，目标同样是最小化延期损失，如表4 - 5 所示。表4 - 5 文献【4 7 】中的例子t a b l e4 - 5e x a m p l ef r o ml i t e r a t u r e 【4 7 】，打jm 2在文献 4 7 】中，运用a t c 规则对上述问题进行调度排序，结果如图4 8 所示。o51 01 5 习2 02 5图4 - 8 文献 4 7 q h 问题的a t c 规则调度结果f i g u r e4 8r e s u l t so fp r o b l e mi nl i t e r a t u r e 【4 7 】b ya t cr u l e3 5北京交通大学硕士学位论文延期损失为：1 x ( 2 4 2 4 ) + 2 x ( 2 6 1 8 ) + 2 x ( 2 2 1 6 ) = 1 6 + 1 2 _ 2 8 。下面将运用本章提出的人工神经网络方法对本例进行调度求解。在t = 0 时刻：肌l 的可加工集合为空( 因任务1 的准备时间为5 ) ，m 2 的可加工集合为空，m 3 的可加工集合为 2 ，3 。对于m 3 ，- 2 ，0 = 0 5 ，t = 2 ，w = 2 ，即神经网络此时的输入为彳= 2 , 0 5 ，2 ，2 。此时神经网络输出为y = o 9 9 1 7 ，0 2 0 4 6 ，0 0 0 0 0 ，根据输出结果选择w s p t 规则。在任务2 和3 中，2 的优先级要高。所以机床m 3 选择任务2 加工。在t = 4 时刻：m l 的可加工集合为 2 ) ，选择任务2 加工；聊2 的可加工集合为空；m 3 的可加工集合为 3 ，选择任务3 加工。在t = 9 时刻：m l 的可加工集合为 1 ，选择任务l 加工，m 2 的可加工集合为 2 ，3 ) ，m 3 的可加工集合为空。对于m 2 ，- 2 ，8 = - i ，t = o ，w = 2 ，即神经网络此时的输入为x = 2 ，1 ，0 ，2 。此时神经网络的输出为y = o 11 4 7 ，0 9 9 9 6 ，0 0 0 0 0 ) ，根据输出结果，选择w s l a c k 规则，2 和3 中，w s l a c k = 1 5 ，1 5 l ，任务3 的优先级高，故选择任务3 加工。在t = 1 2 时，m l 的可加工集合为空，m 2 的可加工集合为 2 ，选择任务2 加工，m 3 的可加工集合为空。在卢1 4 时刻，埘l 的可加工集合为 3 ，选择任务3 加工，m 2 的可加工集合为空，m 3 的可加工集合为空。在户1 8 时刻，m 2 的可加工集合为 1 ，选择任务1 加工，m 3 的可加工集合为空。在f = 2 8 时刻，m 3 的可加工集合为 1 ，选择任务l 加工。动态调度结果如图4 9 所示。一m l ：二 二工二二二二= 二二三二二m 2 厂百丁一一一丁一。t 一一r m 3 二二 二二j jl!三!o51 01 52 02 53 0图4 9 本章人工神经网络动态调度结果f i g u r e4 9d y n a m i cs c h e d u l i n gr e s u l t sb ya r t i f i c i a ln e u r a ln e t w o r k各个任务的延期损失如表4 6 所示。3 6基丁规则推理的动态实时调度表4 6 各个任务的延期损失t a b l e4 6d e l a yp e n a l t i e s延期损失为8 + 0 + 1 0 = 1 8 。可见，用本算法的延期损失明显低于