（控制理论与控制工程专业论文）基于改进量子遗传算法的不确定性生产调度方法研究.pdf

r e s e a r c ho nu n c e r t a i np r o d u c t i o ns c h e d u l i n gb a s e do ni m p r o v e d q u a n t u mg e n e t i ca l g o r i t h m b y w a n gx i n g li n b e ( c h a n g s h au n i v e r s i t yo fs c i e n c e t e c h n o l o g y ) 2 0 0 8 at h e s i ss u b m i t t e di np a r t i a ls a t i s f a c t i o no ft h e r e q u i r e m e n t sf o rt h ed e g r e eo f m a s t e ro fe n g i n e e r i n g co n t r o lt h e o r ya n dc o n t r o le n g i n e e r i n g l n c h a n g s h au n i v e r s i t yo fs c i e n c e t e c h n o l o g y s u p e r v i s o r p r o f e s s o rl im a o j u n a p r i l ，2 0 11 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研 究所取得的研究成果。除了文中特别加以标注引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。 本人完全意识到本声明的法律后果由本人承担。 作者签名： 王孑赤飙 日期：加1 年 岁月7 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅。本人授权长沙理工大学可以将本学位 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“4 ”) 作者签名： 工z 击者日期：p ，1 年 箩月 2 1 e l 堪张日呦严乡月2 7 日 摘要 生产调度一直是生产管理中最为重要的环节，良好的调度方案可以 有效地提高企业的生产能力和生产效率。自五十年代以来，人们已对经 典生产调度做了大量的研究，并取得了令人瞩目的进展。然而，实际的 调度过程中，往往存在大量的不确定因素，使得经典调度方案无法正常 执行。因此，分析生产过程中的不确定因素，将其引入调度模型，并研 究一种有效的优化算法进行求解，具有重要的理论价值和实践意义。 当前，不确定性生产调度的优化算法主要有遗传算法、免疫算法、 蚁群算法、微粒群算法等，它们都能解决调度优化问题，但实际优化过 程中往往要耗用大量的时间。本文针对不确定性生产调度，提出采用量 子遗传算法求解，它利用了量子计算的并行特性，具有更为高效的并行 计算能力，且因量子遗传算法采用比特编码而具有更好的种群多样性， 使得种群规模可以很小而不影响算法性能。 论文介绍了生产调度的一些基本情况，重点描述了不确定条件下生 产调度的研究现状，比较了几种优化算法的优缺点，介绍了量子遗传算 法在解决优化组合问题时存在的优势；随后分析了生产调度的不确定因 素，给出相应处理方法，并以模糊数学为基础，建立不确定性生产调度 的模糊模型；接着介绍了量子遗传算法，包括其独特的编码方式、量子 旋转门更新种群的原理，并分析其特点，提出几种局部操作算子，详细 描述了该算法的内容；最后将该算法应用于不确定性生产调度。m a t l a b 仿真实验验证了该算法的有效性。 关键词：不确定性；生产调度；调度模型；量子遗传算法 a bs t r a c t a st h em o s ti m p o r t a n t l i n ki np r o d u c t i o nm a n a g e m e n t ，a b e t t e r p r o d u c t i o ns c h e d u l i n gm e t h o dc a ni m p r o v et h ec a p a c i t ya n de f f i c i e n c yf o r p r o d u c t i o n s i n c et h ef i f t i e s ，a c a d e m i c sh a v ed o n et h em a s s i v er e s e a r c ht o c l a s s i cp r o d u c t i o ns c h e d u l i n g ，a n d i th a sa c h i e v e dr e m a r k a b l e r e s u l t h o w e v e r i nt h ea c t u a lp r o d u c t i o np r o c e s s ，t h e r e a r el o t so fu n c e r t a i n f a c t o r st h a tm a k es c h e d u l i n gs c h e m en o tw o r k i n gp r o p e r l y t h e r e f o r e ，t h e a n a l y s i so f t h eu n c e r t a i n f a c t o r si np r o d u c t i o np r o c e s s ， w h i c hw i l lb e i n t r o d u c e dt ot h e m a t h e m a t i c a lm o d e lo fp r o d u c t i o ns c h e d u l i n g ，i s n e c e s s a r y s t u d y i n ga ne f f e c t i v eo p t i m i z a t i o na l g o r i t h mf o rt h ep r o b l e mh a s i m p o r t a n tt h e o r e t i c a lv a l u ea n dp r a c t i c a ls i g n i f i c a n c e t h et h e s i si n t r o d u c e ss o m eb a s i cs i t u a t i o no fp r o d u c t i o ns c h e d u l i n g ， a n d e m p h a t i c a l l y s u m m a r i z e st h e r e s e a r c hs t a t u so ft h ep r o d u c t i o n s c h e d u l i n gi nt h ec o n d i t i o n so fu n c e r t a i n t y ，a n dt h e nl e a d st ot h ea d v a n t a g e s o f t h e q u a n t u mg e n e t i ca l g o r i t h m b yc o m p a r i n g t h es t r e n g t h s a n d w e a k n e s s e so fs e v e r a lo p t i m i z a t i o na l g o r i t h m s ；s e c o n d l y ，t h e u n c e r t a i n f a c t o r si np r o d u c t i o np r o c e s sa r ea n a l y z e di nd e t a i l ，a n dt h ea p p r o p r i a t e t r e a t m e n t sa r eg i v e n ，a n dt h e nt h ef u z z ym a t h e m a t i c a lm o d e lo fu n c e r t a i n d r o d u c t i o ns c h e d u l i n gi se s t a b l i s h e d ；t h i r d l y ，t h eq u a n t u mg e n e t i ca l g o r i t h m i si n t r o d u c e d ，i n c l u d i n gi t ss p e c i a le n c o d i n g ，t h ep r i n c i p l eo fp o p u l a t i o n u p d a t eb yq u a n t u mr o t a t i o ng a t e s ，a n di t s c h a r a c t e r i s t i c si sa n a l y z e d ，t h e n t h ea u t h o rp r o p o s e ds e v e r a ll o c a lo p e r a t o r s ，t h es t e p so ft h ea l g o r i t h ma r e a l s og i v e no u t ；a tl a s t ，t h ea l g o r i t h m i su s e dt os o l v et h eu n c e r t a i n p r o d u c t i o ns c h e d u l i n g a tp r e s e n t ，t h e r ea r es o m em a i no p t i m i z a t i o na l g o r i t h m s u s e di n u n c e r t a i n p r o d u c t i o n s c h e d u l i n g ，s u c h a s g e n e t i ca l g o r i t h m ，l m m u n e a l g o r i t h m ，a n tc o l o n ya l g o r i t h ma n ds oo n ，t h e y a l lc a ns o l v et h eq u e s t i o n e f f e c t i v e l y ，b u ti t n e e dt os p e n tal o to ft i m ei nt h e a c t u a lo p t i m i z a t i o n p f o c e s s a c c o r d i n g t oc h a r a c t e r i s t i c s o ft i m ei nu n c e r t a i np r o d u c t i o n p r o c e s s ，t h i st h e s i sp r o p o s e sa n e wq u a n t u mg e n e t i ca l g o r i t h m i th a sm o r e e f f i c i e n t p a r a l l e l c o m p u t i n g c a p a b i l i t i e s b e c a u s e o ft h e p a r a l l e l c h a r a c t e r i s t i c si nt h eq u a n t u mc o m p u t i n g i t a l s oh a sb e t t e rp o p u l a t i o n n _ _ 一 d 1 v e r s l t yf o ri t sq u a n t u mb i t c o d i n g ，s ot h ep o p u l a t i o ns i z ec a nb ev e r v s m a l lb u ti t d o n ta f f e c t a l g o r i t h m ，t h i sp a p e ra l s og i v e ss e v e r a ll o c a l o p e r a t o r st ol m p r o v ea l g o r i t h mp a r t i a ls e a r c h i n g a b i l i t y ，a nt h e nj u m po u to f l o c a lo p t i m u mw e l l t h ei m p r o v e dq u a n t u mg e n e t i ca l g o r i t h mw i l l b eu s e d l nu n c e r t a i np r o d u c t i o ns c h e d u l i n g ，a n dt h es i m u l a t i o nr e s u l t ss h o w t h a tt h e 1 m p r o v e da l g o r i t h mc a na c h i e v e st h ed e s i r e de f f e c te f f e c t i v e l v 1 1 时 毛= e 。= 邶印q ，) ( 3 ) 当i = 2 ，= 1 时 哥= e 。，川，= ( 岛q ，q m 。产妒d ，) ( 4 ) 当i = 2 ， 1 时 茜= m a x 仁。川，e ，) = e 。产，vg ， = 阮- 1 ) v 咏1 ) ，c 酊m - 1 ) v 锩1 ) ，c u v 1 ) v 咏。) 】 ( 5 ) 当i = 3 ，= 1 时 写= m a x e 。，q ，己h m ，一坞) = ( 2 1 9 ) ( 2 2