（机械制造及其自动化专业论文）汽车混装平衡问题的随机有序元胞自动机算法研究.pdf

第1 i 页武汉科技大学硕士学位论文 摘要 汽车产业的发展经历着从标准化到多样化的发展。随着市场竞争的不断加剧，促使汽 车生产厂家依靠多品种来满足用户个性化需求。汽车装配是汽车全部制作工艺过程的最终 环节，汽车装配线负荷均衡严重影响着产品质量和企业生产效率，在汽车制造工艺中尤为 重要。因而，研究汽车装配线平衡问题，设计出快速有效的方法，提高生产绩效，满足汽 车行业的需求具有重要意义。 本文针对汽车混合模型装配线平衡问题，以最小化生产节拍和提高平衡率为目标建立 数学模型，构造了混装平衡的元胞自动机模型，提出了一种随机有序元胞自动机算法。 在算法的初始化过程中，提出并混合使用三种启发式因子( 操作时间、后续操作数和 可释放操作数) 选择操作；同时把工位时间划分为三个区间，根据不同区间使用不同的分 配方法，用以确定选择的操作是否进行分配，以此得到更好的初始分配方案。 然后，提出随机有序元胞进化规则对初始解进行优化，设计工位间的广义任务交换过 程，提出顺序执行规则，根据交换任务数量非增的顺序执行交换过程，从而使算法快速的 收敛到当前最好解。在交换过程中随机选择工位时间大于平均工位时间的工位，同时随机 选择已选工位中的操作，即采用随机选择规则，以此避免算法陷入局部最优。 运用本文提出的随机有序元胞自动机算法对某汽车发动机装配实例及标杆问题的求 解，说明了算法的初始化设计和随机有序元胞进化规则的可行性。相关实验结果也说明了 针对不同规模的装配线问题，本文提出的算法可有效求得近优解或最优解，计算规模小， 求解时间短。 关键字：汽车装配线；混合模型装配线平衡；元胞自动机；有序执行规则；随机选择规则 武汉科技大学硕士学位论文第1 页 a b s t r a c t a u t o m o b i l ei n d u s t r yu n d e r g o e sa d e v e l o p m e n tf r o ms t a n d a r d i z a t i o nt od i v e r s i f i c a t i o n w i t h t h ei n t e n s i f i e dm a r k e tc o m p e t i t i o n ，m o r ev a r i e t i e so fm o d e l sa r ep r o d u c e dt om e e td i f f e r e n t l e v e l sa n dp e r s o n a l i z e du s e rd e m a n d s a u t o m o b i l ea s s e m b l yi st h ef m a lp r o c e d u r eo ft h ew h o l e p r o d u c t i o np r o c e s s ，a n dt h ed e g r e eo f w o r k l o a db a l a n c eh a sag r e a ti m p a c to nt h ep r o d u c tq u a l i t y a n dp r o d u c t i o ne f f i c i e n c y t h e r e f o r e ，i no r d e rt om e e tv a r i o u sp r o d u c td e m a n d sf r o mm a r k e ta n d i m p r o v et h ep r o d u c t i o np e r f o r m a n c e ，i t sn e c e s s a r yt oc a r r yo u ta ne l a b o r a t es t u d yo nt h e a u t o m o b i l ea s s e m b l yl i n eb a l a n c i n gp r o b l e ma n dd e s i g naf a s ta n de f f e c t i v ea l g o r i t h m i nt h i st h e s i s ，t h em i x e d - m o d e la u t o m o b i l ea s s e m b l yl i n eb a l a n c i n gp r o b l e mi ss o l v e db y t h es t o c h a s t i c a l l yo r d e r e dc e l l u l a ra u t o m a t aa l g o r i t h mv i af o u rs t e p s f i r s t , am a t h e m a t i c a l m o d e li sf o r m u l a t e dw i t ht h eo b j e c t i v e so fm i n i m i z i n gt h ep r o d u c t i o nc y c l et i m ea n di n c r e a s i n g t h eb a l a n c ee f f i c i e n c y s u b s e q u e n t l y , t h eg i v e np r o b l e mi sr e p r e s e n t e db yc e l l u l a ra u t o m a t a , w h e r et a s k s 黜c o n s i d e r e da sm o b i l ep a r t i c l e s ，w o r k s t a t i o n sa s 血e d 酣dn o d e s ，t h em e c h a n i s m o fb a l a n c i n ga s s e m b l yl i n e s t r a n s p o r t e da s e v o l u t i o nr u l e s t h i r d , t h ei n i t i a l i z a t i o ni s c o m p l e m e n t e db yh e u r i s t i cs e l e c t i o na n dt a s ka s s i g n m e n tt os p e e du pt h ei n i t i a lf e a s i b l es o l u t i o n a n di m p r o v ei t sp e r f o r m a n c e f o r t h ，a r e rd e s i g n i n gt h eg e n e r a l i z e ds w a p p i n gp r o c e s so ft a s k s b e t w e e na n yt w os t a t i o n s ，a no r d e r l ye x e c u t i o nr u l ei sp r o p o s e da c c o r d i n gt on o n - d e c r e a s i n g n u m b e ro fs w a p p e dt a s k s ，s oa st oc o n v e r g ef a s tt ot h ec u r r e n tb e s ts o l u t i o n ，a n ds t o c h a s t i c s e l e c t i o nr u l ea m o n gs t a t i o n sa n dt a s k s 铷他c o n s t r u c t e d ，w i t ht h ep u r p o s eo fa v o i d i n gb e i n g 缸p p e d i n t ol o c a lo p t i m u m i l l u s t r a t e db yac a re n g i n ea s s e m b l yl i n ea n db e n c h m a r kp r o b l e m s ，t h ec e l l u l a ri n i t i a l i z a t i o n a n ds t o c h a s t i c a l l yo r d e r e dc e l l u l a re v o l u t i o nr u l e sa r ev a l i d a t e dt ob ec o r r e c ta n da p p l i c a t i v e r e l e v a n te x p e r i m e n tr e s u l t ss h o wt h a tt h ep r o p o s e ds t o c h a s t i c a l l yo r d e r e dc e l l u l a ra u t o m a t a a l g o r i t h mg e t sn e a ro p t i m a ls o l u t i o n so ro p t i m a ls o l u t i o n sw i t h i nas h o r tt i m ef o rd i f f e r e n ts c a l e p r o b l e m s k e y w o r d s ：a u t o m o b i l ea s s e m b l yl i n e ；m i x e d - m o d e la s s e m b l yl i n eb a l a n c i n g ；c e l l u l a ra u t o m a t a ； o r d e r l ye x e c u t i o nr u l e ；s t o c h a s t i cs e l e c t i o nr u l e 武汉科技大学硕士学位论文第1 页 1 1b a c k g r o u n d c h a p t e r 1i n t r o d u c t i o n f l o wi i n ep r o d u c t i o nm a k e si tp o s s i b l ef o rt h es u c c e s s i v eo p e r a t i o n st ob ec a r r i e do u tw h i l e m o v i n gt h r o u g ht h ef a c t o r ya l o n gas i n g l ed i r e c t i o n ，w h i c hh a sb e e nq u i t cp o p u l a rf o ral o n gt i m e i nm a s sp r o d u c t i o na n db a t c hp r o d u c t i o n i nf l o wl i n ep r o d u c t i o n ，m i n i m a li n v e n t o r yi se s s e n t i a l t oe n s u r et h ec o n t i n u o u sa c t i v i t y a l s o ，a s s e m b l yl i n ep r o d u c t i o ni sa ne x t r e m ev e r s i o no ff l o w l i n ep r o d u c t i o n n l cf h - s ta s s e m b l yl i n ei sc r e d i t e dt oh e n r yf o r d sf o r dm o t o rc o m p a n yi n1910 s ，w h i c h h a so p e n e dt h ep r e l u d eo fm o d e mp r o d u c t i o na n dm a d eaf u n d a m e n t a lc h a n g eo ft h e m a n u f a c t u r i n gt h a tt h ee n t e r p r i s eo b t a i n e dt h el a r g e s tp r o f i t sb yp r o d u c i n gp r o d u c t sa tt h el o w e s t c o s tw i t ha s s e m b l yl i n e f o re x a m p l e t h ef o r dm o d e lt c a r , o c c u p i e dm o r et h a n5 0 o ft h e m a r k e ts h a r ew i t hs i n g l es t y l ea n dc o l o r u n d o u b t e d l y , t h ei n c r e a s i n gp r o d u c t i o no fm o d e lt r e d u c e dt h ep r o d u c t i o nc o s tl a r g e l ya n dm a d ef o r dm o t o rc o m p a n yaf o r t u n e w i t hi n t e n s i f i e dg l o b a lc o m p e t i t i o n ，f 0 柑m o d e ltc a rw a sf i n a l l yr e p l a c e db yo t h e rm o d e l s w h i c hc o u l ds a t i s f yt h ed i v e r s i f i e dc u s t o m e rd e m a n d s j u s t - i n - t i m ep u l ls y s t e m ，p u tf o r w a r db y t o y o t am o t o rt os a t i s f yv a r i o u sc u s t o m e rd e m a n d s ，f o c u s e so nt h ep r o d u c t i o no fv a i l 啊o f m o d e l so nt h es a m ea s s e m b l yl i n e j u s t - i n - t i m es t r i v e st oi m p r o v et h eb u s i n e s sr e r l r no ni n v e s t m e n t , t h ep r o d u c tq u a l i t y , a n d t h ep r o d u c t i o ne f f i c i e n c yb yf o c u s i n go nt h ec o n t i n u o u si m p r o v e m e n t w i t ht h ea p p e a r a n c eo f j u s t - i n - t i m ep r o d u c t i o n ，t h et r a d i t i o n a lm a n u f a c t u r i n gi st r a n s f o r m e df r o mm a s sp r o d u c t i o no f s i n g l em o d e lt os m a l lb a t c ho rm i x e dm o d e la s s e m b l yl i n ep r o d u c t i o nm o d e s i n c et h e n ，t h e m i x e d - m o d e la s s e m b l yl i n e ( m m a l ) h a sb e e nw i d e l yu s e d i n m a n ye n t e r p r i s e s f o r m a n u f a c t u r i n gt v s ，c o m p u t e r sa n d c a r se t e m i x e d - m o d e la s s e m b l yl i n ei sc o n f i g u r e dt op r o d u c es e v e r a lm o d e l sw i t h o u tc h a n g e o v e r 1 1 l e9 0 a lo fm m a l p r o d u c t i o ni st ok e 印ab a l a n c e da n dc o n t i n u o u sf l o ws t a t e ，r e d u c et h ei d i e t i m eo nw o r k s t a t i o na n di m p r o v et h eu t i l i z a t i o nr a t eo fw o r k e r sa n de q u i p m e r i t u n d e rt h e s p e c i f i co b j e c t i v e sa n dc o n s t r a i n t s ，m 眦i sr e o r g a n i z e db ya s s i g n i n gb a s i co p e r a t i o n st o s t a t i o n sw i t hv a r i o u sk i n d so ft e c h n i q u e s t h i sp r o c e d u r ei sa l s oc a l l e dm i x e d - m o d e la s s e m b l y l i n eb a l a n c i n g ( m m a l b ) n 坞p u r p o s eo f b a l a n c i n gi st oa v o i du n n e c e s s a r yp a u s ea n di n v e n t o r y d u r i n gp r o d u c t i o np r o c e s s n l er e a s o n a b l e n e s so fp r o d u c t i o no r g a n i z a t i o ni sc l o s e l yr e l a t e dt o t h eq u a n t i t y , q u a l i t ya n dc o s to fp r o d u c t s t h u s ，t h es t u d yo nm i x e d - m o d e la s s e m b l yl i n e b a l a n c i n gp r o b l e m ( m m a l b p ) i sq p 沁n e c e s s a r y 1 2l i t e r a t u r er e v i e w a na s s e m b l yl i n ec o m p o s e db yac o l l e c t i o no fs e q u e n t i a lw o r k s t a t i o n s ，w h i c ha r et y p i c a l l y c o n n e c t e db yac o n t i n u o u sm a t e r i a l - h a n d l i n gs y s t e m ，i su s e di nm a s sp r o d u c t i o ns y s t e m st o i n c r e a s et h ep r o d u c t i o ne f f i c i e n c ya n de f f e c t i v e n e s s a s s e m b l yl i n eb a l a n c i n gh a ss i g n i f i c a n t i m p a c to nt h ep e r f o r m a n c eo f t h ea s s e m b l yl i n e 第2 页武汉科技大学硕士学位论文 s i n c eh e l g e s o n ( 1 9 5 4 ) t 1 p e r f o r m e dt h ee a r l i e s ta n a l y s i sa b o u tt h ea s s e m b l yl i n eb a l a n c i n g p r o b l e m ( a l b p ) ，m a n ys o l u t i o na p p r o a c h e sh a v eb e e np r o p o s e d ，a sd e s c r i b e di nd e t a i l si nt h e f o l l o w i n gs e c t i o n s 1 2 1a s s e m b l yl i n eb a l a n c i n ga n dc l a s s i f i c a t i o n t h ec l a s s i c a la l b pw a sf i r s tp u b l i s h e di n19 5 5b ys a l v e s o n l 二j 。w h op r e s e n t e da m a t h e m a t i c a lm o d e la n das o l u t i o np r o c e d u r e ，f o l l o w e db yj a c k s o n ( 19 5 6 ) 川，b o w m a n ( 19 6 0 ) t j ， a n dh u ( 1 9 6 1 ) t ) 。s i n c et h 锄a l b ph a sa t t r a c t e dal o to f r e s e a r c h e r s i n1 9 8 9 ，g h o s ha n dg a g n o n ( 1 9 8 9 ) 6 1c l a s s i f i e da l b pi n t of o u rc a t e g o r i e sa sd e p i c t e db y f i g 1 1 ：s i n g l em o d e ld e t e r m i n i s t i c ( s m d ) ，s i n g l em o d e ls t o c h a s t i c ( s m s ) ，m u l t i m i x e d m o d e ld e t e m l m i s t i cf m m d ) a n dm u l t 们i x e dm o d e ls t o c h a s t i c ( m m s ) f i g u r e1 1c l a s s i f i c a t i o no f t h ea s s e m b l yl i n eb a l a n c i n gp r o b l e m s t h ed e t e r m i n i s t i ca l b pc a nb es t a t e da sf o l l o w s ：g i v e naf i n i t es e to ft a s k s i nw h i c he a c h t a s kh a saf i x e dp r o c e s s i n gt i m e ，a n das e to fp r e c e d e n c er e l a t i o n sw h i c hs p e c i f yt h ep e r m i s s i b l e o r d e r i n g so ft h et a s k s t h ep r o b l e mi st oa s s i g nt h et a s k st oo r d e r e ds t a t i o n ss u c ht h a tt h e p r e c e d e n c et e l a t i o n sa r es a t i s f i e da n ds o m em e a s u r eo fp e r f o r m a n c ei so p t i m i z e d t h es t o c h a s t i ca l b pc a nb es t a t e da sf o l l o w s ：g i v e naf i n i t es e to ft a s k s i nw h i c he a c ht a s k h a sap r o c e s s i n gt i m ed i s t r i b u t e da c c o r d i n gt oap r o b a b i l i t yd i s t r i b u t i o na n das e to fp r e c e d e n c e r e l a t i o n sw h i c hs p e c i f yt h ep e r m i s s i b l eo r d e r i n g so ft h et a s k s 1 1 1 ep r o b l e mi st oa s s i g nt h et a s k s t oo r d e r e ds t a t i o n ss u c ht h a tt h ep r e c e d e n c er e l a t i o n sa r es a t i s f i e da n ds o m em e a s u r eo f p e r f o r m a n c ei so p t i m i z e d 1 1 1 es v e r s i o no ft h ep r o b l e ma p p l i e st os i n g l e - m o d e la s s e m b l yl i n e sw h e r et h et a s k p r o c e s s i n gt i m e sa r ec o n s t a n ta n dd e t e r m i n e d t h i si st h es i m p l e s tv e r s i o no f t h ea l b p t h es m s c a t e g o r yi n t r o d u c e st h ec o n c e p to f t a s kt i m ev a r i a b i l i t y 1 1 1 i sv e r s i o nr e p r e s e n t s t h em a n u a la s s e m b l yl i n e sm o r er e a l i s t i c a l l yw h e r et a s kp r o c e s s i n gt i m e sa r es e l d o mc o n s t a n t s t h ev a r i a b i l i t yo ft a s kt i m e sc a l lb er a t h e rl a r g er e l a t i v et ot h e i rm e a n s t h i si se s p e c i a l l yt r u ef o r t h et a s k sw h i c ha r ec o m p l e xa n dd e m a n dh i g hl e v e l so fs k i l la n dc o n c e n t r a t i o n t h e n 仍v e r s i o no ft h ep r o b l e mi n t r o d u c e st h ec o n c e p to fp r o d u c i n gm o r et h a no n e p r o d u c to nas i n g l e1 i n e m u n i m o d e l l i n e sa 阳i n v o l v e di nt h ep r o d u c t i o no f t w oo rm o r es i m i l a r t y p e so fp r o d u c t sp r o d u c e ds e p a r a t e l yi nb a t c h e s ，w h e r e a sm i x e d m o d e ll i n e sp r o d u c et w o o r m o r es i m i l a rp r o d u c t ss i m u l t a n e o u s l y t h e 删si st h em o s tc o m p l e xv e r s i o na n df e w e rr e s e a r c h e sh a v eb e e nc o n d u c t e do nt h e 删s p r o b l e mc o m p a r e dt oo t h e rv e r s i o n s 1 1 1 i st h e s i sd e a l sw i t ht h em i x e d m o d e la s s e m b l yl i n eb a l a n c i n gp r o b l e m ，w h i c hb e l o n g st o 武汉科技大学硕士学位论文第3 页 t h em u l t i m i x e dm o d e ld e t e r m i n i s t i cc a t e g o r y 1 2 2m e t h o d o l o g i c a lt e c h n i q u e s s i n c et h ea l b pf a l l si n t ot h en p h a r dc l a s so fc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m s ( g u t j a h ra n dn e m h a u s e r , 19 6 4 ) 0 ，n u m e r o u sr e s e a r c h e s h a v eb e e nd i r e c t e dt o w a r d st h e d e v e l o p m e n to f h e u r i s t i cp r o c e d u r e s ，e x a c ta l g o r i t h m s ，a n ds w a r mi n t e l l i g e n c ea l g o r i t h m s h e u r i s t i cp r o c e d u r e s a r c u s ( 19 6 6 ) t 8 】c o n s i d e r e dm i x e d - m o d e ll i n e sa so n eo ft h ec o m p l e xf o r m so ft h em i x e d m o d e ld e t e r m i n i s t i cp r o b l e m ，a n dd e v e l o p e dt h es i n g l em o d e ld e t e r m i n i s t i cp r o b l e mu s i n g a v e r a g et a s kt i m e s ，w h i c ha 他o b t a i n e db ym u l t i p l y i n gt h e t a s kt i m e sa n dt h er e l a t i v e f r e q u e n c i e so f t h er e l a t e dm o d e l s h ea l s oc o n s i d e r e dt h et i m e sn e c e s s a r yf o rc h a n g i n gt o o l s a n dw o r k e r sp o s i t i o nb e t w e e nu n i t s ：t h ec h a n g i n gt i m e sa r cm u l t i p l i e db yt h er e l a t i v e f r e q u e n c i e sa n dt h e na d d e dt ot h es t a t i o nt i m e s h o w e v e r , n oe x p e r i m e n t a lr e s u l t sw e r e r e p o r t e d t h o m o p o u l o s ( 19 7 0 ) 【川p r o p o s e da na p p r o a c hf o rs m o o t h e n i n gf o rt h es t a t i o nw o r k l o a db y t a s ka s s i g n m e n t si nm i x e d - m o d e ll i n e s t os i m p l i f yt h ep r o b l e mo fm i x e dm o d e l s ，a ne q u i v a l e n t s i n g l em o d e l w a so b t a i n e db yc o m b i n g t h ep r e c e d e n c ed i a g r a m so ft h em o d e l s f o re a c hs t a t i o n ， t h ep r o c e d u r es e a r c h e daf i n i t en u m b e ro ff e a s i b l ec o m b i n a t i o n so ft a s k su n t i la na c c e p t a b l e c o m b i n a t i o nw a so b t a i n e d t h e n ，a na t t e m p tt om i n i m i z ef l u c t u a t i o n si ns t a t i o nt i m e so fa n y g i v e nm o d e l w a sm a d eb ys e l e c t i n gt h ef e a s i b l ec o m b i n a t i o n c h a k r a v a r t ya n ds h r u b ( 19 8 6 ) 【1 0 】d e v e l o p e dap r o c e d u r ew h i c hi n t e g r a t e sl a b o rc o s tw i t h i n - p r o c e s si n v e n t o r yh o l d i n gc o s ta n dm a c h i n es e t u pc o s tf o rm i x e d m o d e ld e t e r m i n i s t i cp r o b l e m p r e c e d e n c ed i a g r a m so ft h em o d e l sw e r ec o m b i n e dt ob eas i n g l e - m o d e l t a s k sw e r eg r o u p e dt o f o r mt h es t a t i o n su s i n ge i t h e rs h o r t e s t - p a t ha p p r o a c ho ras i n g l e - p a s sh e u r i s t i cp r o c e d u r e z h ua n dd i n g ( 2 0 0 0 ) 1 1 1c o n s i d e r e dt h et w o s t a g ep a r t - l e v e lv a r i a t i o na sah e u r i s t i cs o l u t i o n a p p r o a c ha n dd i s c u s s e dt h ee f f e c to fm i n i m i z i n gt h ep r o d u c tl e v e lv a r i a t i o no nm i n i m i z i n gt h e p a r t - l e v e lv a r i a t i o n at r a n s f o r m e dt w o s t a g es o l u t i o na p p r o a c hf o rn l ep a r t l e v e lp r o b l e mw a s s h o w nt ob eb e t t e rt h a nt h eo n e - s t a g em e t h o di ns o l u t i o nq u a l i t y k a r a b a t ia n ds a y i n ( 2 0 0 3 ) 1 2 】f o r m u l a t e dt h em i x e d - m o d e la s s e m b l yl i n eb a l a n c i n gp r o b l e m w i t ht h eo b j e c t i v eo fm i n i m i z i n gc y c l et i m eb yu s i n gt h ec y c l i cs e q u e n c i n gi n f o r m a t i o n t h e y p r o p o s e da m a t h e m a t i c a lm o d e la n dah e u r i s t i ca p p r o a c ht om i n i m i z et h em a x i m u mc y c l et i m e d e n i za n dm e l i h ( 2 0 0 8 ) 1 副d e v e l o p e dah e u r i s t i ca l g o r i t h mb a s e do nl a g r a n g e a nr e l a x a t i o n t os o l v et h em i x e d - m o d e lf l o wl i n es e q u e n c i n gp r o b l e mt om i n i m i z em a k e s p a n ，n l c yf o c u s e do n p r o d u c t - f r e e d ，r a t e s y n c h r o n o u sl i n e sw i t hv a r i a b l el a u n c h i n ga n dam i x e d - m o d e lf l o wl i n e s e q u e n c i n gp r o b l e mb e i n gc o n s i d e r e d e x a c ta l g o r i t h m s d u et ot h el a r g ec o m p u t a t i o n a la n ds t o r a g er e q u i r e m e n t so fm i x e d - m o d e la s s e m b l yl i n e b a l a n c i n gp r o b l e m ，f e wr e s e a r c h e r sh a v ea t t e m p t e dt oo b t a i nt h eo p t i m a ls o l u t i o n r o b e r t sa n dv i l l a ( 1 9 7 0 ) 1 4 】c o n s t r u c t e da ni n t e g e rp r o g r a m m i n gm o d e l ；t h eo b j e c t i v ei st o m i n i m i z et h et o t a li d l et i m e d u et ot h ee x c e s s i v en u m b e ro fc o n s t r a i n t sa n dv a r i a b l e s ，t h e yg a v e 第4 页武汉科技大学硕士学位论文 ac o n c l u s i o nt h a tt h ef o r m u l a t i o nw a sm o r et h e o r e t i c a lt h a np r a c t i c a l m i l t e n b u r g ( 19 8 9 ) 0 1 5 jf o r m u l a t e dt h em i x e d