（计算机软件与理论专业论文）利用共生算法求解柔性作业调度问题.pdf

剧情帅好做使用授鼬说明1 y 1 1 j l l l l l i i l l 嬲炒 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 三 论文作者签名：塑 日 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：二委k 一导师签名： 期： ， 、i，0 山东大学硕士学位 目录 摘要i a b s t r a c t 第l 章绪论1 1 1 研究的背景和意义l 1 2 论文所做的工作以及组织形式l 第2 章作业调度介绍3 2 1 作业调度分类特点3 2 2 调度类型4 2 3 柔性作业调度问题5 2 4 作业调度优化方法5 2 5 国内外研究现状及存在问题6 第3 章遗传算法理论一8 3 1 遗传算法简介8 3 1 1 串行运算遗传算法一9 3 1 2 编码和解码9 3 1 3 适应度函数。9 3 1 4 常用算子1 0 3 2 遗传算法的特点1 1 3 3 遗传算法改进和共生算法1 2 3 4 遗传算法的发展和研究现状1 3 3 5 小结1 5 第4 章柔性作业调度问题1 6 4 1 问题描述1 6 4 2 调度指标1 8 4 3 数学模型1 9 第5 章共生算法求解柔性作业调度问题2 2 5 1 共生算法框架2 2 山东大学硕士学位论文 5 2 流程安排表示2 3 5 3 作业调度表示2 7 5 4 遗传算子2 9 5 4 1 交叉算子2 9 5 4 2 变异算子31 5 5 适应值函数3 2 第6 章算法改进与实验分析3 4 6 1n m x 算子3 4 6 2 实验数据和参数3 5 6 3 实验结果和分析_ 3 6 6 3 1 任务属性3 8 6 3 2 最优加工时间4 0 6 3 3 平均加工时间4 1 6 3 4 标准方差分布4 2 6 3 5 搜索能力比较4 2 6 3 6n m x 算子实验分析4 5 第7 章结束语4 6 参考文献4 8 附录5 3 致谢5 8 攻读硕士期间发表的学术论文目录5 9 一 ， i 山东大学硕士学位论文 皇皇! ! ! 曼詈詈! 曼量皇皇! ! ! ! ! ! 曼曼! ! ! ! ! ! ! ! 詈詈詈曼皇! ! ! ! 曼墨皇! 曼皇! ! ! ! ! ! ! ! ! 曼曼曼曼! ! ! 鼍曼詈詈! ! 皇! ! ! ! ! ! ! ! ! ! ! ! ! 皇曼量 t a b l eo fc o n t e n t s a b s t r a c ti nc h i n e s e 】【 a b s t r a c ti ne n g l i s h c h a p t e r li n t r o d u c t i o n 1 1 1b a c k g r o u n d l 1 2m a i nw o r ka n d o r g a i n z a t i o n 1 c h a p t e r 2i n 仃o d u c t i o nt oj o bs c h e d d i n g ，3 2 1c l a s s i f i c a t i o na n dc h a r a c y e ro fj o bs c h e d u l i n gp r o b l e m 3 2 2c a t e g o r yo f j o bs c h e d u l i n g 4 2 3f l e x i b l ej o bs c h e d u l i n gp r o b l e m 5 2 4o p t i m i z a t i o nm e t h o df o rj o bs c h e d u l i n gp r o b l e m 5 2 5c u r r e n tr e s e a r c ha n dp o t e n t i a lp r o b l e m s 6 c h a p t e r 3t h e o r yo fg e n e t i ca l g o r i t h m 8 3 1i n t r o d u c t i o nt og e n e t i ca l g o r i t h m 8 3 1 1s e q u e n t i a lg e n e t i ca l g o r i t h m 9 3 1 2e n c o d ea n dd e c o d e 9 3 1 3f i t n e s sf u n c t i o n 9 3 1 4g e n e t i co p e r a t o r 1 0 3 2c h a r a c t e ro fg e n e t i ca l g o r i t h m j ll 3 3i m p r o v e m e n to fg e n e t i ca l g o r i t h ma n ds y m b i o t i ce v o l u t i o n a r ya l o g r i t h m 1 2 3 4h i s t o r yo f g e n e t i ca l g o r i t h m 1 3 3 5c o n c l u s i o n 11 ； c h a p t e r 4f l e x i b l ej o bs c h e d u l i n gp r o b l e m 1 6 4 1d e s c r i p t i o n 1 6 4 2s c h e d u l i n gi n d e x ：1 8 4 3m a t h e m a t i c a lm o d e l 1 9 c h a p t e r 5as y m b i o t i ce v o l u t i o n a r ya l g o r i t h mf o rf j s p 2 2 5 1f r a m e w o r ko fs y m b i o t i ce v o l u t i o n a r ya l g o r i t h m 2 2 山东大学硕士学位论文 5 2r e p r e s e n t a t i o no f p r o c e s s p l a n n i n g 2 3 5 3r e p r e s e n t a t i o no f j o bs c h e d u l i n g 2 7 5 4g e n e t i co p e r a t o r 2 9 5 4 1c r o s s o v e ro p e r a t o r 2 9 5 4 2m u t a t i o no p e r a t o r 31 5 5f i t n e s sf u n c t i o n 3 2 c h a p t e r 6i m p r o v e m e n ta n da n a l y s i s 3 4 6 2d a t aa n dp a r a m e t r so f e x p e r i m e n t 3 5 6 3e x p e r i m e n tr e s u l ta n da n a l y s i s 3 6 6 3 1a t t r i b u t e so f t a s k s 3 8 6 3 2c o m p a r i s o no f o p t i m a lm a k e s p a nt i m e 4 0 6 3 3c o m p a r i s o no f a v e r a g em a k e s p a nt i m e 4 1 6 3 4c o m p a r i s o no fs t a n d a r dd e v i a t i o n 4 2 6 3 5c o m p a r i s o no f a v e r a g em a k e s p a nt i m e 4 2i - 6 3 6a n a j y s i so f n m xo p e r a t o r 4 5 c h a p t e r 7c o n c l u s i o n 4 6 d r e f e r e n c e s 4 8 a p p e n d i x 5 3 a c k n o w l e g e m e n t s 5 8 p u b l i s h e da c a d e m i c p a p e r s 5 9 l v 只 f 一 山东大学硕士学位论文 摘要 车间作业调度问题是制造系统的一个研究热点，在理论研究方面也是最为困 难的问题之一。此问题具有约束性，非线性，不确定性和大规模性，已被证明调 度问题是n p h a r d 问题，很难求得最优解。人们研究和发展了多种优化算法来 处理此类问题：比如模拟退火、遗传算法、禁忌搜索、神经网络等。这些优化方 法模拟或运用自然现象、过程和规律，其理论涉及数学，物理，人工智能等多个 学科。 在车间作业调度的过程中，要根据生产目标和约束条件，为每个加工对象确 定具体的加工路径以及各具体操作的执行机器和时间。传统的作业调度问题的描 述是：刀个工件( j o b ) 要在m 台机器( m a c h i n e ) 上加工，每个工件需要经过多道工 序或者是包含多个操作( o p e r a t i o n ) ，每个操作只能够由某台特定机器上完成。问 题的目标是求刀个工件在每台机器上最优的加工顺序，使最大流程时间达到最 小。当然还有其他一些变种，比如规定n 个工件在m 台机器上的加工顺序相同 或不同。传统的作业调度一般假定对每个工件只有一个可行的加工方案，即作业 处理计划中没有柔性，而在现在的制造系统中，出现了各种作业柔性。大多数作 业具有大量的柔性加工方式和工序。即可以选择不同的工序序列来完成加工此工 件，同时实现某个工序存在由多个机器的组成的集合。在本文中，将对这种出现 在新的制造系统的作业调度问题运用共生遗传算法来进行计算。 柔性作业调度问题( f l e x i b l ej o bs c h e d u l i n gp r o b e l r n , f j s p ) 是传统作业调度问 题的扩展，也是现实中柔性制造系统所面临的问题。本文将柔性作业调度问题分 解成为流程安排( p r o c e s sp l a n n i n g ) ；乖 1 作业调度( j o bs c h e d u l i n g ) 两个子问题，然后 为两个子问题分别设计了不同的染色体表示，并且提出一种共生算法将两个子问 题放在一起进行求解。为了提高搜索效率，本文设计了基于邻域的多体交叉算子 ( n m x ) 。实验表明本文提出的共生算法能够很好地解决柔性作业调度问题。 关键字：柔性；流程安排：作业调度；共生算法；领域多体交叉 山东大学硕士学位论文 a b s t r a c t a sac l a s so f t y p i c a lp r o d u c t i o ns c h e d u l i n gp r o b l e m s ，j o bs c h e d u l i n g p r o b l e m ( j s p ) h a sb e e np r o v e dt ob eo n eo ft h es t r o n g e s tn p - c o m p l e t ec o m b i n a t o r i a l o p t i m i z a t i o np r o b l e m s b e c a u s ei t sv e r yd i f f c u l tt of i n dt h eo p t i m i a lr e s u l t , m a n y r e s e a r c h e r sh a v e p r o p o s e dm a n yo p t i m i z a t i o na l g o r i t h m s s u c ha ss i m u l a t e d a n n e a l i n g ，g e n e t i ca l g o r h t m ，t a b us e a r c ha n dn e u r a ln e t w o r kt os o l v ei t i nt h ej o bs c h e d u l i n gp r o b l e m , w eh a v et od e t e r m i n t eh o we a c h j o bi sp r o c e s s e d a n dh o wt h ed i f f e r e n to p e r a t i o ni sa r r a n g e db e c a u s ee a c hm a c h i n ec a no n l yp r o c e s s o n eo p e r a t i o na to n et i m e i nt h et r a n d i t i o n a lj o bs c h e d u l i n gp r o b l e m ，j o b sw i l lb e p r o c e s s e db ymm a c h i n e s ，e a c hj o bc o n s i s t so fm a n yo p e r a t i o n s ，a n de a c ho p e r a t i o n c a no n l yb ep r o c e s s e db yo n es p e c i f i cm a c h i n e t h eo b je c ti st of i n dao p t i m a o p e r a t i o ns e q u e n c ew h i c hm i n i m i z et h em a x i m a lt i m eo fa l lt h em a c h i n e s h o w e v e l t h et r a n d i t i o n a lj o bs c h e d u l i n gp r o b l e md o e s n th a v ea n yf l e x i b i l i t yw h i c hm e a n sa j o b c a no n l yb ep r o c e s s e di nas p e c f i co p e r a t i o ns e q u e n c e a tt h es a m et i m e ，t o d a y s m a n u f a c t u r es y s t e m sh a v em a n yd i f f e r e n tf l e x b i l i t i e ss u c h 舔e a c hj o bc a nb ed o n ei n s e v e r a ld i f f e r e n to p e r a t i o ns e q u e n c e s ，a n de a c ho p e r a t i o nc o u l db ep r o c e s s e db y s e v e r a ld i f f e r e n tm a c h i n e s 谢md i f f e r e n tt i m e s s oi nt h ep a p e r ，w ea r eg o i n gt ou s ea s y m b i o t i ce v o l u t i o n a r ya l g o r i t h mt os o l v et h i sk i n do fj o bs c h e d u l i n gp r o b l e m 、i t h f l e x i b i l i t i e sw h i c hi sc a l l e df l e x i b l ej o bs c h e d u l i n gp r o b l e m f l e x i b l ej o bs c h e d u l i n gp r o b l e m ( f j s p ) i sa ne x t e n s i o no fc l a s s i c a lj o b s c h e d u l i n gp r o b l e m ( j s p ) a n da l s oap r o b l e mi nf l e x i b l em a n u f a c t u r es y s t e m ( f m s ) i nt h i sp a p e r ，f j s pi sd e c o m p o s e di n t ot w os u bp r o b l e m sw h i c ha r ep r o c e s sp l a n n i n g a n d jo bs c h e d u l i n g ，a n dt w od i f f e r e n tr e p r e s e n t a t i o na r ed e s i g n e df o rt h e s et w os u b p r o b l e m sr e s p e c t i v e l y as y m b i o t i ce v o l u t i o n a r ya l g o r i t h mi sp r o p o s e dt os o l v ef j s p b yp u t t i n gt h et w os u bp r o b l e m st o g e t h e r t os t r e n g t ht h es e a r c ha b i l i t ya n de n h a n c e t h eq u a l i t yo fr e s u l t s ，an e i g h b o u r h o o dm u l t i p a r e n tc r o s s o v e ro p e r a t o r ( n m x ) i s d e v e l o p e da n du t i l i z e di nt h i sp a p e r t h ee x p e r i m e n t a lr e s u l t ss h o wt h ep r o p o s e d s y m b i o t i ce v o l u t i o n a r ya l g o r i t h mc a ns o l v ef j s pw e l l 一 ， i i i 1 1 研究的背景和意义 有限资源的合理配置与优化利用问题一直是人类社会所面临的最基本的经 济学问题，这个问题贯穿于社会生活之中，涉及到了国民经济从宏观到微观的各 个方面，人们对它的研究也就从不同的角度来进行，由此产生了有关这个问题的 不同学科和理论。其中，在生产领域产生了一个非常重要的理论，也就是调度理 论。调度理论源于对制造车间生产计划与控制的研究，经过几十年的研究与探索， 已逐渐发展成为一个比较完整的科学理论，在企业的生产中得到了一定程度的应 用。作业车间调度在所有调度问题中最具典型性，也是生长调度中最复杂，最困 难的问题之一，所以对作业车间调度问题的研究一直在调度理论中占据主导地 位。 对生产过程的作业计划称为作业调度，作业调度问题( j o bs h o ps c h e d u l i n g p r o b l e m ，j s s p ) 是典型的调度问题，也是许多实际问题的简化模型，被证明是 n p h a r d 问题。作业调度问题随着机器数和工件数的增加，调度方案呈指数增长。 传统的j s s p 可以描述为：7 个作业在m 台机器上加工，q ，表示第f 个作业在第 ，台机器上的操作，对应的操作时间为毛，并且事先给定各工件的加工次序称之 一 v 为技术约束条件，要求确定与技术约束条件相容的各机器上所有工件的加工次 序，使d n - r 性能指标达到最优。近年来，随着先进制造技术的发展，j s s p 有所 拓展，增加了随机性、动态性、不确定性、多目标等特点，与生产实际更为接近。 1 2 论文所做的工作以及组织形式 本文在原有的共生算法处理柔性作业调度问题基础上提出了一种改进算法。 针对共生算法的邻域特点和考虑到流程安排染色体需要满足特殊的性质，本文设 计了一种邻域多体交叉算子( n m x ) ，通过将邻域内所有的个体进行交叉产生一个 新的个体，能够充分利用领域的染色体特征，并且能够使得流程安排染色体表示 山东大学硕士学位论文 上的操作排列的操作之间满足作业d a g 给出的拓扑关系。实验证明这种使用 n m x 交叉算子能够显著地改进算法性能。 本文的内容是这样安排的： 第1 章绪论。介绍了作业调度问题的基础知识以及写作本文的背景和意义， 同时明确了后面各章节的安排。 第2 章作业调度介绍。本章主要讨论了作业调度的基础知识，给出了作业 调度问题的分类、特点以及类型。同时还介绍了现实中作业调度问题的扩展，柔 性作业调度问题。最后给出了针对作业调度问题已有的优化方法和国内外对于作 业调度问题的研究现状以及存在的问题。 第3 章遗传算法理论。这章首先简要的介绍了遗传算法，然后阐述了遗传 算法相对于其他一些经典算法的特点，接着简要地介绍了遗传算法的基础理论研 究情况以及遗传算法的改进，并介绍了本文使用到的基于遗传算法的共生算法。 最后简要地给出遗传算法的发展以及研究现状。 第4 章柔性作业调度问题。本章将会给出柔性作业调度完整的问题描述以 及数学模型，同时给出了常见的柔性作业调度指标。 第5 章共生算法求解柔性作业调度问题。本章讨论了一种共生算法来解决 柔性作业调度问题的方案。 第6 章算法改进与实验分析。从交叉算子方面对已有的共生算法进行改进 和优化并且进行了实验，然后从实验结果分析了改进后算法。 第7 章结束语。对本文进行总结，回顾了主要工作，提出了工作中的不足 以及下一步的研究内容和方向。 山东大学硕士学位论文 2 1 作业调度分类特点 第2 章作业调度介绍 作业调度问题是从实际生产中产生的问题，问题来源不同则具有不同的侧 重，生产调度系统的分类方法有很多。g r a v e s 等人按不同的分类标准对车间调度 问题进行了分类【l 】，主要有以下几种： 一( 1 ) 根据加工系统的复杂度可以分为单机调度问题、作业车间( 1 0 bs h o p ) 调度 问题、流水车间( f l o ws h o p ) 调度和多机器并行加工调度。单机调度问题是所有的 操作任务都在一台机器上完成，即任务的优化排队问题；作业车间( j o bs h o p ) 调度 问题是指由m 个不同的机器加工n 个有特定加工路线的作业，不同作业的工序 间没有顺序约束，工序加工不能中断。它不限制作业操作的加工设备，并允许每 个作业加工具有不同的加工路径。作业车间调度是最一般的调度类型，有很多的 研究成果；流水车间( f l o ws h o p ) 调度指所有作业都在相同的设备上加工，并有一 致的加工操作和加工顺序；多机器并行加工调度是指加工系统有一组功能相同的 加工设备，待加工的作业也只有一道工序，可以任选一台加工设备来加工。 ( 2 ) 根据优化准则，可以分为基于调度费用和调度性能两大类。在理论分析 上，大部分只注意调度的性能，但在实际生产中，通常要综合考虑调度费用和性 能两方面因素。 ( 3 ) 根据生产环境的特点，可将调度问题分为确定性调度问题和随机性调度 问题。确定性调度问题是指加工时间和其他参数是己知确定的量，而随机性调度 问题的加工时间和有关参数是随机的变量。 ( 4 ) 根据作业的加工特点，可将调度问题分为静态调度和动态调度。静态调 度是指所有待安排加工的工作均处于待加工状态，因而进行一次调度后，各作业 的加工被确定，在以后的加工过程中就不再改变：动态调度是指作业依次进入待 加工状态，各种作业不断进入系统接受加工，同时完成加工的作业又不断离开， 要考虑作业环境中不断出现的动态扰动：如作业的加工超时、设备的损坏等。因 此动态调度要根据系统中作业、设备等的状况，不断地进行调度。 实际问题中涉及到的作业调度主要有以下几个特点： 山东大学硕士学位论文 ( 1 ) 复杂性：车间中影响作业加工的因素非常多。每个作业要考虑它的加工 时间、安装时间、操作顺序等因素，因而相当复杂。调度问题是在等式或不等式 约束下求指标的优化，一般都是n p h a r d 问题，随着问题规模的增大，其计算量 急剧增加，使得一些常规的方法无能为力，对于这一点已经证明2 1 。 ( 2 ) 随机性：在实际的作业车间调度系统中存在很多随机的和不确定的因素， 环境是不断变化的，在运行过程中会遇到多种随机干扰，比如工件到达时间的不 确定性、作业的加工时间也有一定的随机性，而且生产系统中常出现一些突发偶 然事件，如设备的损坏、修复、作业交货期的改变等，故作业车间调度过程是一 个动态的随机过程。 ( 3 ) 约束性：车间调度问题中资源的数量、缓存的容量、工件加工时间以及 工件的操作顺序等都是约束。此外还有一些人为的因素，如要求各机器上的负荷 要平衡等。 ( 4 ) 多目标性：实际的车间调度问题是多目标的，而且这些目标之间往往是 发生冲突的。调度目标分为三类：基于作业交货期的目标、基于作业完成时间的 目标和基于生产成本的目标。， 2 2 调度类型 经常将调度分为三个等级【3 】：活动调度，半活动调度和非延迟调度。 ( 1 ) 活动调度( a c t i v es c h e d u l e ，a s ) ：如果在不推迟其他操作或破坏优先顺序 的条件下，其中没有一个操作可以提前加工。 ( 2 ) 半活动调度( s e m i a c t i v es c h e d u l e ，s a s ) ：如果在不改变机器上操作的加 工顺序或破坏优先顺序条件下，其中没有操作可以提前。 ( 3 ) 非延迟调度( n o n d e l a ys c h e d u l e s ，n s ) ：如果至少存在一个工件等待加工 时，对应地不存在相应地处于空闲的机器。 其中活动调度是半活动调度的一个子集，非延迟调度是活动调度的一个子 集。最优调度解可能存在非延迟调度中，也可能存在活动调度中。关于之间的收 深入关系和如何来设计作业调度，在本文5 3 节会进行更深入的讨论和分析。 4 山东大学硕士学位 2 3 柔性作业调度问题 传统的作业调度一般假定对每个作业只有一个可行的加工方案，即作业处理 计划中没有弹性，而在现在的制造系统中，出现了各种作业弹性，大多数作业( j o b ) 具有大量的弹性加工方式和工序，即可以选择不同的工序序列来加工此作业，同 时某个工序可能存在由多个机器的组成的可选加工机器集合。作业调度中的柔性 就是处理过程中的可选择性，主要有操作柔性( o p e r a t i o nf l e x i b i l i t y ，o f ) 、顺序柔 性( s e q u e n c ef l e x i b i l i t y ，s f ) 以及处理柔性( p r o c e s sf l e x i b i l i t y ，p f ) 。操作柔性( o f ) 是指同一个操作( 工序) 可以在不同的机器上运行。顺序柔性( s f ) 是指对于一个操 作序列可以在满足拓扑排序的前提下，在处理过程中操作可以选择不同的处理顺 序。关于操作序列的定义和解释在后面会给出。而处理柔性( p f ) 是指要完成某段 加工过程，可以选择不同的操作集及加工顺序的组合。 一般情况下，作业调度问题只含有其中的一个柔性就相当难以处理，而含有 这三种柔性则更加困难【4 1 。在这篇文章中，我们处理的作业调度包含了所有的柔 性，可以看到使用共生算法可以很好的解决这些柔性问题。 2 4 作业调度优化方法 求解调度问题的方法统称为调度优化算法，它可区分为精确求解方法和近似 求解方法。其中精确求解方法包括解析方法、穷举方法、分支定界等；近似求解 方法包括基于规则的构造法、邻域搜索方法等。所谓优化算法，其实就是一种搜 索过程或规则，它是基于某种思想和机制，通过一定的途径或规则得到满足用户 要求的问题的解。调度问题的求解方法通常可粗略分为以下几类： ( 1 ) 解析方法：指对简单小规模调度问题的解析求解方法。 ( 2 ) 枚举方法：对小规模问题比较有效但对大规模问题计算量和存储量难以 承受。如分支定界和整数规划、混合整数规划等一些数学方法。 ( 3 ) 构造性方法：该类方法能够快速建立问题的解，但通常解的质量较差， 否则需要建立复杂的启发式规则。 ( 4 ) 邻域搜索算法：该类方法从若干解出发，对其邻域的不断搜索和当前解 的替换来实现优化。常用的方法有遗传算法，进化策略，模拟退火算法等。 山东大学硕士学位论文 ( 5 ) 人工智能方法：该类方法利用工智能的原理和技术进行搜索，譬如将优 化过程转化为智能系统动态的演化过程，基于系统动态的演化来实现优化，如神 经网络，免疫算法等。 实际运用中可采用以上算法的混合方法来提高求解效率和质量。本文中主要 是使用遗传算法的变种共生算法来求解作业调度问题的。 2 5 国内外研究现状及存在问题 车间作业调度问题是一个传统问题。对它的研究开始于2 0 世纪5 0 年代。早 在1 9 5 4 年，s m j o h n s o n 对两台机床的f l o ws h o p 调度问题进行研究，提出了部 分问题的求解方法，代表着调度理论研究的开始。6 0 至7 0 年代，随着经典调度 理论的建立，人们开始了对算法复杂性的研究，多数调度问题被证明属于n p c 问题或n p h a r d 问题，难以找到多项式算法，因此人们开始关注启发式算法。到 7 0 年代末，经典调度理论趋向成熟。 由于调度问题是制造系统中最基本、最重要的问题之一，是生产管理的核心 i 问题和关键技术，因此国内外大量的学者对其进行了广泛的探讨和研究。随着调 度理论研究的深入及各种交叉学科的发展，又涌现出许多新的车间调度的理论和 方法。如确定性最优化方法【5 1 、基于规则和基于知识的调度方法【6 1 、仿真调度方 法 7 1 、神经网络优化法【8 1 、基于d e d s 的解析模型方法1 9 1 、拉氏松弛法1 0 1 以及基 于模糊数学理论的方法【1 1 】等。近年来，用模拟退火算法( s i m u l a t e da n n e a l i n g ，s a ) 、 禁忌搜索算法( t a b us e a r c h ，t s ) 、人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k s ，a n n ) 、 蚁群算法( a n tc o l o n ya l g o r i t h m ) $ 1 遗传算法( g e n e t i ca l g o r i t h m ，g a ) 等智能方法 解决车间作业调度问题受到人们的高度关注。 由于各种车间作业调度的算法都存在着不同程度的优缺点【1 2 】，所以，近年来， 人们开始将各种算法组合起来进行研究【1 3 1 ，以扬长避短，达到优化调度的目的。 比如：使用将遗传算法和禁忌搜索算法结合起来的混合策略，求解车间调度问题 【1 4 1 。建立基于仿真和遗传算法的集成车间调度优化方法【1 5 】。通过结合启发式算 法和遗传算法的混合方法，求解多资源约束的车间调度问题1 1 6 】。 r 而作为传统作业调度问题的扩展，柔性作业调度问题( f l e x i b l ej o bs h o p p r o b l e m ，f j s p ) 是一个更加接近现实的问题模型，所以也得到了广泛而且深入的 6 山东大学硕士学位论文 研究。b u r k e r 和s c h i l e t l 7 】首次提出f j s p 并且针对一个包含两个作业的f j s p 设计 了多项式时间复杂度的算法，k l a u se ta 1 f l8 】尝试使用概率算法来解决f j s p ，h o 和t a y 1 9 1 提出了文化算法来求解f j s p ，z h a n g 和g e n t 冽将f j s p 分解成为多个部 分并且针对这个性质提出了多级遗传算法，j i ee ta 1 2 1 1 使用遗传算法同时加入瓶 颈移动方法作为局部搜索算法来计算f j s p ，n o u r e d d i n ee ta 1 【捌将f j s p 看作一个 蚁群系统采用蚁群算法并且配合禁忌算法搜索f j s p 的最优解，k i me ta 1 【4 】等人 扩展了f j s p 并且尝试通过共生算法求解这种扩展的f j s p 。 总体上说，经典调度理论仍是调度理论的基石，但智能调度理论已在迅速发 展，并趋于成熟。可以预测，在不久的将来，智能调度理论必将取代传统调度理 论，二者的结合也是一种趋势。 7 山东大学硕士学位论文 第3 章遗传算法理论 本章首先对遗传算法的起源发展做了简单的介绍；然后给出了遗传算法不同 于传统的搜索和优化方法的独特之处：接着给出现有的遗传算法的改进以及本文 所使用的一个遗传算法的变种共生算法；最后介绍了遗传算法的研究现状和发展 趋势。 3 1 遗传算法简介 二十世纪五十年代中期创立了仿生学，许多科学家从生物中寻求新的用于人 造系统的灵感，一些科学家分别独立地从生物进化的机理中发展出适合于现实世 界复杂问题优化的模拟进化算法( s i m u l a t e de v o l u t i o n a r yo p t i m i z a t i o n ，s e o ) ，主要 有h o l l a n d 2 3 , 2 4 ，b r e m e r m a n t 2 5 1 等创立的遗传算法，r e e h e n b e r g t 2 6 1 ；币f ls c h w e f e l t 2 7 】 等创立的进化策略以及f o g e l t 2 引，o w e n s t 2 9 1 ，w a l s h 冽等创立的进化规划，同时 代有一些生物学家f r a s e r ，b a r i c e l l i 等做了生物系统进化的计算机仿真，很遗憾 的是他们没有引入到人工系统。遗传算法、进化策略及进化规划均来源于达尔文 的进化论，其中遗传算法的研究最为深入、持久，应用面也最广。现在遗传算法 已取得了丰硕的应用成果和理论研究的进展，特别是近年来世界范围形成的进化 计算热潮，计算智能已作为人工智能研究的一个重要方向，以及后来的人工生命 研究兴起，使遗传算法受到广泛的关注。那么什么是遗传算法呢? 遗传算法( g e n 商ca l g o r i t h m ，g a ) 是模拟自然界生物进化机制的一种算法， 即遵循适者生存、优胜劣汰的法则，也就是寻优过程中有用的保留，无用的则去 除。在科学和生产实践中表现为，在所有可能的解决方法中找出最符合该问题所 要求的条件的解决方法，即找出一个最优解。h o l l a n d 在1 9 6 0 年提出这种算法的 最初目的是研究自然系统的自适应行为，并设计具有自适应功能的软件系统。它 的特点是对参数进行编码运算，不需要有关体系的任何先验知识，沿多种路线进 行平行搜索，