（机械电子工程专业论文）不确定环境下模具制造多项目动态调度建模与仿真.pdf

摘要 摘要 模具是工业生产中不可或缺的基础工艺装备，主要用于高效大批量生产工业产品中 的有关零部件和制件，是制造装备业的重要组成部分。模具制造水平的高低，已经成为 衡量一个国家产品制造水平高低的重要标志。伴随着全球制造业向我国转移的大趋势， 广东逐渐成为世界制造业的重要基地之一，模具需求量日益增加。然而，与发达工业国 家相比，我国模具工业的综合水平仍存在一定的差距，这种差距在企业生产管理方面表 现得尤为明显。 模具制造属于面向资源的单件工程订货型生产方式。模具生产过程特别强调交叉与 并行，自始至终存在着双向信息的传递，属于典型的项目式运作模式。模具的生产管理 具有多企业、多项目共享资源，协调管理的典型需求。模具生产过程中存在许多不确定 因素( 如任务工期不确定、可再生资源发生故障、随机插入新订单等) ，这些不确定因 素的出现往往导致实际生产无法遵循开始制订的基准调度计划，只有采取行之有效的预 防方法和科学的动态调度与控制策略，才能优化资源配置，尽量消除不确定因素的影响， 确保项目顺利进行。 本文在国家自然科学基金( 5 0 6 7 5 0 3 9 、5 0 8 7 5 0 5 1 ) 和国家8 6 3 计划资助项目 ( 2 0 0 6 a a 0 4 2 1 3 2 ) 1 拘联合资助下研究不确定环境下的模具制造多项目动态调度问题。从 模具制造的实际情况出发，分析了不确定因素的描述方法，并详细探讨了模具制造多项 目动态调度的决策机制，以及相关调度模型的构建、仿真与求解方法。论文研究成果的 应用，将有利于提高模具企业的生产管理水平，从而提升我国模具行业的整体竞争力。 论文的主要工作包括如下几个方面： 1 、分析了模具的制造方式与特点，阐述了不确定因素和突发事件对模具制造多项 目调度计划的影响，在此基础上构建了一种不确定环境下的模具制造多项目预测一反应 式调度模型； 2 、针对模具制造项目执行过程中任务工期不确定的情况，提出了一种模具制造多 项目预测一反应式调度模型求解算法。首先采用启发式微粒群算法，并结合基于关键链 技术的时间缓冲设置方法求取模具制造多项目调度的预测计划( 基准调度计划) 。在调度 计划执行过程中，以任务拖期为作为反应调度的触发事件，应用基于复合最优模型的改 进微粒群算法，并结合修改后的串行调度生成方案和并行调度生产方案求解反应调度模 型，以缓解局部任务拖期对整体调度计划的影响； i 广东工业大学博士学位论文 3 、针对模具制造项目执行过程中任务工期不确定和项目调度计划具有固定资源流 约束的情况，提出了一种度量资源流网络稳定性的方法，并设计了一种基于优先规则的 微粒群算法来构建稳定的资源流网络，在此基础上提出了一种具有固定资源流约束的模 具制造多项目预测一反应式调度模型求解算法； 4 、针对可再生资源发生故障与任务工期不确定这两种不确定因素同时出现对多项 目调度计划的干扰问题，提出了一种模具制造多项目预测一反应式调度模型求解算法。 采用生灭过程理论对可再生资源的不确定性进行了分析与建模，提出了一种基于两阶段 优化的启发式算法来求解稳定的基准调度计划。根据实际情况，对常用的串行调度生成 方案进行了修改，在此基础上提出了一种基于混沌微粒群算法的反应调度算法； 5 、从多目标优化的角度出发，系统地研究了可随机插单、可再生资源发生故障以 及任务工期不确定等多种不确定因素共同影响下的模具制造多项目动态调度问题。提出 了一种基于最优解评估选取方法，并将孤立点搜索策略与精英归档策略相结合的改进多 目标微粒群算法进行反应调度模型求解； 6 、开发了一套不确定环境下的模具制造多项目动态调度仿真系统，便于设置不 同的环境，采用各种不同的算法和数据，以及配置不同的算法参数进行模具制造多项目 调度仿真，从而对上述调度模型的合理性与有效性进行分析与验证，同时也有利于对相 关调度算法的性能进行系统地分析与比较。 关键词：模具制造；多项目；不确定性；预测一反应式调度；动态调度；系统仿真 i i a b s t r a c t a b s t r a c t m o u l d sa n dd i e s ( m & d ) ，m a i n l yu s e df o re f f i c i e n tm a s sp r o d u c t i o no fi n d u s t r yp r o d u c t p a r t sa n dc o m p o n e n t s ，a l ei n d i s p e n s a b l yb a s i cc r a f te q u i p m e n tf o ri n d u s t r i a lp r o d u c t i o n ；m e y s e r v ea sa ne s s e n t i a lc o n s t i t u e n tf o rt o t a le q u i p m e n tm a n u f a c t u r i n gi n d u s t r y s i m p l yp u t ，t h e l e v e lo fm & d m a n u f a c t u r i n gh a sb e c o m ea l li m p o r t a n ti n d i c a t o rf o rm e a s u r i n gac o u n t r y s p r o d u c tm a n u f a c t u r i n gl e v e l a c c o m p a n i e db yt h et r e n dt h a tg l o b a lm a n u f a c t u r i n gi n d u s t r yi s t r a n s f e r r i n gt oc h i n a , g u a n g d o n gp r o v i n c eh a sb e e ng r a d u a l l yb e c o m i n go n eo fm o s t i m p o r t a n tm a n u f a c t u r i n gb a s e si nt h ew o r l dw i t ht h ee v e r - g r o w i n gd e m a n df o rm & d a s o p p o s e dt ot h ea v e r a g el e v e lo fm & di n d u s t r yo fd e v e l o p e di n d u s t r i a lc o u n t r i e s ，h o w e v e r , t h e l e v e lo fm & di n d u s t r yo fo u rn a t i o n , e s p e c i a l l yt h a ti n t h ee n t e r p r i s ep r o d u c t i o n m a n a g e m e n ta r e a , i ss t i l ll a g g i n gb e h i n d m & d m a n u f a c t u r i n gi sg e n e r a l l yi nt h es i n g l e - p r o j e c to r d e rf o r mw i t hr e s o b r c e o r i e n t e d f e a t u r e r e g a r d e da sat y p i c a lp r o j e c t - b a s e do p e r a t i o nm o d e l ，t h em & dp r o d u c t i o np r o c e s s p l a c e sav e r ys p e c i a le m p h a s i so nc r o s sa n dp a r a l l e l i s m ；i n s i d et h ep r o c e s sa l w a y se x i s t st h e t w o - w a y i n f o r m a t i o nt r a n s m i s s i o nb e t w e e nap r o j e c ta n da n o t h e r m & d p r o d u c t i o n m a n a g e m e n t f e a t u r e s t y p i c a lr e q u i r e m e n t s f o rr e s o u r c e p o o l i n g a n d m a n a g e m e n t c o o r d i n a t i o nb ym u l t i p l ee n t e r p r i s e sa n dp r o j e c t s i np r a c t i c a lm & d p r o d u c t i o ne x i s tm a n y u n c e r t a i n t i e s ，s u c ha st a s kd e l a y i n g ，r e n e w a b l er e s o u r c e sb r e a k i n g - d o w na n dn e wp r o j e c t s a r r i v i n ga tr a n d o mt i m e ，m a k i n gi ta l w a y si m p o s s i b l ef o rp r o d u c t i o nm a n a g e r st of o l l o wt h e o r i g i n a l b a s e l i n es c h e d u l e ( o ri n i t i a l s c h e d u l e ) o n l yb yt a k i n ge f f e c t i v ep r e v e n t i v e a p p r o a c h e sa n ds c i e n t i f i cd y n a m i cs c h e d u l i n ga n dc o n t r o l l i n gs t r a t e g i e sc a nm a k ei tp o s s i b l e t oo p t i m i z et h er e s o u r c ea l l o c a t i o n , t oe l i m i n a t et h ei n f l u e n c eo fu n c e r t a i n t i e sa n dt oe n s u r e t h ep r o j e c te x e c u t i o n s u p p o r t e db yt h en a t i o n a ln a t u r a ls c i e n c ef o u n d a t i o no fc h i n a ( g r a n tn o 5 0 6 7 5 0 3 9 ， 5 0 8 7 5 0 51 ) a n dt h en a t i o n a lh i 曲一t e c h r & dp r o g r a mo fc h i n a ( g r a n tn o 2 0 0 6 a a 0 4 z13 2 ) ， o u rr e s e a r c hw a sf o c u s e do nu n c e r t a i n t y b a s e dd y n a m i cs c h e d u l i n gp r o b l e mf o rm u l t i p l e m & dm a n u f a c t u r i n g p r o j e c t s f r o mt h ep r a c t i c a lm & dm a n u f a c t u r i n gs i t u a t i o n , t h e d e s c r i p t i o nm e t h o d sf o ru n c e r t a i n t yf a c t o r sw e r eh e r e i na n a l y z e d t h ef o l l o w i n gt w oi s s u e s h a v eb e e nd i s c u s s e di nd e t a i la sw e l l ，t h ed e c i s i o n - m a k i n gm e c h a n i s mo fd y n a m i cs c h e d u l i n g i l i 广东工业大学博士学位论文 f o rm u l t i p l em & dm a n u f a c t u r i n gp r o j e c t s ，a n dt h ec o n s t r u c t i o n , s i m u l a t i o na n ds o l u t i o n m e t h o d sf o rt h er e l a t e ds c h e d u l i n gm o d e l s a p p l i c a t i o n so ft h er e s e a r c ha c h i e v e m e n t sw i l lb e a d v a n t a g e o u st oi n c r e a s ep r o d u c t i o nm a n a g e m e n tl e v e l so fm & dc o r p o r a t i o n s ，a n dt o i m p r o v em & di n d u s t r yw h o l ec o m p e t i t i v e n e s so fo u rc o u n t r y t h er e s e a r c hm a i n l yi n c l u d e st h ef o l l o w i n ga s p e c t s 1 t h em a n u f a c t u r i n gm o d e lo fm & da n di t sc h a r a c t e r i s t i c sw e r ea n a l y z e d ，a n d u n c e r t a i n t i e sa n di n c i d e n t si m p a c t i n go nm u l t i p l em & d m a n u f a c t u r i n gp r o j e c t ss c h e d u l i n g w e r ee l a b o r a t e d ap r e d i c t i v e - r e a c t i v es c h e d u l i n gm o d e lf o rm u l t i p l em & d m a n u f a c t u r i n g p r o j e c t su n d e ru n c e r t a i n t i e sw a sc o n s t r u c t e d 2 c o r r e s p o n d i n gt ot h ef a c tt h a tt a s kd e l a y i n gf r e q u e n t l yh a p p e n si nm u l t i p l em & d m a n u f a c t u r i n gp r o j e c t sp r o c e s s ，a na l g o r i t h mw a sp r o p o s e dt os o l v et h ep r e d i c t i v e r e a c t i v e s c h e d u l i n gm o d e l as t a b l eb a s e l i n es c h e d u l ew a sc o n s t r u c t e db ys e t t i n gt i m eb u f f e r sb a s e d o nc r i t i c a lc h a i nt e c h n o l o g y , t h e r e f o r e ，t oe l i m i n a t et h ee f f e c to ft a s k d e l a y i n ga sf a ra s p o s s i b l e a c c o r d i n gt ot h ea c t u a ls i t u a t i o n , t h ec o m m o n l yu s e ds e r i a ls c h e d u l eg e n e r a t i o n s c h e m ea n dp a r a l l e ls c h e d u l eg e n e r a t i o ns c h e m ew e r em o d i f i e d o nt h i sb a s i s ，a ni m p r o v e d p a r t i c l es w a r l l lo p t i m i z a t i o nw a sp r o p o s e dt os o l v et h er e a c t i v es c h e d u l i n gm o d e l 3 t h ec o n c e p t so fr e s o u r c ef l o wa n dr e s o u r c ef l o wn e t w o r kw e r ei n t r o d u c e di nt h i s t h e s i s am e t h o do fm e a s u r i n gt h es t a b i l i t yo fr e s o u r c ef l o wn e t w o r kw a sp r o p o s e d o nt h i s b a s i s ，ap a r t i c l es w a r mo p t i m i z a t i o nb a s e do nt h ep r i o r i t yr u l e sw a sp u tf o r w a r dt oc o n s t r u c ta s t a b l er e s o u r c ef l o wn e t w o r ka n dt os i m p l i f yt h es o l v i n gp r o c e s so ft h er e s o u r c ef l o wn e t w o r k c o n s i d e r i n gt h ef r e q u e n to c c u r r e n c eo ft a s k sd e l a y i n gd u r i n gm u l t i p l em & dm a n u f a c t u r i n g p r o j e c t se x e c u t i o n , a i la l g o r i t h mw a sp r o p o s e dt os o l v et h ep r e d i c t i v e - r e a c t i v es c h e d u l i n g m o d e lw i t hf i x e dr e s o u r c ef l o wc o n s t r a i n t 4 c o n s i d e r i n gt h ei n f l u e n c eo fr e n e w a b l er e s o u r c e sb r e a k i n g d o w na n dt a s kd e l a y i n go l l s c h e d u l i n gf o rm u l t i p l em & dm a n u f a c t u r i n gp r o j e c t s ，a na l g o r i t h mw a sp r e s e n t e dt os o l v e t h ep r e d i c t i v e r e a c t i v es c h e d u l i n gm o d e l u n c e r t a i na v a i l a b i l i t i e so fr e n e w a b l er e s o u r c e s w e r ea n a l y z e dw i t ht h et h e o r yo fb i r t h d e a t hp r o c e s s ，a n dah e u r i s t i c a l g o r i t h mb a s e do n t w o - s t a g e do p t i m i z a t i o nw a sp r o p o s e dt os o l v et h es t a b l eb a s e l i n es c h e d u l e a c c o r d i n gt ot h e a c t u a ls i t u a t i o n , t h ec o m m o n l yu s e ds e r i a ls c h e d u l eg e n e r a t i o ns c h e m e w a sf u r t h e rm o d i f i e d o nt h i sb a s i s ，ar e a c t i v es c h e d u l i n ga l g o r i t h mb a s e do nc h a o t i cp a r t i c l es w a r m o p t i m i z a t i o nw a s t v a b s t r a c t p r o p o s e d 5 f r o mm u l t i o b j e c t i v eo p t i m i z a t i o np e r s p e c t i v e ，am u l t i - o b j e c t i v ed y n a m i cs c h e d u l i n g p r o b l e m f o r m u l t i p l e m & dm a n u f a c t u r i n gp r o j e c t sw a ss y s t e m a t i c a l l ys t u d i e dw i t h c o n s i d e r i n gt h ec o - i n f l u e n c eo fs u c hm u l t i p l eu n c e r t a i n t i e s 嬲r a n d o ma r r i v a lo fn e wp r o j e c t s ， b r e a k i n g - d o w no fr e n e w a b l er e s o u r c e sa n dt a s k sd e l a y i n g a ni m p r o v e dm u l t i o b j e c t i v e p a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h mw a sp r o p o s e dt os o l v et h e r e a c t i v es c h e d u l i n gm o d e l ； b a s e do nt h ea s s e s s m e n ta n ds e l e c t i o nm e t h o df o ro p t i m a ls o l u t i o n , t h ea l g o r i t h mc o m b i n e s b o t ht h ei s o l a t e dp o i n t ss e a r c h i n gs t r a t e g ya n dt h ee l i t ea r c h i v i n gs t r a t e g y 6 as y s t e m - s i m u l a t i o ns o f t w a r eo f d y n a m i cs c h e d u l i n g f o r m u l t i p l e m & d m a n u f a c t u r i n gp r o j e c t su n d e ru n c e r t a i n t i e sw a sd e v e l o p e d ，w i t hw h i c hi ti s c o n v e n i e n tt o s i m u l a t et h ed y n a m i cs c h e d u l i n gp r o c e s sb ys e t t i n gu pd i f f e r e n te n v i r o n m e n t s u s i n g d i f f e r e n ta l g o r i t h m sa sw e l la sal a r g ev a r i e t yo fd a t a , a n dc o n f i g u r i n gv a r i o u sp a r a m e t e r sf o r r e l a t e da l g o r i t h m s ，t h es y s t e ms i m u l a t i o ns o f t w a r ec a na n a l y z ea n dv e r i f yt h er a t i o n a l i t ya n d t h ee f f e c t i v e n e s so ft h es c h e d u l i n gm o d e l sm e n t i o n e da b o v e ；i nt h em e a n t i m e ，s u c hs o f t w a r e c a nb ea l s oo fg r e a tv a l u ef o rs y s t e m a t i c a l l ya n a l y z i n ga n dc o m p a r i n gt h ep e r f o r m a n c eo ft h e r e l a t e ds c h e d u l i n ga l g o r i t h m s k e yw o r d s ：m o u l da n dd i em a n u f a c t u r i n g ；m u l t i p l ep r o j e c t s ；u n c e r t a i n t y ；p r e d i c t i v e r e i e t - i v es c h e d u l i n g ；d y n a m i cs c h e d u l i n g ；s y s t e ms i m u l a t i o n v c o n t e n t s a b s t a r a c t ( c h i n e s e ) a b s t r a c t ( e n g l i s h ) c o n t e n t s ( c h i n e s e ) c o n t e n t s ( e n g l i s h ) c o n t e n t s f i g u r ea n dt a b l ei n d e x ( c h i n e s e ) c h a p t e rlp e r f a c e l i i 1 1b a c k g r o u n d o b j e c t i v e sa n ds i g n i f i c a n c e so fr e s e a r c h l 1 1 1c u r r e n ts i t u a t i o na n dp r o b l e m so fm & di n d u s t r yo fo u rc o u n t r y l 1 1 2m a n u f a c t u r i n gm o d e lo f m & da n di t sc h a r a c t e r i s t i c s 2 1 1 3o b j e c t i v e sa n ds i g n i f i c a t i o n so f r e s e a r c h 3 1 2i 己e s e a r c hs u r v e y 3 1 2 1s u r v e yo fu n c e r t a i n t i e si np l a n n i n ga n ds c h e d u l i n g 4 1 2 2d e c i s i o nm e c h a n i s mf o rs c h e d u l i n gu n d e ru n c e r t a i n t y 6 1 2 3s o l u t i o na n do p t i m i z a t i o nf o rp r o j e c t ss c h e d u l i n gu n d e ru n c e r t a i n t y 毒p 10 1 2 4s u m m a r i z a t i o no fr e s e a r c hs u r v e ya n dp r o b l e m sa n a l y s i s 14 1 3i 迁! s e a r c hc o n t e n ta n dt h e s i ss t i 山c t u r e l5 1 4s u l 、心1ar yo fc h a p t e r1 17 c h a _ p t e r2p r e d i c t i v e r e a c t i v es c h e d u l i n gm o d e lf o rm u i j i p l e m dm 【a n u f a c t u r i n gp r o j e c t s 2 1i n t r o d u c t i o n 18 2 2e x e c u t i n gp r o c e s so fm & dm a n u f a c t u r i n gp r o j e c t l8 2 3f r a m e w o r ko fp r e d i c t i v e r e a c t i v es c h e d u l i n gf o rm u l t i p l em & d m a n u f a c t u r i n gp r o j e c t s 21 2 4p r e d i c t i v es c h e d u l i n gm o d e lf o rm u l t i p l em & dm a n u f a c t u r i n gp r o j e c t s 2 2 2 5r e a c t i v es c h e d u l i n gm o d e lf o rm u l t i p l em & dm a m 腰a c t l 瓜i n gp r o j e c t s 2 4 2 5 1s i n g l eo b j e c t i v er e a c t i v es c h e d u l i n gm o d e l 。2 5 2 5 2m u l t i p l eo b j e c t i v e sr e a c t i v es c h e d u l i n gm o d e l 2 5 2 6b a s i cp r e c o n d i t i o n sa n dh y p o t h e s i s e s 2 6 2 7s u 嗄 嗄ar yo fc l a p t e r2 2 7 c h a p t e r3p r e d i c t i v e r e a c t i v es c h e d u l 小gf o rm i 丁i 肌p l em & d 刚u f a c t u l u n gp r o 皿c t sw i t ht a s k d e l a y l n g 3 1i n t r o d u c t i o n 2 8 3 2l 也l a n o n s h i pb e t w e e nd u ed a t ec o n s t r a j n to np r o 甩c t sa n d s 1 ：a b i l i t yo fs c h e d u l e 2 8 3 3g e n e r a t i o no fs t a b l eb a s e l i n es c h e d u l e 2 9 3 3 1g e n e r a t i o no fi n i t i a ls c h e d u l e 2 9 3 3 2t i m eb u f f e rs e t t i n gb a s e do nc r i t i c a lc h a i nt e c h n o l o g y 3 0 3 4r e a c t i v es c h e d u l i n ga l g o r i t h mb a s e do ni m p r o v e dp s o 3 6 i x 广东工业大学博士学位论文 3 4 1r e a c t i v es c h e d u l i n ga l g o r i t h md e s c r i p t i o n 3 6 3 4 2i m p r o v e dp s 0b a s e do nc o m b i n e do p t i m a lm o d e l 3 7 3 4 3m o d i f i e ds c h e d u l eg e n e r a t i o ns c h e m e s ：；9 3 5s i m u l a t i o ne x p e i u m e n t 4 2 3 5 1n u m e r i c a le x a m p l ed e s c r i p t i o na n da l g o r i t h mp a r a m e t e r ss e l e c t i o n 4 2 3 5 2a n a l y s i so fs i m u l a t i o nr e s u l t s z m 3 5 3p a r a m e t e r ss e t t i n gf o ra l g o r i t h m3 7a n di t sp e r f o r m a n c ea n a l y s i s 4 5 3 6s i m m a r yo fc h a p t e r3 4 6 c h a p t e r4p r e d i c t i v e r e a c t i v es c h e d u l i n gf o rm u m p l em & d l 悄u f a c t u r i n gp r o j e c t sw i t hf i x e dr e s o u r c ef l o wc o n s t r a i n t 4 7 g 1i n t r o d u c t i o n 4 7 4 2r e s o u r c ef l o wn e t w o r ka n di t sc o n s t r u c t i o na l g o r i t h m s 4 7 4 2 1c o n c e p to f r e s o u r c ef l o wn e t w o r k 4 7 4 2 2a no v e r v i e wo fc o n s t r u c t i o na l g o r i t h m sf o rr e s o u r c ef l o wn e t w o r k 5 0 4 3h e u r i s t i cc o n s t r u c t i o na l g o r i t h m sf o rr e s o u r c ef l o wn e t w o r k 5 2 4 3 1u n a v o i d a b l er e s o u r c ea r c si nr 5 2 4 3 2a i m p r o v e dh e u r i s t i cc o n s t r u c t i o na l g o r i t h mf o rr e s o u r c ef l o wn e t w o r k 5 3 4 4p r e d i c t i v e r e a c t i v es c h e d u l i n ga l g o r i t h mf o r 叮【t i p l em & d m a n u f a c t u r i n gp r o j e c t sw i t hf i x e dr e s o u r c ef l o wc o n s t ra i n t 5 8 4 4 1p r e d i c t i v es c h e d u l i n ga l g o r i t h m 5 8 4 4 2r e a c t i v es c h e d u l i n ga l g o r i t h m ! ；9 4 5s i m u l a t l 0 ne x p e r i m e n t 6 0 4 5 1n u m e r i c a le x a m p l ea n ds i m u l a t i o ne n v i r o n m e n ti n t r o d u c t i o n & a l g o r i t h m s p a r a m e t e r ss e t t i n g 6 0 4 5 2a n a l y s i so fs i m u l a t i o nr e s u l t s 6 1 4 6s im m a r yo fc h a p t e r4 6 2 c h a p t e r5p r e d i c t i v e r e a c t i v es c h e d u l i n gf o rm i 月r i p l em & d m 【