《并行遗传算法在车间作业调度问题上的应用》由会员分享，可在线阅读，更多相关《并行遗传算法在车间作业调度问题上的应用（48页珍藏版）》请在金锄头文库上搜索。
1、山东师范大学硕士学位论文摘要车间作业调度( J S S P ) 在企业生产经营活动中占有十分重要的地位。生产调度系统也是C I M S 、E R P 等系统中的重要组成部分。生产调度位于C I M S 体系结构中的中间层，是控制与管理一体化的接合部。向上要给企业经营战略决策层提供决策依据，向下要安排生产加工任务，指导监督控制层的动作。因些，生产调度是实施C I M S 的关键。由于车间作业调度问题是一个典型的N P h a r d 问题，因此受到学术界和工业界的广泛关注。对它的研究具有很高的理论意义和实际意义。迄今为止，已有很多关于车间作业调度问题的研究方法，如分枝定界法、基于优先规则的启发式
2、方法，但是常见的J S S P 的困难性和复杂性使传统的搜索方法很难在合理的时间内找到最优解。近年来，已经引进了一些人工智领域的新技术来解决这些问题，如模拟退火( S A ) 、禁忌搜索( T A ) 、人工神经网络( A N N ) 、遗传算法( G A ) 等等。遗传算法是一类借鉴生物界的进化规律演化而来的随机化搜索方法，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，己被人门广泛地应用于组合优化、机器学习、信号处理、自
3、适应控制和人工生命等领域。并行遗传算法( P G A ) 是过去十几年以来G A 研究的热点之一，无论是理论还是应用上都取得一些成熟的成果。因此本文将P G A 用于求解J S S P 调度问题，本文主要有以下几项内容：( 1 ) 介绍分析了车间作业调度的问题描述、模型表示、特点以及对它的研究方法和研究现状。本文将J S S P 的研究方法分为两大类，最优化方法和近似启发式方法；( 2 ) 作为并行遗传算法的基础，介绍了标准遗传算法的来源，生物学方面的背景，编码方式，适应度函数，基本遗传操作( 选择、交叉、变异) ，基本参数的设置原则；( 3 ) 介绍了并行遗传算法的分类，以及他们各自发展的历
4、史现状，粗粒度并行遗传算法的迁移策略，分为两种同步迁移和异步迁移；( 4 ) 详细介绍了针对J S S P 的特点设计的新的粗粒度并行遗传算法，主要包括算法流程，编码方式，遗传操作，迁移策略。最后，对两个经典的J S S P 的实例即F T 6 x 6 、L A 0 1 ，进行了仿真实验。通过对结果的分析，得出设计的新算法比普通的遗法效率高的结论。山东师范大学硕士学位论文2关键字：并行遗传算法，车间作业调度，编码，迁移策略分类号：T P 3 9 1知识水坝damdocdamdoc为您倾心整理(小店)(QQ2218108823)山东师范大学硕士学位论文A B S T R A C TJ o b s
5、 h o ps c h e d u l i n gp l a y sag r e a tr o l ei nt h ep r o d u c t i o na c t i v i t yo fa l le n t e r p r i s e ，j o b s h o ps c h e d u l i n gs y s t e mi sa l s oag r e a tp a r to fC I M So rE R EP r o d u c t i o ns c h e d u l i n gi s 缸t h em i d d l el a y e ri nt h eC I M Ss y s t
6、 e ms t r u c t u r e w h i c hi st h ej o i n to fc o n t r o la n dm a n a g e m e n t O no n eh a n d , i tw i l ls u p p l yd e c i s i o n sf o rt h ee n t e r p r i s e ；o nt h eo t h e rh a n d ，i tw i l la r r a n g ep r o d u c t i o nt a s k sa n ds u p e r v i s et h ec o n t r o ll a y e
7、 r S ot h ep r o d u c t i o ns c h e d u l i n gi st h ek e yo ft h eC I M S J S S Pi sat y p i c a lN P h a r dp r o b l e m ，s oi ta t t r a c t sg r e a ta t t e n t i o nf r o mb o t ht h ea c a d e m i aa n di n d u s t r y T h e r e f o r e ，t h es t u d yo fj o bs h o ps c h e d u l ei so fg
8、 r e a tt h e o r e t i c a la n dp r a c t i c a li m p o r t a n c e S of a rt h e r eh a v eb e e nm a n yr e s e a r c hm e t h o d st od e a lw i t hJ S S P , s u c ha sb r a n c h - b o u n dm e t h o da n ds o m eh e u r i s t i cp r o c e d u r e sb a s e do np r i o r i t yr u l e s ，b u tt
9、 h ed i f f i c u l t ya n dc o m p l e x i t yo fg e n e r a lJ S S Pm a k e si tv e r yh a r df o rt h ec o n v e n t i o n a ls e a r c h - b a s e dm e t h o d st of i n da no p t i m a ls o l u t i o ni nr e a s o n a b l et i m e N e wt e c h n i q u e se m e r g i n gf r o mt h ef i e l do fa
10、 r t i f i c i a li n t e l l i g e n c eh a v eb e e ni n t r o d u c e dt oa d d r e s st h e s ep r o b l e m si nr e c e n ty e a r s ，s u c ha ss i m u l a t e da n n e a l i n g ，t a b us e a r c h ，a r t i f i c i a ln e u r a ln e t w o r ka n dg e n e t i ca l g o r i t h m ，a n ds oo n T h
11、 eG e n e t i cA l g o r i t h m ( G A ) i sar a n d o ms e a r c hm e t h o di m i t a t i n gt h er u l e so ft h eo r g a n i cw o r l d T h em a i nd i s t i n g u i s h i n gf e a t u r ea r ea sf o l l o w i n g ：o p e r a t i n go nt h ec o m p o s i t i o nt a r g e t , r e q u e s t i n gn
12、og u i d ea n df u n c t i o nc o n t i n u a n c e ；h a v i n gc o n c e a lc o n c u r r e n c ea n ds p l e n d i dc a p a b i l i t yw i t ht h eb e a e rs i t u a t i o na saw h o l e ；a d o p t i n ga p p r o x i m a t e l yt h eg u i d i n go ft h em o s ts p l e n d i dm e a n so fl e a d i
13、n g ，b e i n ga b l et og a i nv o l u n t a r i l ya n dt h es e a r c h i n gr o o mt h ed i r e c t i o no p t i m i z e s ，s e l f - a d o p t i n gt h er e g u l a t i o nd i r e c t i o no f s e a r c h ，n o tn e e d i n gc e r t a i nr e g u l a t i o n T h ef e a t u r e so f G Ah a v eb e e
14、 nw i d e l yu s e da p p l i e di nt e r r i t o r i e ss u c ha so p t i m i z a t i o n , m a c h i n el e a r n i n g ，t r e a t m e n to fs i g n a l ，s e l f - a d o p t i o nc o n t r o l ，a r t i f i c i a le x i s t e n c ea n dS Oo n P a r a l l e lG e n e t i cA l g o r i t h m 伊G A ) i s
15、o n eo f t h er e s e a r c hf o c u s e so f G Af r o mp a s t1 0y e a r s ，a n dh a si m p r o v e dal o tb o t hi nt h e o r ya n da p p l i c a t i o n T h i sp a p e ru s eP G At os g l v eJ S S Ps c h e d u l i n gp r o b l e m ，a n dt h em a i nc o n t e n ti s 邵f o l l o w i n g ：( 1 ) I n t
16、 r o d u c ea n da n a l y z es o m ea s p e c t sa b o u tJ o b s h o ps c h e d u l i n gp r o b l e m ，s u c ha sd e s c r i p t i o no ft h ep r o b l e m ，e x p r e s s i o no ft h em o d e l ，f e a t u r e sa n dm a i nr e s e a r c hm e t h o d so nJ S S ET h i sp a p e rd i v i d ea l lt h em e t h o d si n t ot w oc l a s s i f i c a t i o n ，o p t i m i z a t i o nm e t h o da n dh e u r i s t i cp r o c e d u r e s ；( 2 ) I n t r o d u c et h eS i
