（机械电子工程专业论文）基于逻辑网的知识表示、推理、学习及其在fms调度中的应用.pdf

华申科技大学博士学位论文 摘要 厂投入实际运行的柔性制造系统( f m s ) 广泛采用规则调度方法完成生产运行 控莉，但规则调度不能得到最优解，在很多情况下甚至无法保证满意解，主要原 因在于：缺乏有效的调度规则选择方法，凭经验或仿真往往导致调度规则选择不 当，使调度系统性能下降；规则调度是一个多级决策过程，各决策点一般依据时 间空间局部信息进行决策，并且无法预测当前决策对系统全局性能的影响：缺乏 调度目标函数和必要的优化控制手段。适应规则调度( a d a p t i v es c h e d u l i n g ) 根据 制造系统当前运行状态选择合适调度规则，是提高规则调度系统性能的一种有效 方法，但调度知识获取是其瓶颈技术。7 本文以广泛应用的规则调度为对象，针对 调度知识表示、推理和获取瓶颈问题，研究了基于逻辑网( l o g i c a ln e t w o r k ) 的 调度知识表示、综合推理技术，提出了不可扩展d n f ( d i s j u n c t i v en o r m a lf o r m ) 递增归纳学习模型，研究了相应的递增学习算法，用于调度知识的递增归纳学习。 结合规则调度系统，研究了基于状态，性能反馈的规则调度原理和实现方法，研究 了工艺规划柔性评价及多工艺规划中操作优先级判据，分别从反馈控制和系统运 行柔性两个角度改进了现有规则调度方法。上述研究成果对于提高规则调度系统 性能具有重要的理论意义和实践意义。本文主要研究内容和取得的研究成果表现 在以下几个方面。 ( 1 ) 提出了一种逻辑网络模型并用于适应调度知识表示，该模型具有符号模型 和连接模型的主要优点，具有坚实的数学基础、显式( e x p l i c i t ) 知识表达方式、 并行运算能力，且易于处理变量绑定( v a r i a b l eb i n d i n g ) 问题。 ( 2 ) 研究了基于逻辑网的综合推理方法，能同时支持演绎推理( 直接推理与反 证法) 、a b d u c t i o n 推理和部分推理( p a r t i a lr e a s o n i n g ) ，有效解决了调度知识和 观测事实不完备条件下的推理问题。 ( 3 ) 提出了不可扩展d n f 递增归纳学习模型，研究了基于该模型的递增归纳学 习算法，证明了递增学习过程中，该模型的不可扩展性，并将该算法用于调度知 识的递增归纳学习。 ( 4 ) 分析了制造系统运行状态、运行性能指标，研究了影响系统运行性能的关 键因素，提出并初步建立了基于状态，性能反馈的规则调度原理和两种实现方法： 迭代优化调度和学习调度。仿真试验结果表明，该方法能有效提高规则调度系统 的运行性能。 ( 5 ) 从制造系统运行柔性角度出发，研究了多工艺规划柔性及其度量方法，提 一_ _ _ _ _ 一 华中科技大学博士学位论文 出一种操作柔性评价准则，解决了多工艺规划中加工操作优先级排序问题，并用 于生产调度，提高了制造系统运行柔性。声 关键词：布尔代数、知识表示、自动推理、机器学习、柔性制造系统、生产调度、 规则调度 华中科技大学博士学位论文 a b s 仃a c t af 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 ) c o n s i s t so fc n cm a c h i n i n gt o o l s ，a na u t o m a t i c a l l y m a t e r i a lh a n d l i n gs y s t e ma n dac o m p u t e rc o n t r o ls y s t e m ac n cm a c h i n et o o li sc a p a b l eo f p r o c e s s i n gm u l t i p l eo p e r a t i o n sa n daf m si s o r d i n a r yu s e dt op r o d u c em u l t i p l ep r o d u c t sw i t h m i d d l e s m a l lv o l u m e t h e s em a k et h em a t e r i a lf l o wi naf m se v e nm o r ec o m p l e xt h a nw h i c hi na l l o r d i n a r yj o b s h o p s c h e d u l i n gf m s t h u sb e c o m e s e x t r e m e l ys o p h i s t i c a t e d t h e r e f o r em o s to ff m s s r u n n i n gi ni n d u s t r i a le n v i r o n m e n ti ss c h e d u l e du s i n gd i s p a t c h i n gr u l e s n l ea d v a n t a g e so f r u l e b a s e d s c h e d u l i n gc o m e f r o mi t ss i m p l i c i t y h o w e v e rr u l e b a s e ds c h e d u l i n gc a nn o tg u a r a n t e et h eo p t i m a l s o l u t i o n a c t u a l l yi nm o s ts i t u a t i o n si tc a nn o te v e np r o v i d es a t i s f y i n gs o l u t i o n s t h em a j o rr e a s o n s a r e ：( 1 ) t h e r ei sn oe f f i c i e n tw a y t os e l e c tas u i t a b l ed i s p a t c h i n gr u l ef o ra p a r t i c u l a rm a n u f a c t u r i n g s y s t e mb e i n gs c h e d u l e d t h eo p e r a t i o n a lp e r f o r m a n c eo f t h em a n u f a c t u r i n gs y s t e md e g r a d e sd u et o u n s u i t a b l es e l e c t i o no fs c h e d u l i n gr u l e ( s ) ( 2 ) r u l e - b a s e ds c h e d u l i n gi s e s s e n t i a l l yam u l t i l e v e l d e c i s i o np r o c e d u r e u s u a l l yt h ed i s p a t c h i n gr u l e sa r et e m p o r a l l ya n ds p a t i a l l yl o c a l ，r e q u i r i n go n l y t h ei n f o r m a t i o na v a i l a b l ea tt h ep r e s e n ta n da tt h ed e c i s i o n - m a k i n gl o c a t i o n t h e vd on o tt r yt o p r e d i c t 也ef u t u r e t h u st h e yc a l l n o tp r e d i c tt h ei n f l u e n c e so ft h ec u r r e n td e c i s i o nt ot h et o t a l p e r f o r m a n c e o ft h e m a n u f a c t u r i n gs y s t e m ( 3 ) r u l e - b a s e ds c h e d u l i n gi s c o m m o n l y l a c ko f s c h e d u l i n go b j e c t i v ef u n c t i o na n d l a c ko f e f f i c i e n tf e e d b a c kc o n t r o ll o o p ，t h u si tc a nn o to p t i m i z et h e p r o d u c t i o np r o c e d u r e a c c o r d i n g t ot h e o p e r a t i o n a l s t a t e sa n d p e r f o r m a n c e o fa p a r t i c u l a r m a n u f a c t u r i n gs y s t e m a d a p t i v es c h e d u l i n gs e l e c t sas u i t a b l er u l ea c c o r d i n gt ot h ec u r r e n ts t a t e so f t h em a n u f a c t u r i n gs y s t e mt h u si tc a l li m p r o v et h ep e r f o r m a n c eo fr u l e b a s e d s c h e d u l i n gs y s t e m s t h eb o t t l e - n e c kt e c h n i q u el i m i t i n gt h ea p p l i c a t i o n so ft h ea d a p t i v e s c h e d u l i n gi s i t s k n o w l e d g e a c q u i r e m e n t t oo v e r c o m e t h ea b o v e s h o r t c o m i n g so f r u l e - b a s e ds c h e d u l i n g ，t h i sd i s s e r t a t i o ns t u d i e s t h ek n o w l e d g er e p r e s e n t a t i o n ，i n f e r e n c ea n di n d u c t i v el e a r n i n gf o ra d a p t i v e s c h e d u l i n g as t a t e p e r f o r m a n c ef e e d b a c ks c h e d u l i n gs c h e m ei sp r o p o s e dt oi m p r o v et h ep e r f o r m a n c eo fr u l e b a s e d s c h e d u l i n gs y s t e m s ac r i t e r i o ne v a l u a t i n go p e r a t i o n a lf l e x i b i l i t yf o rm u l t i p l ep r o c e s s i n gp l a n si s a l s os t u d i e d ，w h i c he n h a n c e st h ea b i l i t yr e a c t i n gt ou n p r e d i c t e de v e n t sf o rs c h e d u l i n gs y s t e m s t h e m a j o r c o n t r i b u t i o n so f t h ed i s s e r t a t i o nc a l lb es u m m a r i z e da sf o l l o w s 1 an e w k i n do f n e t w o r k m o d e l c a l l e d l o g i c a l n e t w o r k i sp r e s e n t e d t or e p r e s e n ta d a p t i v es c h e d u l i n g k n o w l e d g e t h el o g i c a ln e t w o r ki n t e g r a t e st h em a j o ra d v a n t a g e so fs y m b o l i ca n dc o r m e c t i o n i s t m o d e l s i tr o o t so nt h es o l i dm a t h e m a t i c a lf o u n d a t i o nt h u si t si n f e r e n c ep r o c e d u r ei ss t r i c ta n dt h e i n f e r e n c er e s u l t s a ”b e l i e v a b l e i t e x p r e s s e sk n o w l e d g ee x p l i c i t l y a n da l ln e u r o n s o p e r a t e s i m u l t a n e o u s l y i ta l s om a k e st h ev a r i a b l eb i n d i n gp r o b l e me x t r e m e l ye a s y , w h i c hi s i m p o r t a n ta n d d i 衢c u l tf o rn e u r a ln e t w o r kb a s e di n f e f e n c e 2 h y b r i di n f e r r i n gt e c h n i q u eb a s e do nt h e l o g i c a l n e t w o r ki s s t u d i e da n du s e di n a d a p t i v e s c h e d u l i n g i ts u p p o r t sd e d u c t i o n ( b o t hd i r e c ta n di n d i r e c t ) ，a b d u c t i o na n dp a r t i a lr e a s o n i n g t h i si s n i 华中科技大学博士学位论文 m e 血ia n dn e c e s s a r yb e c a u s et h es c h e d u l i n gk n o w l e d g ei so r d i n a r yi n c o m p l e t ea n dt h eo b s e r v e d f a c t sa r ei n s u f f i c i e n t 3 i n d u c t i v el e a r n i n gi se s s e n t i a l l yd i v i d e di n t ot w op h a s e s ：l e a r n i n ga n dg e n e r a l i z a t i o n t h ea i m o f l e a r n i n g i st or e c o r dt r a i n i n gi n s t a n c e se x a c t l y , w h i l et h eg e n e r a l i z a t i o ni s t oa b s t r a c tf r o mt h e i n s t a n c e ss oa st oo b t a i nm o r ee s s e n t i a la n dm o r eu n i v e r s a lc o n c l u s i o n s i nt h er e s e a r c ha r t i c l e s p u b ls h e d ，h o w e v e r , t h et w op h a s e so f i n d u c t i v el e a r n i n ga r eo r d i n a r yb o u n dt o g e t h e r ；t h a ti s ，t h e l e a r n i n gp r o c e s si t s e l fi s ag e n e r a l i z a t i o np r o c e s s f o re x a m p l e s ，t h ef a n m u sa qa l g o r i t h m ，i d 3 a i g o r i t h ma n dv a r i o u si m p r o v e m e n t so fa q a n d1 d 3f a l li n t ot h ec a t e g o r y t h i si n d u c t i v el e a r n i n g s c h e m ei sc a l l e dg e n e r a l i z e dl e a r n i n g s u c hal e a r n i n gs c h e m em a y r e s u l ti np r o b l e m sw h e nu s e di n i n c r e m e n t a li n d u c t i o n f i r s lg e n e r a l i z a t i o ni sa l lo p e r a t i o nt h a ti n t r o d u c e sl e a r n i n ge r r o r s f o rt h e i n c r e m e n t a ll e a r n i n g , n e we p o c ho f l e a r n i n gi sb a s e do nt h eg e n e r a l i z e dr e s u l t so f l a s tl e a r n i n ge p o c h i ts t a r t sw i t ht h o s et h a th a v es o m el e a r n i n ge r r o r s m o r e o v e r , t h en e we p o c ho fl e a r n i n gw i l ia i s o i n t r o d u c en e wl e a r n i n ge r r o r ss i n c ei ti t s e l fw i l lp e r f o r mt h eo p e r a t i o no fg e n e r a l i z a t i o nd u r i n g l e a r n i n gp r o c e s s t h e r e f o r , i n c r e m e n t a ll e a r n i n gt h a ta d o p t sg e n e r a l i z e dl e a r n i n gs c h e m ei s s u c ha p r o c e s s t h a ta c c u m u l a t e sl e a r n i n ge r r o r s t h i sw i l lc e r t a i n l yd e c r e a s et h ea c c u r a c yo f l e a r n i n g r e s u l t s s e c o n d ，g e n e r a l i z e dl e a r n i n gs c h e m eu s e di n c r e m e n t a l l ym a y l e a dt oc o n c e p t u a li n c o n s i s t e n c yo v e r t r a i n i n gi n s t a n c e s a l t h o u g ht h el e a r n i n gr e s u l ti s c o n s i s t e n tw i t ht h et r a i n i n gi n s t a n c e st h a th a v e b e e na l r e a d yl e a r n e d ，t h e ym a yc o n f l i c tt ot h en e wt r a i n i n gi n s t a n c e sa v a i l a b l ei nt h ef o l l o w i n g l e a r n i n ge p o c h s o n eo ft h em a j o rp r o b l e m su n d e rt h ei n c r e m e n t a ll e a r n i n g i st om a i n t a i nt h e c o n s i s t e n c yo fl e a r n i n gr e s u l t so v e rt h et r a i n i n gi n s t a n c e s t h ea b o v et w op r o b l e m sa r eb o t hr e l a t e d t ot h eg e n e r a l i z e dl e a r n i n gs c h e m e t h i sd i s s e r t a t i o np r e s e n t san e wk i n do fi n c r e m e n t a ll e a r n i n g m o d e l ，w h i c hi sc a l l e dn o n e x p a n d a b l ed i s j u n c t i v en o r m a l f a r m ( n e d n f ) w ef i r s ti n t r o d u c et h e d e f i n i t i o no fn e d n fa n de x p l o i th o wt h en e d n fc a nb eu s e d 部a ni n c r e m e n t a ll e a r n i n gm o d e l t h e nw ed i s c u s st h ep r o p e r t i e so fn e d n fi nd e t a i l s b a s e do nt h ep r o p e a i e s ，w ed e v e l o pa n i n c r e m e n t a ll e a r n i n ga l g o r i t h m ，w h i c hd i v i d e st h el e a r n i n gp r o c e s si n t ot w op h a s e s ：l e a r n i n ga n d g e n e r a i i z a t i o n t h el e a r n i n gp r o c e s si s t or e c o r dt h et r a i n i n gi n s t a n c e se x a c t l ya n ds i m p l i f yt h e l e a r n i n gr e s u l t s t h i si sc a l l e da c c u r a t el e a r n i n ga n dt h el e a r n i n gr e s u l ti sc a l l e da c c l d r a t ec o n c e p t t h el e a r n i n gp r o c e s se m p h a s i z e st h el o g i c a le q u i v a l e n c yb e t w e e nl e a r n i n gr e s u l t sa n dt r a i n i n g i n s t a n c e s w h e nl e a r n i n gi s c o m p l e t e d ，g e n e r a l i z a t i o np r o c e s s s t a r t sa n d p r o d u c e sg e n e r a l i z e d c o n c e p t t h el e a r n i n gs y s t e mk e e p sb o t ht h ea c c u r a t ec o n c e p ta n dg e n e r a l i z e dc o n c e p t w h e nn e w t r a i n i n g i n s t a n c e sa r ea v a i l a b l e n e we p o c ho fl e a r n i n gs t a r t sw i t ht h ea c c u r a t e c o n c e p t t h e g e n e r a l i z a t i o np r o c e s sb e g i n s a i d e rt h e l e a r n i n gp r o c e s s i s c o m p l e t e d b e c a u s eo ft h el o g i c a l e q u i v a l e n c yb e t w e e na c c u r a t ec o n c e p ta n dt r a i n i n gi n s t a n c e s ，t h ep r o p o s e di n c r e m e n t a ll e a r n i n g m e t h o dc a nm a i n t a i nt h ec o n s i s t e n c yo v e ra l lt h e t r a i n i n gi n s t a n c e s a n dh a s h i g h e rl e a r n i n ga c c u r a c y 4 s t a t e p e r f o r m a n c e f e e d b a c ks c h e d u l i n gp r i n c i p l ei s p r o p o s e df o rr u l e b a s e ds c h e d u l i n g t w o d i f f e r e n ts c h e d u l i n gs c h e m e sa r es t u d i e d 1 1 1 e ya r ei t e r a t i v e l y o p t i m a ls c h e d u l i n ga n dl e a r n i n g 华中科技大学博士学位论文 s c h e d u l i n g b o t h c a l li m p r o v et h ep e r f o r m a n c eo f r u l e - b a s e ds c h e d u l i n gs y s t e m s 5 f l e x i b i l i t y i so n eo ft h em o s ti m p o r t a n ta t t r i b u t e s o ff m s s i n c r e a s i n gt h e f l e x i b i l i t y o f m a n u f a c t u r i n gs y s t e m sw i l li m p r o v et h eo p e r a t i o n a lp e r f o r m a n c e s t h i s d i s s e r t a t i o ns t u d i e st h e m u l t i p l ep r o c e s s i n gp l a n sa n dt h e i rf l e x i b i l i t ye v a l u a t i o n aq u a n t i t a t i v em e a s u r ei sp r o p o s e dt o e v a l u a t et h ep r o c e s s i n gp l a nf l e x i b i l i t y f u r t h e r m o r eac r i t e r i o ni sp r e s e n t e dt op r i o r i t i z ee a c h o p e r a t i o n , w h i c hc a nb eu s e da so n eo ft h ed i s p a t c h i n gr u l e s s oa st oe n h a n c et h eo p e r a t i o n a l f l e x i b i l i t yo f t h em a n u f a c t u r i n gs y s t e m s ，t oi m p r o v es y s t e mp e r f o r m a n c e s ，a n dt oe n l a r g et h ea b i l i t y r e s p o n d i n gt ou n p r e d i c t a b l ee v e n t s k e yw o r d s ：b o o l e a na l g e b r a , k n o w l e d g er e p r e s e n t a t i o n ，a u t o m a t i ci n f e r e n c e ，m a c h i n el e a r n i n g , f l e x i b l em a n u f a c t u r i n g s y s t e m sf f m s ) ，p r o d u c t i o ns c h e d u l i n g ，r u l e b a s e ds c h e d u l i n g v 1 i 课题来源 1 绪论 本学位论文得到下列科研项目资助 国家自然科学基金重大项目 “支持产品创新的先进制造技术中的若干基础研究”( 资助号5 9 9 9 0 4 7 0 ) 一 课题l “现代制造系统的理论、建模及运行试验研究” 1 2 选题背景、目的和意义 制造是人类最基本的生产活动之一，制造自动化是人类提高劳动生产率、提 高产品质量、降低生产成本、缩短生产周期、提高企业市场竞争力的重要手段。 从三十年代到五十年代，人们主要建立由机械式或液压式的自动车床、组合机床 或专用机床组成的自动生产线。这类生产线生产效率高，具有固定的生产节拍， 适用于单一品种大批量生产模式，故称为刚性生产自动线。随着刚性生产自动线 的推广普及，人们发现单一品种大批量生产只占整个制造活动的1 5 2 5 ，而 中、小批量生产占整个制造活动的7 5 8 5 t 1 2 i 。如何提高中、小批量生产的劳 动生产率，成为人们关注的焦点。另一方面，从六十年代开始，计算机技术得到 飞速发展和广泛应用，计算机数控机床( c n c 机床) 在制造自动化领域开始逐步 取代机械式或液压式自动机床。c n c 机床一般具有多种工序能力，通过改变加工 程序，c n c 机床可以方便地完成不同加工操作，非常适合多品种中、小批量产品 生产，因而被称为柔性加工设备【l 】。柔性加工设备能完成多种工序加工，有效减 少了机床上部分非切削时间和部分工序间零件的搬运、存放时间，提高了制造系 统的生产效率。但是，进一步研究发现，零件在机床上的加工时间仅占零件全部 生产时间的5 ，毛坯和半成品的运输、存放、准备时间占零件全部生产时间的 9 5 坩u j 。为进一步提高劳动生产率，缩短零件的生产周期，提高设备利用率，必 须对零件整个生产过程的各个环节实现自动化，如工件存取、装卸、搬运自动化， 刀具输送、交换、管理自动化等，由此，产生了柔性制造系统。 柔性制造系统f l , 3 1 ( f m s ：f l e x i b l em a n u f a c t u r i n gs y s t e m ) 是由若干c n c 设备、 自动物料储运系统( m h s ：m a t e r i a lh a n d l i n gs y s t e m ) 、计算机控制系统组成的自 动化生产系统，它能根据生产计划和生产品种的变化迅速调整生产，适合多品种 一 华中科技大学博士学位论文 中、小批量生产。 与一般制造系统相比，f m s 系统组成与运行模式具有以下特点。 ( 1 ) f m s 中普遍采用以c n c 机床为主的加工设备，它们一般具有多种工序能力， 可以完成多种加工任务。 ( 2 ) f m s 一般以多品种中、小批量生产方式为主，能实现多种产品( 零件) 的 混合加工。 ( 3 ) f m s 具有自动物料储运系统，零件固定在标准托盘上，能实现毛坯、在制 零件的快速传递，提高了零件的输送速度，降低了零件的输送成本。 ( 4 ) f m s 由计算机集中控制，可完成生产调度控制和加工程序自动、快速传送。 f m s 的这些特点，使得f m s 的物流与一般制造系统有很大的区别，主要表 现在： ( 1 ) 零件的加工路径( r o u t i n g ) 可能各不相同。 ( 2 ) 零件可能存在加工路径柔性( r o u t i n gf l e x i b i l i t y ) 和可重入性( r e e n t r a n c e ) ( 同一零件多次访问同一加工设备) 。当多台设备可完成同一加工操作时，不同 设备完成该操作所需时间可能不同。 ( 3 ) 随时可能有调度计划外的急件( r u s hj o b ) 进入f m s 且需要尽快加工。 ( 4 ) 自动、快速的物料储运系统与计算机通信、控制系统为多工艺规划的使用 创造了条件。 f m s 中物流过程的上述特点是f m s 柔性的集中体现，它们增加了f m s 运行 效率，提高了f m s 对不可预见因素的响应能力。与一般制造系统相比，f m s 具 有下列无可比拟的优点【i 3 1 ： ( 1 ) 生产周期缩短 以吉丁刘易斯弗雷泽公司f m s 为例，一批零件用传统方式加工需2 0 0 小时，用独立的c n c 机床加工需8 0 小时，而用f m s 加工则只需2 0 小时。 ( 2 ) 主要设备利用率提高 在典型情况下，f m s 中一组机床的产量是单机作业车间环境下用相同数目机 床产量的3 倍。 ( 3 ) 在制品库存减少 在相同设备条件下，f m s 与常规加工车间相比，在制品可减少8 0 。 ( 4 ) 生产具有柔性 能快速响应生产条件的变化，由于f m s 具有柔性，不需要硬件结构的变化 即可用于生产不同产品，临时增加的生产任务也可及时投入生产。 2 华中科技大学博士学位论文 。 由于f m s 具有上述优点，世界各主要经济强国均投入巨资进行f m s 研发、 推广工作。据统计，自1 9 6 7 年英国建立世界上第一个柔性制造系统以来，f m s 一直呈加速发展趋势。1 9 8 0 年投入运行的f m s 约2 0 0 套，1 9 8 5 年达5 0 0 多套， 而到1 9 9 0 年，各国投入运行的f m s 已达到1 0 0 0 套以上。美国政府甚至将柔性 制造列入其“国家关键技术计划”( 1 9 9 1 年) 中i i 川。 我国第一套f m s 由北京机床研究所于1 9 8 5 年1 0 月研制成功( j c s f m s - 1 ) 。 1 9 8 7 年以后，在国家的大力支持下，北京第一机床厂，郑州纺织机械厂，上海第 一纺织机械厂，华中科技大学等单位先后从德国、日本、意大利等国家引进了 f m s 。此后，在原国家机电部、国家重点科技攻关项目和国家8 6 3 高技术计划自 动化领域的大力支持下，我国f m s 的研究和应用推广工作得到快速发展。1 9 8 8 年，北京机床研究所全部自行开发、研制成功了j c s f m s 2 型柔性制造系统，标 志着我国具有自主开发f m s 的能力。 需要指出的是：f m s 的优点是潜在的l z , 3 l 。单纯地将f m s 硬件设备合理地组 成一个系统，并不一定能取得预期经济效益。作为生产运行控制与过程优化的重 要手段，f m s 生产调度直接影响着f m s 运行性能，是f m s 运行中最重要的一环。 从第一套f m s 诞生至今，f m s 生产调度问题直是企业与学术界关注的焦点之 由于f m s 生产方式的灵活性和物流过程的复杂性，其生产调度对现有调度 理论与实践提出了巨大挑战：传统的基于运筹学的最优化方法，因建模困难或因 模型求解困难，无法有效解决上述f m s 调度问题：在实际中广泛使用的规则调 度又无法满足优化生产的需求；专家系统调度受到知识获取瓶颈的困扰；计算机 仿真方法一般侧重于f m s 模型的评价及简单调度规则的评价。因此，现有调度 方法一般不能直接用于f m s 调度：或虽能应用，但无法获得满意的系统运行性 能。 在此背景下，本文以实际运行f m s 中广泛应用的规则调度为研究对象，针 对调度知识表示、推理和获取问题，研究具有符号模型和连接模型主要优点的逻 辑网络模型，用于调度知识的表示和综合推理；研究复杂问题的递增归纳学习问 题，提出了基于不可扩展d n f 的递增归纳学习模型和递增归纳学习算法，用于 调度知识的学习。上述研究成果可直接用于适应规则调度，具有重要的实践意义； 同时，这些研究成果对于人工智能领域里的知识表示、推理和递增归纳学习问题 的研究，具有重要的理论意义和促进作用。另一方面，结合规则调度系统，研究 华中科技大学博士学位论文 基于状态性能反馈的规则调度原理和实现方法，研究工艺规化柔性评价及多工艺 规划中操作优先级判据，分别从反馈控制和系统运行柔性两个角度改进现有规则 调度方法，对提高制造系统运行性能具有重要的实践意义。 1 3 生产调度概述 1 3 1 生产调度的定义及其复杂性 ， 制造系统的生产调度本质上是一类广泛的约束优化问题，调度问题一般可描 述为在满足一定技术与资源约束的前提下，安排工件的投放顺序，指定各工件的 加工路径、加工开始时间和完成时间，并尽可能满足生产管理者的生产目标刚。 生产调度问题涉及加工设备、被加工工件和调度目标函数，我们称其为调度三要 素( 或生产运行要素) 。 调度问题可以根据这三个要素进行分类。 ( 1 ) 按加工设备分：单机调度、多机调度； ( 2 ) 按工件加工路径分：流水车间( f l o ws h o p ) 调度、单件车间( j o bs h o p ) 调度，可重入( r e e n t r a n t ) 生产调度： ( 3 ) 按调度目标分：单目标调度，多目标调度。 此外，根据事件发生的时间特性可分为确定型调度与随机型调度，根据调度 计划的产生时间和执行时间之间的关系可分为静态调度和动态调度。 制造系统的复杂性、生产任务和调度目标的多样性，决定了生产调度的复杂 性。这种复杂性首先表现为建模难和模型求解难n 3 1 。制造系统是典型的离散事件 动态系统，其异步、并发、冲突等特点很难用传统的数学模型表达，因而无法对 其进行解析分析，进而寻找最优解。生产调度问题虽可以转化为数学规划问题， 但复杂系统的建模需要很高的技巧，而且往往忽略了许多因素，使数学模型与实 际问题相去甚远：另外，除极少数简单调度问题外，绝大多数调度问题都是n p 难题。无法在多项式时间内求解1 。 调度问题的复杂性还表现在系统运行性能评价指标的多样性 7 j o i 。常见的系统 运行性能评价指标有：设备利用率最高、工件延误时间最小、在制工件数最小、 加工时间最短等，这些性能指标从不同侧面反映了制造系统运行情况，其中有些 指标互相冲突，因此在调度过程中，必须针对具体问题综合分析。 制造环境的随机性则在另一个方面增加了调度问题的复杂性。诸如设备故 4 华中科技大学博士学位论文 障、加工时间的波动、原材料短缺、工夹具短缺、生产任务变更等不确定因素， 使调度计划执行期间所面l 临的环境与制定计划时所考虑的环境不一致导致原有 计划无法顺利执行，或导致系统运行性能下降，这时需根据生产现场具体情况对 原计划进行修改，甚至重新制定新的调度计划。 调度问题的复杂性及现实生产对优化调度方案的需求性吸引着大量的研究 者，他们从不同领域提出诸多研究方法，推动调度理论与实践的发展，正如r w c o n w a y 等在( t h e o r y o f s c h e d u l i n g ) ) 一书中