基于裝配約束的機(jī)械產(chǎn)品生產(chǎn)調(diào)度算法研究.pdf

1、大連理工大學(xué)碩士學(xué)位論文基于裝配約束的機(jī)械產(chǎn)品生產(chǎn)調(diào)度算法研究姓名：趙國(guó)凱申請(qǐng)學(xué)位級(jí)別：碩士專業(yè)：機(jī)械電子工程指導(dǎo)教師：王福吉20091216基于裝配約束的機(jī)械產(chǎn)品生產(chǎn)調(diào)度算法研究R e s e a r c ho n P r o d u c t i o nS c h e d u l i n g A l g o r i t h mf o r M e c h a n i c a lP r o d u c t sB a s e d o n A

2、 s s e m b l y C o n s t r a i n t sA b s t r a c tP r o d u c t i o ns c h e d u l i n g i s a l li m p o r t a n tp a r ti nm e c h a n i c a lp r o d u c t s m a n u f a c t u r i n g ，a n di th a sd i r e c tr e l a

3、t i o n s h i pw i m p r o d u c t i o n c y c l e ，p r o d u c t i o nc o s ta n de n t e r p r i s e s u r v i v a b i l i t y ．E x c e l l e n tp r o d u c t i o ns h e d u l i n gs c h e m e sa r eh e l p f u lt oe n

4、 t e r p r i s ei na l l o c a t i n gd i f f e r e n tt y p ep r o d u c t i o nr e s o u r c er e a s o n a b l y ，r e d u c i n g p r o d u c t i o nc o s t ，r e a l i z i n gj u s t —i n —t i m ep r o d u c t i o na

5、n di m p r o v i n g m a c k e t c o m p e t i t i v e n e s s ．I n t h e p a s t ，m o s t o fr e s e a r c h o n p r o d u c t i o ns c h e d u l i n g f o c n s e do nJ o b - s h o p S c h e d u l i n gP r o b l e m -

6、- J S P w i t h o n tc o n s i d e r i n ga s s e m b l ys t a g e o fp r o d u c t s ．A s s e m b l y c o n s t r a i n t s o fm e c h a n i c a l p r o d u c t s m u s t b e c o n s i d e r e d i np r o d u c t i o n s

7、 c h e d u l i n g b e c a u s em e c h a n i c a l p r o d u c t s ’a r e m o s t l ya s s e m b l y t y p e o n e s ．S oa n o t h e r s c h e d u l i n gp r o b l e md e r i v e s - - A J S P ( A s s e m b l y J o b —s

8、 h o pS c h e d u l i n gP r o b l e m ) w h i c hi sl e s si n v e s t i g a t e d ．R e s e a r c hi nt h sp a p e r f o c u s e s o n r e l a t e da l g o r i t h m f o r A J S P a n dh a s v e r yi m p o r t a n tp r

9、a c t i c a l s i g n i f i c a n c e ．I n a d d i t i o n , p r o b l e mm o d e l i n g a n da l g o r i t h m o p e r a t o r sd e s i g n i n g a r em o r e d i f f i c u l t f o re x i s t a n c eo f s t r o n ga s

10、s e m b l yc o n s t r a i n t s ，S O t h e r e s e a r c ha l s oh a s g r e a tt h e o r y v a l u e ．F i r s t l y ，t h ep a p e rd e s c r i b e sa s s e m b l yj o b —s h o p s c h e d u l i n gp r o b l e mi nd e t

11、 a i lt h r o u g hm a t h e m a t i c a lm o d e l i n ga n dg i v e st h ec l a s s i c a l a s s e m b l ys t r u c t u r ea n d a s s e m b l yc o n s t r a i n t sr e l a t i o n s h i p ．T h e nt h e e n c o d i n

12、gs c h e m ea n ds e l e c t i o n o p e r a t o ra r e b o t h d e t e r m i n e dw h e ns u m m a r i z i n gt h ek e y t e c h n o l o g ya n de v o l u t i o np a r a m e t e r so fg e n e t i ca l g o r i t h m ( G

13、A ) ，a n ds e v e r a lk i n d so ff i t n e s sf u n c t i o n s a l ed e s i g n e d ．T w og e n e t i ca l g o r i t h m sa r ep r o p o s e df o rA J S P - - E n t i r e S o l u t i o n S p a c e G e n e t i c A l g

14、o r i t h m a n d F e a s i b l e S o l u t i o n S p a c e G e n e t i cA l g o r i t h m ( F S S G A ) ．T h e d e s i g n o f r e p a i r o p e r a t o r i st h em o s t d i f f i c u l t p o i n t i n d e s i g n i n

15、g e n t i r es o l u t i o ns p a c e g e n e t i ca l g o r i t h m ．T w on e w r e p a i ro p e r a t o r sT D R A ( T o p - D o w n R e c u r s i v e l yA d j u s t m e n t ) a n d G E ( G e n e s E x c h a n g e B a

16、s e d o n F a t h e r L i n k —L i s t ) a r ep r o p o s e d i n t h er e s e a r c h ．T h e ya r e c o m p a r e di n d e t a i l 、歷廿l o p e r a t o rb a s e d o n D e s i g n S t r u c t u r e M a t r i x - - D S M i

17、ni n f o r m a t i o ne n t r o p y l o s sa n d c l l r o m o s o m em a p ，a n dt h e r e s u l t ss h o w t h a tT D R A a n dG E C a nr e s e r v ep o p u l a t i o nd i v e r s i t yb e t t e rt h a nD S M i n G A ．

18、S u b s e q u e n t l y ，s o l u t i o n s p a c es i z e i sa n a l y z e da n d c o m p u t i n gm e t h o d i s i l l u s t r a t e d b ye x a m p l e ，a n di t ’Sp r o v e dt h a tf o rA J S Pt h ef e a s i b l es o

19、l u t i o ns p a c e s i z ei sm u c h s m a l l e r t h a n t h e e n t i r e o n e ．B a s e do n t h e a b o v e c o n c l u s i o n ,t h ef e a s i b l es o l u t i o n s p a c e g e n e t i ca l g o r i t h m i sp r

20、o p o s e da n dc o r r e s p o n d i n gf e a s i b l es o l u t i o ns p a c e o p e r a t o r s a r ed e s i g n e d t os e r v eF S S G A ．I n t h a tc a s e ，t h es e a r c h i n gs o l u t i o n s p a c e i sm u c