（机械电子工程专业论文）基于免疫原理的job+shop调度研究.pdf

西北t 业大学博士学亿论文 基于免疫原理的j o bs h o p 调度研究 摘要 j o bs h o p 调度是一类复杂的组合优化难题，有着深刻的实际背景和广阔的应 用前景。目前的调度理论研究对实际调度问题进行了简化处理，忽略了许多必要 的实际因素，离实际应用还存在较大差距。因此，考虑柔性、多目标、多约束、 分布式，研究接近生产实际的j o bs h o p 调度具有重要的理论意义和工程价值。 本文以j o bs h o p 调度为研究对象，以接近生产实际为中心线索，以免疫优 化理论为技术支撑，对j o bs h o p 调度的建模、求解、优化和仿真等关键问题进 行了系统深入的研究和探索。本文的主要研究成果和结论如下： 】提出了适合于j 0 bs h o p 捌皮的建模方法，按照从简单到复杂、逐渐接近 生产实际的主线，依次建立了标准j o bs h o p 调度模型、柔性j o bs h o p 调度模型、 多目标柔性j o bs h o p 调度模型、多约束多目标柔性j o bs h o p 调度模型和分布式 多目标j o bs h o p 调度模型。在剖析实际生产调度的基础上，按照普遍通用的原 则进行抽象提取，采用目标函数、约束条件等数学方法对实际调度的物理形式和 逻辑意义进行描述，采用p e 一网图论理论和面向对象结构化方式对实际调度的 静态特性和动态特性进行刻画。 2 提出了多种有效的j o bs h o p 调度算法，针对不同调度问题的特点和差异， 基于调度模型，依次提出了基于动态评价的免疫遗传算法、免疫模拟退火算法、 多种群双倍体自适应免疫算法、免疫蚁群算法以及基于调度网格的分布式调度算 法。这些免疫调度算法以调度模型为应用背景，以高效调度为原则，以免疫优化 理论为依托，模拟实现了多种免疫机制：包括免疫识别、免疫学习、免疫记忆在 内的免疫应答机制：基于抗体期望繁殖率的免疫选择机制；保证抗体多样性的免 疫调节机制；提高算法收敛速度和防止群体退化的免疫疫苗机秘。实例求解证实 这些算法能够快速收敛，具有较强的调度优化能力，适用于相应的调度问题。 3 根据具体问题具体分析的哲理，提出了灰色关联层次分析等多种多目标 处理策略分别应用于不同调度问题的求解。依据柔性调度包含设备分配和工序 调度两个子问题的本质，采用了分解策略和综合策略两种柔性处理策略。本着简 单有效的原则，探索了将约束条件转化为目标函数和用约束条件对进化解进行过 滤的两层约束处理策略。 摘耍 4 提出了调度网格的概念，基于调度网格提出了分布式调度方法；提出了 单元问调度和单元内调度两级调度策略，确立了分布式j o bs h o p 调度体系框架： 搭建了任务调度系统，构造了调度器；提出了任务调度管理逻辑结构，确立了任 务调度管理过程：提出了基于免疫原理的招投标机制和基于匹配层次图的谈判策 略，搭建了多目标评价体系；实现了局部调度和全局调度协同优化，验证了分布 式j o bs h o d 调度方法的有效性。 5 确定了j o bs h o p 调度求解方法，设计了求解要素：针对单目标j o bs h o p 调度、多目标j o bs h o p 调度、分布式多目标j o bs h o p 调度，采用本文所提相应 调度算法分别进行了求解与仿真；分别以国际标准j o bs h o p 调度算例和企业实 际j o bs h o p 调度案例进行验证与对比，证明模型和算法的有效性。 6 基于本文调度理论，采用先进软件技术，设计开发了j o bs h o p 调度原型 系统，并成功应用于企业生产实践。 关键词：j o bs h 叩调度，免疫原理，免疫算法，建模，仿真，柔性，多目标，多 约束，分布式，调度网格 本论文研究依据教育部博士点基金“基于免疫算法的车间计划调度方法研 究( 2 0 0 4 6 9 9 0 2 5 ) ”选题，并得到国家8 6 3 ，c i m s 基金( 2 0 0 i a a 4 1 2 1 5 0 ， 2 0 0 3 a a 4 1 11 1 0 ) 和国家自然科学基金( 6 9 9 8 4 0 0 4 ) 的资助。 a b s 几i a c i r e s e a r c ho nj o bs h o ps c h e d u l i n gb a s e do ni m m u n ep r i n c i p i e ( p h d d i s s e n a t i o n ) n o r t h w e s t e mp o i ”e c h n i c a lu i l i v e r s i ty ，x i a n ，p r c t l i n a a b s t r a c t j o bs h o ps c h e d u l i n gi so n eo fm o s tc o m p i i c a t e dc o m b i n a t o r i a io p t i m i z a t i o n p m b i c n l sa 1 1 dh a sp r o f b u n dp r a c t i c eb a c k g r o l l i l da 1 1 d 、v i d e 印p l i c a t i o n 士o r e g r o u n d b e c a u s co fi g n o 血gm a i l ya c t u a lc o n 蚰面n t st os i m p l i 】，c o m p u 诅t i o nc o m p l c x i t y ，a t p r c s e ms c h e d u l i n gt h e o r yr e s e a r c hd o e s n ts a t i s 黟t 1 1 ep r a c t i c a l 印p l i c a t i o nd e m a n d n l e r e f o r e ，i t sm o r es i g n m c a i l ti nt h e o r ya 【i dv a i u a b l ei ne n g i n e e r i n gt os t u d yl h ej o b s h o ps c h e d u l i n gc l o s et o t h ep r o d u c c i o np 眦t i c e ，w h i c hi n v o l v e sw i t hn e x i b i l i 哆， m u i t i o b j c c t i v e ，m u l t i c o n s 打a i n ta i l dd j s t r i b u t i n g 1 1 1m ed i s s e r t a t i o i l j o bs h o ps c h e d u j i n gi sr e g a r d c da st h cr e s e a r c ho b j e c t j v e ，a n d t h ec e n t m lc l u ei st oc l o s et ot h ep f o d u c t i o np r a c “c e ，a n dt h et e c l l n o l o g ys u p p o r ej st h e i m l u n eo p t i m i z a t i o nt h e o r y s e v e r a lk i n d so fk e yt e c h n o l o g yo f j o bs h o ps c l l e d u l i n g t l a v eb e e nd e 印i ys t u d i e d ，w h i c ha r em o d e l i n 岛s o j u t i o n ，o p t i m i z a t i o na n ds i m u i a t i o n ， e ta lt h em a i nf e s u l ta n dc o n m b u t i o no f t l l ed i s s e r t a t i o na r 。a sf o l l o w s 1 t h cm o d e j i n gm e t h o d sa r cp u tf o n v a r d a c c o r d i n gt 0t h ep r i m a r yc l u eo f a p p r o a c h i n gt ot h ep r o d u c t i o np r a c t i c e ，s e v e 瞄k h d so fd i f f e r e n tj o bs h 叩s c h e d u l i n g m o d e i sa r es e tu p w h i c ha r ct l l ec l a s s i c a ij o bs h o ps c h e d u l i n gm o d e l ，t h en e x i b l ej o b s h o ps c h c d u l i n gm o d e l ，t 坨m u i t l o b j e c t i v en e x 沌l ej o bs h o ps c h e d u l i n gm o d e l ，t l l e m u l t i c o n s t r a i n cm u j t i o b j e c t i v ef 】e x i b l ej o bs h o ps c h e d u l i n gm o d e la n dt h e d i s t m u t i n gm u l t i - o b j e c t i v ej o bs h 叩s c h e d u l i n g m o d e l a r c r a i i a l y z i n g 血e p r o d u c t i o np r a c t i c e ，t h ed i s s e r t a t i o n sp i c k su pt h ee s s e n c ea c c o r d i n gt ot h eu n i v e r s a l p r i n c i p i e t h ep h y s i c a lf o r r na n dt h el o g i cm e a n i n go fj o bs h o pa i d e p j c t e db yt h e o b i e c c i v e 如n c t i o na n dm ec o n s t r a i n t ，a n dt h es 叫i cc h a r a c t e r i s t i ca n dt h ed y 衄m j c a i c b a f a c t e r i s t i co fj o bs h o ps c h e d u l i n ga r ee x p r e s s e db yt 1 1 ep e t r in e tt h e o r ya n dt 1 1 c o b j e c co r i e n f e ds t n i c t u r e 2 s e v e m ib n d so fe f f e c t u a is c h e d u l i n ga l g o r i t h n l sa r ep u ff o r w a r db a s e do nt h c m o d e la n dt h ec h a m c t e r i s f i co fe a c hk i n do f j o bs h o ps c h e d u l i n g t h e ya r ed y i l 锄i c e v a l u a t i o nb a s e d 曲l m u n ea l g o r i t ， i m m u n es i m u l a t e d锄e a l j n ga l g o r i t l u i l ， m u c o l o n yd i p l o i da d a p t i v ei 衄u n ea l 驴r i m m ，i 哪u n ea n tc o l o n ya l g o r h h ma n d d j s t r i b u t i n gs c h e d u l i n ga l g o r i 山mb a s e do nt h es c h e d u l i n g 酽i d t h e s ea l g o r i t l l m s s m u l a t em a n yk i n d so fi m m u n em e c h a n i s mb yu s i n gt h es c h e d u l i n gm o d e ia st h e 一l 一 阳北| = 业大。￥再十号：付论文 a p p l i c a t i o nb a c k g r o l i i l d ，t h ee 伍c i e n t j ys c h e d u 】i n ga s 1 e 州n c i p l e ，t h ei 叫n u n e o p t i m i z a t i o nt h e o r ya st h eb a s e t h ei l m 叽er e s p o n s em e c h a n i s mi n c l u d e st h e i 皿u n ed e t e c t i o n ，t h ei m m u n ei e a m i n 昏m ei m m u n er e m e m b e r ，e ta 1 t h ei m m u n e s e l e c t i o nm e c h a i l i s mi sb a s e do nt h ea n t i b o d yr e p r o d u c i b i l i t yr a t i oi n v o l v e dw i t ht l l e a n t j b o d ya 伍n i 哼a n dt 1 1 e c o n c e n t m t i o n t h ei m m u n es e l f - a d j u s t i n gm e c h a 血s mi s a d o p t e dt ok e e pd i v e r s i 哆1 1 1 ev a c c i n em e c h 如i s mi su s e dt os p e e dt h ec o n v e r g e n c e a l 】da v o i d 出ec 0 j o n yd e g r a d a t i o n t h ei n s t a n c es j m u l a “0 ne x p e r i m e n t sj n d j c a t em a 士 t l l e s ea l g o r i t h 】sh a v ep o w e r m ls c h e d u l i n go p t i m i z a t j o nc a p a b i l i t ya n dc a nc o n v e r g e q u i c k i y ，a n df i tt h ec o t t e s p o n d i n gj o bs h o ps c h e d u l i n g 3 s e v e r a l “n d so fe f 佗c t u a ls c h e d u l i n gs t r a t e g i e sa r ep u ff o n v a r d a c c o r d i n gt o 山ei d e ao fs p e c j 茹c a 】j ya n a 】y z j n gt b eg i v e np r o bj e m ，s e v e r a lm u l t i o b j e c t i v ed j s p o s a l s t r m e g i e sa r ep u tf o r w a r dt os o l v et 1 1 ec o r r e s p o n d j n gj o bs h o ps c h e d u l i n g ，s u c h 舾 g r d y c o r r e j a “o n a n a i y s i s m c t h o do r i e n c e d s c h e d u l i n g t h en e x i b l ej o bs h o p s c h e d u i i n ge s s e n t i a l l yi n c l u d e st 、v os u b p r o b l e m s ，i e t h ee q u i p m e n td i s t r i b u t i o na 】1 d t 1 1 e0 p e r a t i o ns c h c d u l i n g ，a c c o r d i n g j yt h ed e c o m p o s i t i o ns t r a t e g ya n dt 1 1 ei n t e g r a l i o n s t r a t e g ya r el l s e dt ot r e a tw i t ht h ef l e x i b i l i t yp r o b l e m a c c o r d i n gt ot h ep r i n c i p l eo f s i m p l i f i c a t i o na 1 1 da v a i l a b i l j 哆，t v v o l e v e ic o n s t r a i n td i s p o s a ls t r a t e g ) ，i ss t u d i e d ，w m c h t r a n s f 0 肌st h ec o n s t r a i mi n t ot h eo b j e c t i v em n c t i o na n df i l t e r st h ec a n d i d a t es o l u t i o i l s b yc h ec o n s t m i n tc o n d i t i o n s 4 t h ec o n c 印to fs c h e d u l i n g 鲥di si n j t i a l l yp u tf o 刑a r da n da c c o r d i n g i yt h e d j s t r i b u t i n gs c h e d u l i n gm e t h o di sp u tf o n v a r db a s e do ni t t h et w oi e v e ls c h e d u i i n g s t r a t e g yi sp u tf o r w a r dw h i c hi n v o i v e dw i t i lt 1 1 es c h e d u l i n ga m o n gm a n u f k t u r i n g c e i l sa n dt h es c h e d u i i n gw i 山i nt 1 1 em a l l u f a c t u r i n gc e l l t h es y s t e mf a m eo ft h e d i s t r i b u t i n gj o bs h o ps c h e d u l i n gi se s t a b l i s h e d t h e 诅s ks c h e d u l i n gs y s t e mi ss e tu p a 1 1 dt h es c h e d u l i n gi m p l e m e n ti sc o n s t r u c t e d t h el o g i cs t m c t u r e o ft h et a s k s c h e d u l i n gm a n a g e m e n ti sp u tf b n v a r d 姐dt t l ep r o c e s so ft a s ks c h e d u i i n g m a i l a g e m e n ti sc o n f i n n e d t h em e c h a n i s mo fc h eb i d d i n ga n di n v i t i n gp u b l i cb i d d i n g b a s e do nt h ei m m u n cp r i n c i p l ei sp u tf o n v a r d 锄d 山en e g o t i a t i o ns t r a t e g yb 船e do n t h em a t c h i n gl a y e rc h a r ti sp u tf o n v a r d t h em u l t i 0 b j e c t i v ee v a l u a t i o ns y s t e mi ss e t u pa n ds y n c h r o n o u s l y0 p t i m i z a t i o ni sc 删e do u tb yl o c a ls c h e d u l i n ga n dg l o b a l s c h e d u l i n g t h ev a l i d i t yo ft t l ed i s t r i b u t i n gs c h e d u i i n gm e t h o di su l t i m a t e l yp r o v e d 5 t h es o l v i n gm e t h o do f j o bs h o ps c h e d u l i n gi se s t a b l i s h e da j l dt h ek e ys t e p sa r e d e s i g n e d t h es i n g i eo b j e c t j v ej o bs h o ps c h e d u l i n g ，t h em u l t i - o b j e c t i v ej o bs h o p s c h e d u i i n ga n dt h ed ；s t r j b u t i n gm u l t i o b j e c t i v ej o bs h o ps c h e d u l i n ga r er e s p e c t i v e i y s i m u l a i e da n ds 0 l v e dw i t l lt | l ea l g o r i t h m sp u tf o n v a r d t h ei n t e m a t i o n a lc l a s s i c a lj o b i v a b s r r a c 。r s h o ps c h e d u l i n gi n s t a n c e sa n dt h ee n c e r p r i s ep r a c t i c ej o bs h o pc a s e sa r es i m u l a t e da n d c o n 旺a s t e d ，a n dt h ea v a j j a b m t yo ft 1 1 em o d e l sa n dt h ea l g o r i t h m sa r ev a j i d a t e d 6 c o n s # q u e n t i y 血ej o bs h o ps c h e d u l i n gs y s t c mi s a c h i e v e db a s e do na b o v e s c h e d u l i n g 山e o r yw i t ht h ea d v a n c e ds o f tt e c h n o l o g y ，a n da p p l i e dt 0p r o d u c t i o n d r a c t i c e k e yw o r d s ： j o bs h o ps c h e d u l i n g ，i r 姗u n e p r i n c i p l e ，i m m u n ea l g o r i t ， m o d e l i n g ，s i m u i a t i o n ，f l e x i b l e ，m u l t i 一0 b j e c t i v e ，m u l t i - c o n s 仃a i n t ，m u j t i d i s t u r b ， d i s t r i b u t i n 岛s c h e d u l i n gg r i d i m m l l l l ea g e n t ，c o m p o n c n t 1 1 1 ed i s s e 砌石o ne s t a b l i s h e ss u b j e c ta c c o f d j n gi oc h ep h dp r o g r a mf o u n d a “o no f e d u c a t i o nm i i l i s t 叮o fc 1 1 i n a ( g 髓n tn o 2 0 0 4 6 9 9 0 2 5 ) a 1 1 di ss u p p o r t e db yt h en a l i o n a l h i t c c h n o l o g yr e s e a r c h & d e v c l o p m e n tp r o g 瑚】f o rc i m so fc h i n a ( g m n tn o 2 0 0 l 从4 1 2 1 5 0 ，2 0 0 3 a a 4 1 1 1 1 0 ) a n ds u p p o n e db y t i l e n a t i o n a l n a t l l r ef o u n d a t i o n o f c h i i l a ( g r a n 【n o 6 9 9 8 4 0 0 4 ) 一v 一 两北工业大学博十学位论文 英文缩写索弓 缩写 全称 汉泽 a c aa n tc o l o n ya i g o m h m 蚁群算法 a g e n ta g e n t 智能体 a h p a n a l y t i c a lh i c 唧h yp r o c e s s层次分析洁 a i sa r i t i c i a i i m m u n cs y s t e m 人工免疫系统 a m s a 百l cm a n u f a c t u r i n gs y s t e m敏捷制造系统 a m ta d v a n c e dm a | l u f 砬t u r h l gt e c h n o l o g y 先进制造技术 a n t i b o ( 1 v a n t b o d y 抗体 a n t i g e n sa n t i g e n抗原 b m sb i o n i c a im a n u f k t u r i n gs y s t e m 仿生制造系统 b o mb 1 lo f m a t c r i a l 物料清单 c cc c l lc l o n e 细胞克隆 c i m s c o m p u t c ri n t e g r a t e dm a n u f 如f u r i n g计算机集成制造系统 s y s t e m c p nc o l o r e dp n n e t 着色佩雷网 c sc l o n es e i e c n o n 克隆选择 c s nc i o n es u p p r e s s i o n 克隆抑制 d e i a d y n a m i ce v a i u a t i o nb a s e di m m u l l e基于动态评价的免疫算法 a l g o r i t h m e r p e n t e r p s er e s o u f c ep j a 仰i 几g企业资源规划 f j s sf 1 e x i b i cj o bs h o ps c h e d u l i n g 柔性作业车问调度 f m sf l e x b l em a n u f a c t u r i n gs y 5 t e m 柔性制造系统 f s sf i o ws h o ps c h e d u l i n g 流水车问调度 g c a h p g m yc o r r e l d t i o na 衄l 州c a lh i e 眦时 面向调度的灰色关联层次分 p r o c e s s 析 g p pg l o b a lp r o c e s sp i a n n i n g 全局：r 艺分析 g r s gr i dr e s o u r c ei n f o m l a t i o ns e r v i c e 网格资源信息服务 【ai m m u n ea i g o r “h m 免疫算法 i a c ai m m u n ea n tc o l o r l ya l g o r t h m 免疫蚁群算法 i ci n m l u n ec r o s s o v e r 免疫交叉 i mi m m u n em u t a t j o n 免疫变异 i s a ai m m u n es j m u l a t e d a n n e a l i n g免疫模拟退火算法 a i g o r i t h m 一l2 9 茎塞丝王室! ! j s sj o bs h o ps c h e d u 沛g 作业车间调度 l p sl e a np m d u c t j o ns y s t e m敏捷制造系统 m c d a i a m u i t i c o i o n yd i p i o j da d a p t i v ei m m u n e多种群取倍体自适应免疫算 a l g o r j t l l m法 m c m o f j s sm u j f j c o n s l m j m m u l f j o b j e c t j v e多约束多目标柔性作业车间 f l e x i b i ej o bs h o ps c h e d u i i n g 调度 m o f j s s m u i c i - o b j e c “v e f l e x i b l ej o b s 1 1 0 p多目标柔性作业车间调度 s c h e d u n g n nn e u m in e t w o 神经网络 n p n o n - p o l y n o m i a i 非多项式 0 0 o b j e c t o r i e n t e d 面向对象 o o t c p n o b j e c t - o r i e n t e d t i m e dc 0 1 0 f e dp e t r i面向对象赋时着色佩雷网 n e t o o t c p n s o b j e c t o e n t e dt i m e dc o l o r e d p e t i 面向对象赋时着色佩雷网系 n e ts y s t e m 统 p f j s sp a 州a lf f e x m i ej o bs h o ps c h e d u i j n g 部分柔性作业车问调度 p h e r o m o n ep h e r o m o n e 信息激素 p m o f j s sp a r t i a lm u l t i o b j e c t i v ef 1 e x b l ej o b部分多目标柔性作业车间调 s h 叩s c h e d u l i n g 度 p np e 谢n e t 佩雷网 p s fp r o d u c ts t r u c t u r ef i g u r e 产品结构图 s as i m u i a t e da n n e a l i n ga i g o r i t h m 模拟退火算法 s c h e d u l i n g s c h e d u j j n g 调度 s g s c h e d u l i n gg r j d 调度网格 s o d s s c h e d u l i n gg dd i r e c t o r ys e r v i c e调度网格目录服务 t f j s s t o 诅if l e x j b i ej o bs h o ps c h e d u l j n g 完全柔性作业车间调度 t m o f j s st o t a lm u l c l o b j e c t j v ef l e x i b i ej o bs h o p完全多目标柔性作业车间稠 s c l l e d u i i n g度 t p n t i m e dp e 们n e t 赋时佩雷网 t r ft a s kr e l a t i o nf i g u r e 任务关系图 v m sv i n u a lm a n u f k t u r i n gs y s t e m 虚拟制造系统 西北工业大学 学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定，即：研究生在校攻读 学位期间论文工作的知识产权啦位属于西北工业大学。学校有权保留并 向国家有关部门或机构送交论文的复印件和电子版。本人允许论文被查 阅和借阅。学校可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 同时本人保证，毕业后结合学位论文研究课题再撰写的文章一律注明作 者单位为西北工业大学。 保密论文待解密后适用本声明。 学位论文作者签名：金莲星 加7 年月，； 日 指导教师签名：立咝 7 年占月日 西北工业大学 学位论文原创性声明 秉承学校严谨的学风和优良的科学道德，本人郑重声明：所呈交的 学位论文，是本人在导师的指导下进行研究工作所取得的成果。尽我所 知，除文中已经注明引用的内容和致谢的地方外，本论文不包含任何其 他个人或集体已经公开发表或撰写过的研究成果，不包含本人或他人已 ”请学位或其它用途使用过的成果。对本文的研究做出重要贡献的个人 和集体，均已在文中以明确方式标明。 本人学位论文与资料若有不实，愿意承担一切相关的法律责任。 学位论文作者签名：全鎏军 d o7 年6 月晤日 两北一r 业大学博士学位论文 第一章绪论 市场环境决定着企业的生产方式，2 1 世纪制造业面临的市场环境有如下特 点：经济全球化，使企业面对的竞争者和顾客范围更广；市场竞争加剧，竞 争的基础和层面多样化；顾客需求多样化、个性化，变化频率加快：制造场 合和经营环境的变化成为普遍的、持续的、常规的现象。在这种形式下，制造企 业需要以最快的上市速度( t t i m e ) ，最好的质量( q q u a l i t y ) 、最低的成本( c c o s t ) 、最优的服务( s s e r v i c e ) 及最清洁的环境( e e n v i r o n m e n t ) 来满足不同客户 对产品的需求和社会可持续发展的要求。为实现这一目标，近年来人们将制造技 术与当代信息技术、自动化技术、现代管理技术及系统工程方法相互融合，提出 了先进制造技术( a d v a n c e dm a n u f a c t l l r i n g t e c h l l o l o g y ，a m t ) 的概念。 国内外已经提出或实施的先进制造技术模式有柔性制造系统( f l e x j b j e m a n u f a c t “n gs y s t e m ，f m s ) 、计算机集成制造系统( c o m p u t e ri n t e g r a t e d m a n u f a c t 晡n gs y s t e m ，c i m s ) 、敏捷制造系统( a 昏i em a n u 矗l c n 嫡n gs y s t e m ，a m s ) 、 精良生产系统( l e a i lp r o d u c t i o ns y s t e m ，l p s ) 、虚拟制造系统( v i m l a lm a n u f a c t u r i n g s y s t 咖，v m s ) 、企业资源觑划( e n t e 巾r i s e r e s o u r c e p j a n n i n 吕e r p ) 1 ”、仿生制造系 统( b i o n i c a lm a l l u f 孔t l i r i n gs y s t e m ，b m s 严i 等。它们足在不同的时代、不同的经济 环境下根据不同的用户需求相继发展起来的，均发挥了不同的重要作用。 尽管这些先进制造技术模式的原理和实现技术存在很大差异，然而，它们都 是通过合理配置和优化内外资源、缩短制造周期、降低生产成本来解决企业普遍 面临着的许多共性问题。生产调度( p r o d u c n o ns c h e d u l i n g ) 币是有效的资源配置和 优化手段，能够将作业均衡地安排到各处理机上，并合理安排各作业的加工次序， 在满足系统约束条件的前提下优化相关性能指标。因此，生产调度很自然地成为 以上各种先进制造技术模式共同关注的核心内容和重要组成部分。德国汉诺威大 学生产系统研究所曾对6 个不同行业的企业做过调查，调查结果表明：零件实际 加工时间约占总加工周期的1 5 左右，而8 5 以上的时唰用于等待、搬运和排 队| 3 j 。因此，提出先进而实用的调度与控制算法，开发高效而稳定的调度与管理 系统己成为企业界的迫切需求，也是理论界的研究热点。 1 1 生产调度 作为机械工程、应用数学、信息技术、系统工程等多学科的交叉研究热点和 第一章绪论 难点，生产调度有着深刻的实际背景和广阔的应用前景。生产调度是为完成若干 项任务将所需要用到的人、财、物等资源进行最优分配、最优排序。 1 1 1 生产调度的概念 定义1 1生产调度：针对一项可分解的工作，探讨在尽可能满足约束条件 ( 如交货期，工艺路线、资源情况) 的前提下，通过下达生产指令，安排其组成部 分( 操作) 使用哪些资源、加工时间及加工顺序，以获得某些性能指标( 如生产周期、 生产成本) 的最优化1 4 i 。 定义1 2 生产调度：在给定产品集、计划周期、加工资源集和各产品加工 工艺条件下，关于w h a t ，w h e n ，w h e r e ，h o w 的一个决策过程n w h a t 确定在具体的计划周期内生产的产品品种及其数量： w b e n 确定每一个具体操作的开始时间和结束时间： w h e r e 确定执行每一个具体操作的设备或处理单元； h o w 确定产品的生产批量、产品进入生产系统的方式、加工设备选择规则、 加工优先级规则和中间存储策略等。 调度系统的功能在于组织生产过程，一个理想的调度系统要通过合理的生 产组织工作，使产品生产的各个工艺阶段、各个生产环节和各道工序之间相互衔 接，协调工作，从而保证各种资源得以充分利用，以达到按质，按量，按期、按 成本生产出合格产品的目标。 调度作为一类复杂的组合优化问题，具有多约束、多目标和随机不确定性的 特点，其求解过程的计算量随调度问题规模呈指数增长，绝大多数调度问题都属 于n p 完备问题i j 。 1 1 2 生产调度分类 生产调度问题的分类方法很多，主要有以下几种： ( 1 ) 根据加工系统的复杂度，调度可以分为单机调度、多机器并行调度、f j o w s h o p 调度、o p e ns h o p 调度、j o bs h o p 调度等几个基本类型： ( 2 ) 根据优化准则，可以分为基于代价的调度和基于性能的调度两大类： ( 3 ) 根据生产环境的特点，可将调度分为确定性调度和随机性调度； ( 4 ) 根据加工任务的特征，可将调度分为静态调度和动态调度。 实际的调度问题往往是由f l o ws h o p 和j o bs h o p 等基本调度类型组合而成， 基于代价和性能，且是随机性的、动态的 i 。 眄北f 业人学博f 。学位论文 1 1 3 生产调度研究策略 调度策略是调度的高层次： 1 5 分，由于一般调度问题的复杂性，各种不同的具 体问题往往有很多不同的解决方法，因此需要从策略上去考虑调度问题，形成各 种研究方法策略以指导对调度的研究m j 。目前调度策略大致可以分为以下几种： ( 1 ) 并行或分布策略； ( 2 ) 分解与成组策略； ( 3 ) 人机交互策略： ( 5 】实时或动态重调度策略； ( 6 ) 多目标决策策略； ( 7 ) 生产计划与调度集成策略； ( 8 ) 异地分布式调度策略。 1 2 生产调度研究综述 调度理论与应用研究内容主要包括调度建模、调度算法、调度仿真、调度评 估等。调度理论与应用经过几十年的长足发展，已经成为发展最迅速、研究最活 跃、成果最丰硕、前景最诱人的学科领域之一，在此，分析一些与本文研究比较 相关的成果与现状。 1 2 1 调度建模研究现状与发展趋势 模型是对所研究系统的一种描述，它可采用多种形式进行表征，如数学公式、 图表、语言描述等。基于系统模型，可分析系统的行为性能与系统结构参数的关 系，可进一步研究系统的控制和优化。车间生产调度模型是对车间这个复杂动态 系统的一种抽象和简化。从现有的文献来看，对车间生产调度进行建模可归结为 四种类型：基于图与网络进行建模、基于控制论