（系统工程专业论文）基于遗传算法的车间动态粗调度研究.pdf

原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写过的科研成果。对本 文的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。 本声明的法律责任由本人承担。 论文作者签名：缝重量 日期：型竺：笙圣! 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意 学校保留或向国家有关部门或机构送交论文的复印件和电子版，允 许论文被查阅和借阅；本人授权山东大学可以将本学位论文的全部 或部分内容编入有关数据库进行检索，可以采用影印、缩印或其他 复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：艋曼童导师签名：圣逝日期：埋! ：! ：圭 山东大学硕十学何论文 目录 摘要l a b s t r a c t i i i 第一章绪论1 1 1 课题研究背景及意义1 1 2 车间调度2 1 2 1 车间调度问题的描述、分类及特点2 1 2 2 国内外车间调度问题研究现状和存在问题4 1 2 3 车间调度研究方法及策略5 1 2 4 车间调度的发展趋势9 1 3 论文研究的主要内容及结构1 0 第二章基于遗传算法的车间静态调度研究1 1 2 1 遗传算法理论一1 1 2 1 1 遗传算法的生物学背景1 1 2 1 2 遗传算法的基本思想和特点1 3 2 1 3 遗传算法基本操作1 4 2 2 车间调度模型描述17 2 3 车间调度遗传算法的设计一1 9 2 3 1 遗传编码设计1 9 2 3 2 适应度函数2 0 2 3 3 遗传算子的设计2 0 2 3 4 算法终止条件一2 2 2 4 仿真实验2 3 2 5 小结2 6 第三章粗集理论一2 9 3 1 引言2 9 3 2 知识的相关理论一2 9 3 2 1 知识的基本概念一3 0 3 2 2 知识的等价、推广和特化3 1 3 3 粗集的概念及性质3 1 山东大学硕十学何论文 3 3 1 粗集的近似定义3 2 3 3 2 粗集的性质3 4 3 4 粗函数3 5 3 5 小结3 6 第四章基于粗集的车间动态调度3 7 4 1 车间动态调度问题概述3 7 4 1 1 车间动态调度问题描述3 7 4 1 2 动态事件的分类3 8 4 1 3 动态调度策略3 8 4 2 基于遗传算法的车间动态调度3 9 9 9 o 2 2 3 5 6 7 7 7 9 3 5 3 3 4 4 4 4 4 4 4 4 4 4 5 5 一 另 一 一 一 略 别识 目 山东大学硕十学伊论文 c o n t e n t s c h i n e s ea b s t r a c t i a b s t r a c t i l l c h a p t e r1 i n t r o d u c t i o n 1 1 1t h eb a c k g r o u n da n ds i g n i f i c a n c eo ft h er e s e a r c h 1 1 2j o bs h o ps c h e d u l i n g 2 1 2 1d e s c r i p t i o n ，c l a s s i f i c a t i o na n df e a t u r e so fj s p 2 1 2 2r e s e a r c hs t a t u sa n de x i s t i n gp r o b l e ma th o m ea n da b r o a do fj s p 4 1 2 3r e s e a r c hm e t h o d sa n ds t r a t e g i e so fj s p 5 1 2 4d e v e l o p m e n tt e n d e n c yo fj s p 9 1 3m a i nw o r k sa n ds t r u c t u r eo ft h ed i s s e r t a t i o n 10 c h a p t e r2t h es t u d y o ns t a t i cj o bs h o ps c h e d u l i n gb a s e d o ng e n e t i c a l g o r i t h m 1 1 2 1g e n e t i ca l g o r i t h mt h e o r y 1 1 2 1 1t h eb i o l o g i c a lb a c k g r o u n do fg e n e t i ca l g o r i t h m 11 2 1 2t h eb a s i ci d e aa n df e a t u r e so fg e n e t i ca l g o r i t h m 13 2 1 3b a s i co p e r a t i o n so fg e n e t i ca l g o r i t h m 1 4 2 2t h ed e s c r i p t i o no ft h es h o ps c h e d u l i n gm o d e l 二17 2 3g e n e t i ca l g o r i t h mf o rj o bs h o ps c h e d u l i n g 19 2 3 1t h ed e s i g no fg e n e t i cc o d i n g 19 2 3 2f i t n e s sf u n c t i o n 2 0 2 3 3t h ed e s i g no fg e n e t i co p e r a t o r s 2 0 2 3 4a l g o r i t h mt e r m i n a t i o nc o n d i t i o n s 2 2 2 4s i m u l a t i o ne x p e r i m e n t s 2 3 2 5s u m m a r y 2 6 c h a p t e r3r o u g hs e tt h e o r y 2 9 3 1i n t r o d u c t i o n 2 9 3 2t h et h e o r yo fk n o w l e d g e 2 9 3 2 1t h eb a s i cc o n c e p to fk n o w l e d g e 3 0 3 2 2t h ee q u i v a l e n c e ，p r o m o t i o na n ds p e c i a l i z a t i o no fk n o w l e d g e 3 1 i j j 东大学硕十学侍论文 3 3t h ec o n c e p ta n dp r o p e r t i e so f t h er o u g hs e t 3 1 3 3 1a p p r o x i m a t i o nt ot h ed e f i n i t i o no fr o u g hs e t 3 2 ：；3 2p r o p e r t i e so ft h er o u g hs e t 3 4 ：；4r o u g hf u n c t i o n 3 5 ：；5s u m m a r y 3 6 c h a p t e r4 t h ed y n a m i c j o bs h o ps c h e d u l i n gb a s e do nr o u g hs e t 3 7 4 1o v e r v i e wo ft h ed y n a m i cj o bs h o ps c h e d u l i n gp r o b l e m 3 7 4 1 1d e s c r i p t i o no fd y n a m i cj o bs h o ps c h e d u l i n gp r o b l e m 3 7 4 1 2c l a s s i f i c a t i o no f d y n a m i ce v e n t s 3 8 山东大学硕十学伊论文 摘要 作业车间调度是制造系统生产过程中的个重要组成部分。合理的调 度方法与优化技术的研究和应用对提高企业的生产效率、减少生产损耗、 增强资源优化配置能力有着重要的作用。因此车间调度问题越来越受到学 者们的关注。本文对遗传算法进行了研究和改进，并将改进后的遗传算法 应用于作业车间静态调度问题的求解，获得满意的结果；研究了基于事件 驱动和基于周期性与事件驱动的作业车间动态调度策略，结合粗集理论的 分类特性和上下近似特性，进一步研究了作业车间的动态调度策略。 首先，本文介绍了作业车间调度的研究背景和意义，分析了国内外对 车间调度问题进行研究的方法与存在的问题，探讨了车间调度的发展趋势。 其次，阐述了遗传算法的基本概念、原理和基本操作，对作业车间调 度问题进行了数学描述，建立了一般的车间静态调度模型，针对遗传算子 进行了改进，对编码解码、初始种群的产生、适应值函数等进行了设计， 并使用改进后的遗传算法实现了车间静态调度，仿真结果表明了改进算法 的有效性和正确性。 再次，研究了作业车间的动态调度问题，并使用改进的遗传算法分别 对基于事件驱动和基于周期性驱动与事件驱动混合的再调度问题进行建模 与仿真。实验结果表明该算法能大大减小调度问题的求解规模，获得满意 的调度结果。 最后，研究了粗集理论在车间动态调度建模中的应用。根据粗集的分 类特性和上下近似特性，提出了基于粗集的车间动态粗调度窗口工件识别 方法，建立了车间动态粗调度模型，并利用改进的遗传算法对该模型进行 仿真验证。仿真结果表明，基于遗传算法的动态粗调度算法不仅能适应动 态的加工环境，获得满意的调度结果，还能有效地减少再调度次数，提高 整个动态调度系统的稳定性。 关键词：车间调度；遗传算法；动态调度；粗集。 山东大学硕十学何论文 a b s t r a c t i nt h ep r o c e s so fm a n u f a c t u r i n gs y s t e mp r o d u c i n g ，j o bs h o ps c h e d u l i n gi s a ni m p o r t a n tp a r t t h es t u d ya n da p p l i c a t i o no fr e a s o n a b l es c h e d u l i n ga n d o p t i m i z a t i o nt e c h n o l o g yp l a y si m p o r t a n t r o l ei n i m p r o v i n gp r o d u c t i o n e f f i c i e n c y ，r e d u c i n gp r o d u c t i o nl o s s e s ，i n c r e a s i n g t h e a b i l i t yt oo p t i m i z e r e s o u r c e s ，t h a t sw h yj o bs h o ps c h e d u l i n gi sp a i dm o r ea n dm o r ea t t e n t i o nb y r e s e a r c h e r s t h i st h e s i sf o c u s e so nt h es t u d ya n di m p r o v e m e n to fg e n e t i c a l g o r i t h m ，a n da c h i e v e sg o o dr e s u l t sw h e na p p l yt h ei m p r o v e da l g o r i t h mt ot h e s t a t i cj o bs h o ps c h e d u l i n g m e a n w h i l e ，t h i st h e s i ss t u d i e st h ed y n a m i cj o b s h o ps c h e d u l i n gb a s eo ne v e n t d r i v e n ，p e r i o d i ca n de v e n t - d r i v e n a tl a s t ，t h i s t h e s i sf u r t h e rs t u d i e st h ed y n a m i cj o bs c h e d u l i n gu s i n gt h ec l a s s i f i c a t i o n f e a t u r e sa n dc h a r a c t e r i s t i c so fu p p e ra n dl o w e ra p p r o x i m a t i o no fr o u g hs e t t h e o r y f i r s t l y ，t h es t u d yb a c k g r o u n da n ds i g n i f i c a t i o n sa r ei n t r o d u c e d m e t h o d s a n dp r o b l e m so nj o bs h o ps c h e d u l i n go fb o t hn m i o n a la n di n t e r n a t i o n a la r e a n a l y z e d ，a n dt h et r e n d so f j o bs h o ps c h e d u l i n gi sd i s c u s s e di nd e t a i l s e c o n d l y ，t h eb a s i ci d e a s ，p r i n c i p l e sa n do p e r a t i o n sa r ee x p l a i n e d w e d e s c r i b et h ejo bs h o ps c h e d u l i n gi nm a t h e m a t i c sa n db u i l dt h eg e n e r a lm o d e l f o rs t a t i cj o bs h o ps c h e d u l i n g ；a l s o ，w ei m p r o v et h eg e n e t i ca l g o r i t h m ，d e s i g n m e t h o d so fe n c o d i n g ，d e c o d i n g ，g e n e r a t i o no fi n i t i a lf a r m ，a n dt h ef i t n e s s f u n c t i o n ，a n da p p l yt h ei m p r o v e dg e n e t i ca l g o r i t h m t os t a t i cj o bs h o p s c h e d u l i n g t h es i m u l a t i o nr e s u l t sv a l i d a t et h ev a l i d i t ya n dc o r r e c t n e s so f t h e i m p r o v e da lg o r i t h m t h i r d l y , t h ed y n a m i cjo bs h o ps c h e d u l i n gi ss t u d i e d w eb u i l dt h em o d e l o fr e s c h e d u l i n gp r o b l e mb a s e do ne v e n t - d r i v e n ，a n db a s e do np e r i o da n d e v e n t d r i v e nu s i n gi m p r o v e dg e n e t i ca l g o r i t h mr e s p e c t i v e l y s i m u l a t i o n sa r e c a r r i e do u tf o rt h e s ep r o b l e m sa n dr e s u l t ss h o wt h a tt h ei m p r o v e da l g o r i t h m c a na p p a r e n t l yr e d u c et h ed i f f i c u l t yo fs c h e d u l i n g ，a n da c h i e v er e a s o n a b l e r e s u l t s i i i i j j 东大学硕十学何论文 l a s t ，t h ea p p l i c a t i o no fr o u g hs e tt h e o r yi nd y n a m i cj o bs h o ps c h e d u l i n g i s s t u d i e d a c c o r d i n g t oc l a s s i f i c a t i o nf e a t u r ea n d u p p e r a n d l o w e r a p p r o x i m a t i o nc h a r a c t e r i s t i c so fr o u g hs e tt h e o r y , w ep r o m o t et h ew o r k p i e c e i d e n t i f i c a t i o nm e t h o do fd y n a m i cj o bs h o ps c h e d u l i n g ，b u i l dt h ed y n a m i cj o b s h o ps c h e d u l i n gm o d e l ，t h ev a l i d a t et h ev a l i d i t y o ft h ei m p r o v e dg e n e t i c a l g o r i t h mv i as i m u l a t i o n t h es i m u l a t i o nr e s u l t ss h o wt h ed y n a m i cr o u g h s c h e d u l i n gm e t h o db a s e do ng e n e t i ca l g o r i t h mc a nn o to n l ya d a p td y n a m i c m a n u f a c t u r i n g ，a n da c h i e v er e a s o n a b l er e s u l t s ，b u ta l s oc a nr e d u c et h et i m e so f r e - s c h e d u l i n g ，a n di m p r o v et h es t a b i l i t y o ft h ew h o l ed y n a m i cjo b s h o p s h o p s c h e d u l i n g ； g e n e t i c a l g o r i t h m ；d y n a m i c 山东大学硕十学伊论文 1 1 课题研究背景及意义 第一章绪论 随着世界经济的全球化、一体化以及信息科学技术日新月异的发展， 市场竞争愈演愈烈，现代企业面临着复杂多变的市场环境。为了适应激烈 的市场竞争，保证生产的高效稳定运行，企业必须能够具有动态地调整其 生产策略和模式的能力。因此原来的一元化、单品种、大批量、流水线式 的大批量制造的生产方式，逐渐向多元化、多品种、小批量、高柔性、相 对复杂的敏捷制造的生产方式转变。敏捷制造是2 1 世纪企业的先进制造模 式，它综合了j i t ( j u s ti nt i m e ，准时生产) 、并行工程、精益生产等多种 先进制造模式的哲理，其目的是要以最低成本制造出顾客满意的产品，是 完全面向顾客的。在这种模式下如何进行组织管理，包括如何组织动态联 盟、如何重构车间和单元、如何安排生产计划、如何进行调度都是面临的 主要问题。其中作业车间调度与控制技术是实现生产高效率、高柔性和高 可靠性的关键，有关资料表明，制造过程中9 5 的消耗在非切削过程中o l o 因此，有效的调度方法与优化技术的研究和应用，是实现先进制造和提高 生产效率的基础和关键。对降低生产成本、提高企业市场竞争力有着重要 的作用。 生产调度就是在一定时间内，进行可用共享资源的分配和加工任务的 排序，以满足某个或某些特点的生产指标【2 l ，是整个先进生产制造系统实 现管理技术、运筹技术、优化技术、自动化与计算机技术发展的核心。车 间生产调度主要针对一项可分解的工作( 如产品制造) ，探讨在尽可能满足 约束条件( 如交货期、工艺路线、资源情况) 的前提下，通过下达生产指令， 安排其组成部分( 操作) 使用哪些资源、其加工时间及加工的先后顺序，以 获得产品制造时间或成本的最优化【3 j 。车间生产调度直接影响生产成本和 资源的合理利用，决定着生产过程能否顺利进行，生产资源能否合理配置 和优化。在过去的几十年里，基于实际的要求和理论上的考虑，人们不断 地寻找新的调度策略和优化算法，以提高资源的生产率和操作管理的相对 水平，生产出具有竞争力的产品。 山东大学硕十学位论文 目前，国内的大部分企业主要依靠传统的数学模型或是调度人员的经 验来安排调度计划，这在调度问题比较简单的情况下还是可行的，然而， 当调度规模较大且动态多变时，单纯的手工调度就显得低效甚至无能为力 了。况且，对于企业来说，经验丰富的工人本身就是一种稀缺资源。因此， 研究车间调度算法，建立一个运行高效、使用简单的车间调度系统，对于 促进车间生产管理的发展和企业生产资源的合理配置、提高企业在市场中 的竞争力具有重要的意义。 分 达 题 排 能 类 o p 务 工 的 往 调 山东大学硕十学位论文 度问题。 ( 5 ) 根据作业的加工特点，可将调度问题分为静态调度和动态调度。 静态调度是指所有待安排加工的作业均处于待加工状态，且工件的信 息和车间状态都是明确的，因此进行一次调度后，所有作业的加工时间被 确定下来，而且在以后的加工过程中就不需要再改变。动态调度是指作业 依次进入待加工状态，各种作业连续不断进入系统接受加工，同时完成加 工的作业又不断离开。此外，还要考虑实际加工环境中不断出现的动态扰 动：如工件的报废、机器的故障、订单的取消、急件订单的到来等。因此 动态调度要根据系统中作业、设备等的状况，不断地进行调度。 ( 6 ) 根据调度是否有序，可分为有序加工和无序加工。 在实际的作业环境中，现代车间调度的类型往往是j o bs h o p 型，而且 是动态的。实际的车间调度问题有以下特点： ( 1 ) 复杂性 橐 由于生产车间中工件、机器、缓存和搬运系统之间相互影响、相互作 用，并且每个工件又要考虑它的加工时间、安装时间、操作顺序和交货期 等，使调度相当复杂。调度问题是在等式或不等式约束下求性能指标的优 化，在计算量上往往是n p 完全问题，随着问题规模的增大，对于求解最 优化的计算量呈指数增长，使得一些常规的最优化方法往往无能为力。” ( 2 ) 随机性 在实际的生产调度系统中存在很多随机的或不确定的因素，如作业到 达时间的不确定性、实际工件的加工时间也有一定的随机性，以及生产系 统中常出现的一些突发事件，如设备的损坏、修复、作业交货期的改变、 急加工工件到来等。 ( 3 ) 多目标性 实际工件调度往往是多目标的，而且这些目标间可能发生冲突。k i r a n 等人将调度目标分三类：基于作业交货期的目标、基于作业完成时间的目 标、基于生产成本的目标【5 1 。这种多目标性导致调度的复杂性的提高和计 算量急剧增加。 ( 4 ) 多约束性 生产车间中资源的数量、缓存的容量、工件加工时间和工件操作顺序 山东大学硕十学何论文 等都是约束。此外还有一些人为的约束，如要求各机器上的负荷平衡等。 1 2 2 国内外车间调度问题研究现状和存在问题 2 0 世纪5 0 年代初期，应用数学、运筹学、工程技术等领域的学者开 始对制造过程中的调度问题进行大量研究。在研究的初期阶段，调度问题 是作为一个纯粹的数学问题加以研究的。l9 5 4 年，j o h n s o n 研究了两台机 器有序加工型的调度问题，提出了解决n 2 c m a x ( n 个工件2 台机器的f l o w s h o p 型调度的最小流程周期问题) 和部分特殊的n 3 f c m a x 问题有效的 j o h n s o n 规则1 6 】，从此开始了对调度问题的研究。 六十年代，建立了调度理论的主体，并重视调度复杂性的研究。人们 多利用混合或纯整数规划、动态规划和分枝定界法解决一些有代表性的问 题，如s t o r y 的研究【7 】。同时也有人开始尝试用启发式算法研究此问题，如 g a v c t t 提出的方法【8 1 。六十年代末期，经典调度理论体系初步形成。一 从七十年代开始，随着复杂性理论( c o m p l e x i t yt h e o r y ) 以及n p 完 全问题( n p c o m p l e t e ) 研究的兴起，人们开始注意并重视调度问题的复杂 性研究，证明了许多调度问题是n p 难的( n p h a r d ) ，即使简单的j o b s h o p 和f l o w s h o p 问题也是n p 的，不存在有效的多项式求解方法，因此只好 寻找有效的启发式方法来解决它们。p a n w a l k a r 总结和归纳出了1 1 3 条调度 规则，并对其进行了分类1 9 】。七十年代末期，经典调度理论趋向成熟。 八十年代初期，调度研究转向应用研究阶段。以f o xms 发表的文章 为标志，开始了人工智能方法( a i ) 在j s p 调度问题中的研究应用【1 0 】。八十 年代后期，g i f f i e r 等人【l l 】总结了生产调度的理论和实践方面的最新研究进 展，从七个方面论述了生产调度的技术和方法，认为生产调度无论在理论 还是实践上都已突破了传统晃限。 国内对车间调度的研究起步较晚，“八五”期间一些高校和研究机构如 清华大学、上海交通大学、西安交通大学和北京机械工业自动化研究所等 研究单位对此进行了理论研究，并开发出了相应的计算机辅助生产调度与 管理系统，使车间高度问题逐步从理论研究阶段走向应用阶段。 调度领域中的问题大多属于n p h a r d 问题，因此寻找具有多项式复杂 性的最优算法几乎是不可能的。各种近似启发式方法、诸如基于规则的算 4 山东大学硕十学伊论文 法等，由于能在合理的时间内产生比较满意的调度，因此广泛应用于实际 调度中，但其往往对所得的调度解的次优性不能进行评估。而且实际的生 产系统是一个动态生产环境，存在着很多不确定性的变化。所以，实际的 调度应该是动态调度，只用静态调度的理论解决问题不会达到最好的效果。 1 2 3 车间调度研究方法及策略 目前，车间调度问题的优化算法有很多种，它可区分为精确求解方法 和近似求解方法，具体如下图1 1 所示。 图1 - 1 车间调度问题算法分类 具体分类如下： 1 ) 解析法 该类算法针对简单小规模调度问题的解析求解，如m o o r e 算法、 j o h n s o n 算法。但这类算法只适用于一些特殊类型的单机调度问题和双机 f l o w s h o p 调度问题【1 2 1 。 山东大学硕十学何论文 2 ) 枚举法 该类算法对小规模问题比较有效，但对大规模问题计算量和存储难以 承受。其中应用最多的是分枝定界法( b y r a n c ha n db y o u n d ) 和数学方法 ( m a t h e m a t i c a lm e t h o d ) 。 ( 1 ) 分枝定界法 基本思想是先求出对调度整数规划模型所对应的线性规划问题的最优 解，如果解不能满足调度问题的整数条件，则对应的线性规划问题的最优 解必是调度问题的目标函数值的上界，而调度问题的任意可行解的目标函 数值则是其最优解的下界，然后将对应的线性规划问题的可行域分成子域， 通过不断减少上界和增大下界，最终寻找到最优解【1 3 1 。分枝定界法只适合 于小规模调度问题，并对实际问题比较敏感，因此限制了它在调度问题上 的应用。 ( 2 ) 数学方法 数学规划法在车间调度中被广泛采用。调度问题可以用整数规划法 【14 1 、混合整数规划法【1 5 1 和动态规划法来描述。其优点是任务分配和排 序的全局性比较好，所有选择同时进行，能保证求解问题的全局优化。但 是，实际生产中有很多不确定因素，使建模不明确，且求解空间太大，计 算困难。另外，数学规划法是一种精确求解方法，需要对调度问题进行统 一的建模，因此，对于复杂多变的车间调度来说，单一的数学规划模型不 能覆盖所有因素。 3 ) 构造性方法 该类方法可以快速建立问题的解，但解的质量通常比较差，但对于实 际生产系统中复杂的、大规模的车间调度问题来说具有很大的优越性，如 优先分配规则( p r i o r i t yd i s p a t c hr u l e ) 和启发式方法。 ( 1 ) 优先分配规则 优先分配规则即计算工件的优先权，按优先权来分配。n i l s s o n 根据加 工时间和到期时间的线性组合来决定工件的优先权，并通过仿真用改进的 h o o k e j e e v e s 搜索法来求优先规则【17 1 。 ( 2 ) 启发式方法 从实用的角度看，启发式方法因其易于实现、计算复杂度低等优点， 6 山东大学硕十学位论文 在实际中得到了比较广泛的应用【1 8 】，并且不断涌现出许多的新的调度规 则，常见的启发式有：优先分配启发式，随机移动启发式，随机分配启发 式，瓶颈移动启发式等。虽然启发式规则常被用于实际当中，但它们一般 不具有全局优化的特点【1 9 珊】。 4 ) 邻域搜索方法 邻域搜索方法应用非常普遍，该方法从若干解出发，对其邻域的不断 搜索和当前解的替换来实现优化。在概念上与爬山法类似，这种技术不断 的刺探和评价调度，直到目标方程的值没有任何进展。在这一类技术当中， 应用最为普遍的是禁忌搜索( t a b us e a r c h ) 、模拟退火( s i m u l a t e da n n e a l i n g ) 和遗传算法( g e n e t i ca l g o r i t h m s ) 。 ( 1 ) 禁忌搜索 禁忌搜索是由g l o v e r 提出的用于获取组合最优化难题近似解的一种 高级启发式方法【2 。该方法可以从一个可行解开始逐步搜索移向一个最优 或次优解。在每次移动前，根据某种与问题有关的规则确定在现行解周围 的相邻解集，然后评估每一个相邻解，并移动到该相邻解集中的一个最优 解。有些移动是禁忌的( 禁止的) ，因为它们会陷入局部最优或导致循环。 这些禁忌的移动被加入禁忌表，一般地，禁忌表的长度越长，则搜索陷入 局部最优的可能性越小。但是，长禁忌表需要更多的计算扫描时间，并且 在每次迭代中限制了搜索空间。最合适的长度与问题有关，但到目前为止 还没有确定长度的规则可循。 禁忌搜索已经成功的应用在调度问题和混合整数规划问题中。 t a i l a r d t 2 2 】提出了解决流水车间调度问题的禁忌搜索算法。m a n u e l 2 3 1 为了更 有效地搜索解空间，引入了插入移动和移动相结合的机制，提高了搜索效 率。但由于禁忌搜索应用时需要较多技巧，故在车间调度中应用较少。 ( 2 ) 模拟退火 模拟退火模仿金属中结晶体结晶和冷却的物理过程。在车间调度问题 中，当前的调度结果类似热动能系统中的当前状态，目标方程类似热动能 系统中的能量方程，全局最优解类似基态。 模拟退火也能有效地解决车间的调度问题。j e f f c o a t 和b u l f i n l 2 4 】应用模 拟退火法解决资源受制约的调度问题。他们的计算结果表明与其他邻域搜 7 山东大学硕十学何论文 索技术相比模拟退火能获得更好的解。但它的收敛速度慢，很难用于实时 动态调度环境。 ( 3 ) 遗传算法 遗传算法是一种模仿生物群体进化过程的一种优化调度算法。它是一 种崭新的并行优化搜索方法。给定一组初始解作为一个群体，通过选择、 交叉和变异等遗传操作来搜索最优解。 遗传算法的优越性主要表现在：搜索过程中不易陷入局部最优，能以 极大的概率找到全局最优解，且具有并行性，非常适合于大规模并行分布 处理，易于与别的技术( 如神经网络、启发式规则等) 相结合，形成性能 更优的算法【2 5 1 。但遗传算法的搜索效率低、易过早收敛。 l l j 东入学硕十学佗论文 和启发式信息等；推理机制用来选择一种策略处理知识库中的知识，以便 随时解决问题。 i s i s t l 0 】是最早提出针对车间调度的专家系统之一。i s i s 采用了面向约 束推理的方法，把约束分成三种类型：组织目标约束、物理限制约束和临 时约束。利用这些约束知识可以维护调度的一致性，同时还能验证最低限 度满足约束的调度决策。s o n i a l 2 7 1 是一个包含预测和反应调度组件的单件 车间调度系统，反应组件用于解决由于各种原因产生的调度效果与预期效 果间的偏差，系统考虑的意外事件有操作延误、容量冲突和机器故障。 ( 3 ) 蚁群算法 蚁群算法( 又称蚂蚁算法) 是一种用来在图中寻找优化路径的几率型 技术，具有较强的鲁棒性、分布式计算、易于与其他方法结合的优点f 2 引。 蚁群算法已经在若干领域取得成功的应用，其中最成功的应该是在组合优 化问题中的应用。但蚁群算法在求解连续优化问题方面的优越性比较弱， 且是一种新型的模拟进化算法，许多问题有待进一步研究。 1 2 4 车间调度的发展趋势 由于车间调度问题的复杂性，各种不同的具体问题往往有很多不同的 解决方法，目前车间调度问题的研究形成了下列研究趋势。 ( 1 ) 并行或分布策略适合不同车间控制结构与高度问题复杂性的实际 需要，不少学者提出并行或分布策略来解决调度问题1 2 弘3 0 j 。 ( 2 ) 分解与成组策略利用分解和成组调度策略可以大大降低问题的计 算复杂性和规模，求得调度问题的较优解，同时优化系统的一些性能指标。 ( 3 ) 人机交互策略调度问题的性质、现有研究方法的缺陷以及人类独 特的思维能力决定了人机交互策略的生命力，大量的研究成果表明在目前 知识条件下人机交互策略是解决困难问题的一条有效途径。 ( 4 ) 动态重调度策略车间制造过程的随时性、不确定性需要不断地进 行重调度，以处理突发的事件。基于目前的研究，对于动态调度的具体策 略有周期调度、连续调度、事件驱动调度、周期与事件驱动混合调度、周 期与连续调度混合的策略等。 ( 5 ) 多目标权衡决策实际调度问题往往是多目标的，如最短生产期、 9 山东大学硕十学付论文 最大生产利润，而且这些目标往往相互冲突【3 1 1 。如何对调度系统的不同目 标进行权衡分析，实现多目标调度是车间调度问题的一个值得研究的方向。 1 3 论文研究的主要内容及结构 根据课题的国内外研究现状和存在的问题，本文在现有的车间调度遗 传算法研究的基础上，结合粗集理论的分类特性，研究车间的动态调度问 题。研究内容主要包括：( 1 ) 针对遗传算法在车间调度中的应用，通过分析 山东大学硕十学伊论文 第二章基于遗传算法的车间静态调度研究 2 1 遗传算法理论 遗传算法( g e n e t i ca l g o r i t h m s ，简称g a ) 【32 】是一种借鉴生物界自然 选择和自然遗传机制的高度并行、随机、自适应搜索算法。它模仿自然界 生物进化过程中“物竞天择，适者生存”的原理来进行优化，是一种多参 数、多群体的优化方法。由美国m i c h i g a n 大学的j o h n h o l l a n d 教授于1 9 7 5 年首先在自然与人工系统中的适应性行为( a d a p t a t i o ni nn a t u r a la n d a r t i f i c i a ls y s t e m s ) 书中提出。其主要特点是群体搜索策略和群体中个体 之间的信息交换，且搜索不依赖于梯度信息。自2 0 世纪8 0 年代以来，遗 传算法的理论与应用研究都成了热门的课题，尤其是应用研究显得十分活 跃。目前，它已被广泛应用于组合优化、机器学习、规划设计、自适应控 4 制和生产调度等领域。 “ 2 1 1 遗传算法的生物学背景 自从达尔文的进化论得到人们的接受之后，生物学家们就对进化机制 产生了极大的兴趣。按照达尔文的进化论，地球上的每一物种从诞生开始 就进入了漫长的进化历程。生物种群从低级、简单的类型逐渐发展成为高 级、复杂的类型，最终进化到人类这样有思维、有智力的高级生命体。这 一过程是一个自然的、并行发生的、稳健的优化过程，其目标是对环境的 自适应性。 我们了解一下生物学中进化与遗传的概念【3 3 1 。 ( 1 ) 生物的进化 地球上的生物，都是经过长期进化而形成的。根据达尔文的自然选择 学说，地球上的生物具有很强的繁殖能力。在繁殖过程中，大多数生物通 过遗传使物种保持相似的后代；部分生物由于变异，后代具有明显差别， 甚至形成新物种。正是由于生物不断繁殖后代，生物数目大量增加，而自 然界中生物赖以生存的资源却是有限的，因此，为了生存，生物就需要竞 争。生物在生存竞争中，根据对环境的适应能力，适者生存、不适者消亡， 山东大学硕十学何论文 自然界中的生物，就是根据这种优劣的原则，不断地进行进化。遗传算法 就是借用生物进化的规律，通过繁殖一竞争一再繁殖一再竞争，实现优胜 劣汰，一步一步地逼近问题的最优解。 ( 2 ) 遗传物质 众所周知，细胞是生物结构和功能的基本单位，细胞通常由细胞膜、 细胞质与细胞核三部分组成。细胞核位于细胞的最内层，由核膜、染色质、 核液三者组成，是遗传物质储存和复制的场所。细胞核中的染色质，在细 胞分裂时形成光学显微镜可以看到的染色体。染色体主要由蛋白质和d n