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

山东大学硕士学位论文 摘要 本文研究了遗传算法的改进问题，将改进后的遗传算法应用于车间调度问 题的求解，获得了满意的结果；研究了粗集理论( m u g l ls e 协) 在生产车间动态调 度中的应用，在生产车间动态加工环境下，当有影响加工过程的实时事件发生 时，必须对实时事件进行处理，静态调度不能适应动态加工环境的变化，本论 文基于粗集理论，与调度专家经验相结合，研究了动态调度窗口中调度工件的 识别和调度问题，提出了相应的车间动态调度窗口工件识别方法，建立了基于 粗集理论的车间动态调度模型，并基于改进后的遗传算法求解所建立的动态调 度模型。仿真结果验证：与传统动态调度方法相比较，该方法不仅能够减少再 调度次数和提高动态调度的稳定性，而且能获得满意的调度结果。 本文的主要工作和创新点如下： 1 、阐述了车间调度的概念和意义，建立了一般的车间静态和动态调度模型。 改进了遗传算法，使用改进后的遗传算法求解了调度模型，仿真实验结果表明 了改进算法的有效性。 2 、研究了粗集理论在车间动态调度建模中的应用基于粗集的分类特性、 条件属性、决策表和近似特性，提出了基于粗集的车间动态粗调度窗口工件识 别方法，提出了基于粗集理论的工件决策表约简规则，建立了车间动态粗调度 模型。通过仿真实验，验证了所提动态调度模型的正确性和有效性。与传统动 态调度方法相比，该方法减少了动态再调度的次数，均衡了设备的利用率，而 且能够获得满意的调度结果。 3 、研究了函数s 粗集在车间动态调度中的应用，与s 粗集的应用进行比 较，指出了s 粗集在应用中的不足，证明了应用函数s 粗集理论的正确性，这 是本论文的最大创新点。 最后，总结了本文的主要工作，指出了进一步的研究方向。 关键词：遗传算法；动态调度；滚动调度，粗集：函数s 粗集 本文的研究工作得到山东省自然科学基金资助( y r 2 0 0 4 g 0 5 ) 。 山东大学硕士学位论文 a b s t r a c t t h i sd i s s e r t a t i o n s t u d i e st h ei m p r o v e m e n tp r o b l e mo ft h eg e n e t i c a l g o r i t h m ，a p p l i e st h ei m p r o v e dg e n e t i ca l g o r i t h mt o g o l v ej o bs h o p 8 c h e d u l i n gp r o b l e m ，a n da c q u i r e sas a t i s f i e dr e s u l tf i n a l l y ；i ts t u d i e st h e a p p l i c a t i o no fr o u g hs e t st h e o r ya n df h n c t i o n8 一r o u g hs e t s ( s i n g u i a rr o u g h s e t s ) t h e o r yi nj o bs h o pd y n a m i c8 c h e d u l i n g u n d e rd y n a m i cp r o c e s s i n g e n v i r o n m e n t ，w h e ns o m er e a la f f a i r so c c u r w es h o u l dr e - s c h e d u l et h ej o b i nt h er o l l i n gw i n d o w ，a ss t a t i c s c h e d u l i n g c a n t a d a p tad y n a m i c p r o c e s s i n ge n v i r o n m e n tw e l l w es t u d yt h ej o bi d e n t i f i c a t i o na n dj o b s c h e d u l i n gp r o b l e m si n t h er o l l i n gw i n d o wu n d e rd y n a m i cp r o c e s s i n g e n v i r o n m e n t t h ec o r r e s p o n d i n gj o bi d e n t i f i c a t i o nm e t h o d so ft h ej o b s h o pd y n a m i cs c h e d u l i n gw i n d o wb a s e do nr o u g hs e t st h e o r ya n da r e e x p e r te x p e r i e n c ep r e s e n t e d w e e s t a b l i s ht h e j o bs h o pd y n a m i c s c h e d u l i n gm o d e l i n gb a s e do nt h e s et h e o r i e s ，a n dr e s o l v et h e s em o d e l s u s i n gt h ei m p r o v e dg e n e t i ca l g o r i t h m t h es i m u l a t i o nr e s u l t sd e m o n s t r a t e t h en e wm e t h o d sh a v ec e r t a i nm e r i t si nd e c r e a s et h er e s c h e d u l i n gd e g r e e a n di m p r o v et h es y s t e ms t a b i l i t yc o m p a r e dw i t ht h et r a d i t i o n a ld y n a m i c s c h e d u l i n gm e t h o d s t h em a i ns t u d yw o r k so ft h i sd i s s e r t a t i o na r ea sf o l l o w s 1 f i r s t l y ， w ep r e s e n tt h ec o n c e p ta n ds i g n i f i c a n c eo fj o bs h o p s c h e d u l i n g ， a n de s t a b l i s ht h e g e n e r a ij o bs h o p8 t a t i c a n dd y n a m i c s c h e d u l i n gm o d e i s i m p r o v et h eg e n e t i ca l g o r i t h mt os o l v et h em o d e l s t h es i m u l a t i o nr e s u l t ss h o wt h ea v a 订a b i l i t yo ft h ei m p r o v e da l g o r i t h m 2 s e c o n d l y ，t h ej o bs h o pd y n a m i cs c h e d u l i n gm o d e l i n gb a s e do n r o u g hs e t st h e o r yi ss t u d i e d b a s e do nt h ea p p r o x i m a t ec h a r a c t e r i s t i co f r o u g hs e t s ，aj o bi d e n t i f i c a t i o nm e t h o do ft h ej o bs h o pd y n a m i cr o u g h s c h e d u l i n gw i n d o wi sp r e s e n t e d ，ad e c i s i o nt a b l ei si n v i t e da n dt h ej o b s h o pd y n a m i cr o u g hs c h e d u l i n gm o d e lb a s e do nr o u g hs e t si se s t a b l i s h e d i i 山东大学硕士学位论文 t h es i m u l a t i o nr c s u l t sd e m o n s t r a t et h ea d v a n t a g eo ft h ep r o p o s e d m e t h o d sc o m p a r e dw i t ht h et r a d i t i o n a ld y n a m i cs c h e d u l i n gm e t h o d s t h r o u g ht h eu s eo ft h i sd y n a m i cs c h e d u l i n ga l g o r i t h m ，f i r s t l yt h ed y n a m i c p r o c e s s i n ge n v i r o n m e n ti sa d a p t e da n das a t i s f i e ds c h e d u l i n gr e s u l t i 8 o b t a i n e d ，s e c o n d i y ，t h ep r o b l e md i m e n s i o n i sr e d u c e da n dt h eu t i l i t yr a t i o o ft h e e q u i p m e n t i sa d v a n c e d ，f i n a l l yt h er e s c h e d u l i n g d e g r e ei s d e c r e a s e da n dt h es y s t e ms t a b i l i t yi si m p r o v e d 3 t h i r d l y w es t u d yt h ea p p l i c a t i o no ff u n c t i o ns r o u g hs e t st h e o r y i nt h ej o bs h o pd y n a m i cr o u g hs c h e d u l i n gc o m p a r e dw i t ht h eu s i n go f s r o u g hs e t s p o i n to u tt h es h o r t a g eo fs r o u g hs e t s ，p r o v et h ea c c u r a c yo f t h ea p p l i c a t i o no ff u n c t i o ns r o u g hs e t s ；t h i si 8t h eb i g g e s ti n n o v a t i o n p o i n ti nt h i sd i s s e r t a t i o n f i n a l l y t h em a i nw o r k so ft h i sd i s s e r t a t i o na r es u m m a r i z e d ，a n dt h e f h r t h e rs t u d yd i r e c t i o n sa r ep o i n t e do u t k e yw o r d s ：g e n e t i ca l g o r i t h m ；d y n a m i c8 c h e d u l i n g ；r o l l i n gs c h e d u l i n g ； r o u g hs e t s ；f u n c “o ns r o u g hs e t s t h i 8d i s 8 e r t a t i o ni s s u p p o r t e db yt h es h a n d o n gn a t u r a ls c i e n c e f o u n d a t i o n ( g r a n tn o y 2 0 0 4 g 0 5 ) i n 原刨性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：挝笙垒 日期： 2 盟：互：2 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：幺监导师签名：蛐日期：呈丝型 山东大学硕士学位论文 1 1 引言 第一章绪论 随着人类社会生产力水平的空前飞跃，对资源的需求急剧上升，资源的有 限性问题逐渐摆在了人们面前，对资源的合理配置与优化利用开始成为一个科 学研究的新问题。有限资源的合理配置与优化利用问题是人类社会面临的最基 本经济问题，贯穿于社会生活的各个方面，从一个国家、社会的宏观经济运行 到企业的微观经济活动，都要受到资源条件的限制，人们对它的研究过程中产 生了一个非常重要的理论，就是调度理论。 何为调度? 调度是在满足某些约束的条件下对操作的排序，按照排序给调 度目标分配资源和时间，并且使某个执行目标达到最优。调度存在于人们的生 产、生活和科研活动中，只不过有些调度跃然纸上，有些存在于人们的大脑中。 调度问题来源于不同的领域，如生产计划、计算机设计、电力传输、军队作战、 交通运输、后勤及通讯等 所有调度问题的共同特性是没有一个有效的算法能在采用多项式的有效 时间内求出其最优解，它们都是n p 完全( n o n p 0 1 y n o m i a lc o m p l e t e ) 问题。 调度问题的复杂性、调度领域的多样性和生产环境的动态性，决定了调度问题 的解决单纯依靠人或计算机是难以完成的，必须把人、人工智能技术、数学规 划和计算机有机结合起来去研究调度问题。 1 2 生产调度概述 1 2 1 生产调度的概念 生产调度就是在一定的时间内， 以满足某个或某些特定的生产指标。 资源来完成任务的问题“。 进行可用资源的分配和加工任务的排序， 简单地说，生产调度问题就是按时间分配 山东大学硕士学位论文 共享的可用资源包括：原料、加工设备、存贮设备、运输设备、人力、资 金能源等。加工任务就是指定时间内生产特定的产品。这些产品既可以是用户 订购的产品，又可以是根据市场需求计划生产的产品。生产指标制定的目的是 为了尽可能获得最大的经济效益，所以生产指标一般定位为成本最低、库存费 用最少、生产周期最短、生产切换最少、设备利用率最高、三废最少等。 1 2 2 影响生产调度的因素 影响调度的因素很多，正常情况下有：产品的投产期、交货期( 完成期) 、 生产能力、加工顺序、加工设备和原料的可用性、批量大小、加工路径、成本 限制等，这些都是所谓的约束条件。有些约束条件是必须满足的，如交货期、 生产能力等，而有些达到一定的满意程度即可，如生产成本等。这些约束一般 情况下是可见的或可预见的，因此，在进行调度时，可以作为确定性因素进行 考虑。还有一些非正常情况，如急加工任务的到来，设备的突然故障，原料的 供应不足等，都是事先不可预见的，在进行调度时要作为非确定性因素。 1 2 3 实际生产中的调度问题 企业内部的生产计划调度控制是决定企业竞争力的一个很重要的环节，调 度的好坏直接影响企业所有其他部门( 销售、采购、服务部门等) 的工作效率。 如果企业没有关于生产计划调度管理的有效系统，就无法准确的了解生产过程 情况进而对生产进行调度控制。很多企业误认为企业的订单完成情况良好，而 实际情况并非如此，德国汉诺戌大学生产系统研究所对当地一家著名的金属加 工企业进行了调查，得出了令人吃惊的结果，企业原定的每个工序5 工作日的 计划生产周期，实际上每个工序的评价时间生产周期为8 5 个工作日。实际平 均任务周期为8 0 1 天而不是原计划的5 5 4 天，平均拖期为1 3 天。 这一调查结果完全出乎企业领导人的意料，因为他们在调查开始前对企业 的生产计划能力还抱着满意的态度。同时调查还了解到，3 6 的任务至少有一 个工序没有反馈数据，2 3 的工序记录的工作中心的编号不正确。 由于对实际生产能力缺乏了解，出现了很多所谓的“车间经验”。对此， 2 山东大学硕士学位论文 美国生产计划专家g w p 1 0 s s e l 作过的描述并列出6 个车间“神话”，对我们 现在研究仍然有重要的警示： ( 1 ) 要想使一个车间的生产力提高，就要多给它下达一些任务。遗憾的是， 给一个超负荷的车间下达更多的任务，会使在正确的时刻完成任务更加困难 ( 2 ) 为了使重要的任务按时完成，必须尽可能早地开始处理这个任务。如下 达更多的任务一样，这也会使车间内的在制品库存增加，从而使特定任务按时 完成更加困难。 ( 3 ) 如果计划生产周期不够长的话，就将它延长不可能通过修改计划资料 的方法消除计划与实际生产周期之间的差距重要的是要提高生产能力，消除 超量的任务延迟 ( 4 ) 如果不能为装配按时提供零件的话，就将提供零件的时间提前。这样肯 定会造成更多的紧急任务，从而使处理任务的灵活性减小，使更多的任务与真 正的紧急任务形成竞争，并且影响资料的正确性 ( 5 ) 如果由同一台机床加工的几种零件都不够的话，就将这些零件的加工批 量分得更小。这样看起来情况会有好转，但如果涉及的是一个真正的瓶颈能力 的问题的话，这样的做法将引起许多更严重的问题。 ( 6 ) 如果几个紧急任务被很好的完成了，那么再多几个可能完成得更好。这 种方法企图解决糟糕的计划和控制造成的问题，但是一旦开始能力竞争时。这 种加快方法马上就失败了 图卜2 1 生产周期的恶性循环( p l o s s e l ) 山东大学硕士学位论文 忽视目标与实际能力之间的相互关系会导致生产控制中错误的恶性循环， 如图卜2 一l 所示。 近二十年，生产调度控制方法有了很大的改善，但是还有很多问题没有解 决。很多企业在生产、反馈和生产活动控制系统中广泛应用了数据处理技术， 为能力调度和精确的时间调度花费了很多计算时间，但由计算机计算得到的最 佳生产过程与实际生产过程却很少符合。通常计算得到的周期计划常常由于紧 急订单、技术意外和故障很快就过时了，必须在很短的时间内重新修订精确调 度。因此，为赶日期而绕开系统进行的特别行动在实际生产中经常可见。在线 数据采集系统在企业中广泛应用，为生产计划的修订提供实时的反馈信息，有 关的生产控制方法还在发展，很多关键问题需要进一步的研究。 1 3 车间调度问题 1 3 1 车间调度概述 车间调度( j o bs h o ps c h e d u l i n g ) 就是对一个可用的加工机床集在时间上 进行加工任务集分配，以满足一个性能指标集。从数学规划的角度看，车间调 度问题可表达为在等式或不等式约束下，对目标函数的优化。典型的车间调度 问题包括一个要完成的作业集( 零件集) ，每个作业由一个操作集( 工序集) 所组 成，各操作的加工需要占用机床或其它生产资源( 人员、刀具和辅助资源) ，并 且必须按一些可行的工艺次序进行加工：每台机床可加工零件的若干操作，并 且在不同的机床上能加工的操作集可以不同。调度的目标是将作业合理地安排 到各机床以及合理地使用其它生产资源，并合理安排作业的加工次序和加工时 间，使约束条件被满足，同时优化一些生产性能指标。 生产车间调度问题( j o bs h o ps c h e d u l i n gp r o b l e m ) 是n p 问题。是最困 难的组合优化问题之一妲3 。一般车间调度问题可以描述为：n 个工件在m 台机 器上加工，一个工件分为k 道工序，每道可以在若干台机器上加工。每一台机 器上在每个时间只能加工某个工件的某道工序，只能在上道工序加工完成才能 开始下一道工序的加工，前者称为占用约束，后者称为顺序约束。 车间调度问题的决策内容包括分配决策( 工件的加工顺序) 和时间决策( 工 山东大学硕士学位论文 件各工序的加工时间) 以及路径决策( 工件的加工设备分配) 。 车间调度问题有以下特点： ( 1 ) 复杂性：工件、机器、缓存和搬运系统之间相互影响，相互作用，每 个工件又要考虑它的加工时间、安装时间和操作顺序等因素，因而相当复杂 调度问题是在等式或不等式约束下求指标的优化，在计算量上这往往是n p 一完 全问题，随着问题规模的增大，计算量急剧增加，使得一些常规的方法无能为 力。即使对单台机床加工问题，如果有n 个工件而每个工件只考虑加工时间以 及与操作序列有关的安装时间，则这个问题就和有n 个城市的t s p 问题等价 对一般加工系统，问题更复杂。 ( 2 ) 随机性：在工件加工过程中有很多随机和不确定因素，如工件到达时 间的不确定性，实际工件的加工时间也有一定的随机性而且系统中常有突发 事件发生，如机器的损坏、急加工工件到来等 ( 3 ) 多约束：资源的数量、缓存的容量、工件到期时间，以及工件的操作 顺序等都是约束。此外还有一些人为的约束，如要求各机器上的负荷要平衡等 等。 ( 4 ) 多目标：调度的目标很多，a 1 i s k i r a n 等人将目标分为三类3 ：基于 工件加工完成时间的目标，基于工件到期时间的目标和基于生产成本的目标， 他们在文中列举了几十种目标。实际工件调度往往是多目标的，而且这些目标 之间往往有冲突。 车间调度的规则和性能指标： ( 1 ) 车间调度分配规则：就是在一大堆可加工的工序中，依据某一规则为 每一台机床设备和相应的生产资源选择工序“”。 ( 2 ) 车间调度性能指标：是调度人员和生产管理人员评价调度的标尺。 实际的调度问题往往是多耳标的，而且这些目标往往相互冲突这时，需 要同时考虑多种性能指标，这就是所谓的多目标调度。 1 3 2 车问调度的分类及车间动态调度 1 车间调度的分类 根据研究的侧重点不同，车间调度问题根据资源约束种类和数量的不同可 5 山东大学硕士学位论文 分为单资源车间调度( s i n g l er e s o u r c ec o n s t r a i n e d ) 、双资源车间调度( d u a l r e s o u r c ec o n s t r a i n e d ) 和多资源车间调度( m u l t i p l er e s o u r c ec o n s t r a i n e d ) ； 根据零件和车间构成不同可分为：生产车间调度( j o bs h o p ) 、流水车间调 度( f l o ws h o p ) 、开放车间调度( o p e ns h o p ) 、单车间调度( s i n g l es h o p ) 根据加工工件的特点可将调度问题分为静态调度和动态调度问题： ( 1 ) 静态车间调度( s t a t i cs c h e d u l i n g ) ：所有的零件在开始调度时刻已经 准备就绪，不考虑零件在加工过程中出现的突发事件，如机床突然损坏、零件 的交货期提前、有更紧迫的零件要求被加工等等。 ( 2 ) 动态车间调度( d y n a m i cs c h e d u l i n g ) ：车间调度要求考虑零件在加工 过程中出现的各种突发事件。这种调度方式要求调度能随时响应车间加工能力 的变化，在有突发事件出现后，能立即根据当时的车间加工能力，对待加工的 零件进行重新调度，以确保在任何时候，都能保持车间的加工性能指标处于最 优或次优状态。 2 车间动态调度 无论是离散事件系统还是连续过程生产系统，几乎没有一个生产系统的运 行能够维持在一个一成不变的调度上一方面由于外部原因，即由市场需求变 化引起的产品的订单改变，例如产品数量的变化，交货期的变化等；另一方面 是由于企业内部原因，例如生产设备故障、能源的短缺、加工时间的变化等 这些因素都会使得原来的调度性能变坏或不再可行。所以，再调度 ( r e s c h e d u l i n g ) 或动态调度( d y n a m i cs c h e d u l i n g ) 是不可避免的。 动态调度有两种形式：一种是滚动调度( r o l l i n gs c h e d u l i n g ) 州“，另一 种是被动调度( r e a c t i v es c h e d u l i n g ) 7 1 ”。 滚动调度是指调度的优化随时间推移在一个接一个的时间段内动态进行 生产调度。被动调度( r e a c t i v es c h e d u l i n g ) 则是指当生产过程发生变化，原 来的调度不再可行时所进行的调度修正。滚动调度既可以在静态调度的基础上 进行1 ，也可直接进行“h ”，其最终目的都是尽量在当前优化区域内得到最优 或次优调度。而被动调度是在原有的静态调度的基础上进行的，因此它的调度 目标是尽量维持原调度水平，性能指标下降越小越好。 再调度问题最关心的是在线计算能力问题。为了能在有效的时间内得到一 个较为满意的调度结果，人们希望将问题规模减小，在一个较小的问题空间内 6 山东大学硕士学位论文 得到一个较好的结果，因此大都采用启发式方法和基于滚动的优化调度方法 动态车间调度的工件依次进入待加工状态，各种工件不断进入系统接受加工， 同时完成加工的工件又不断离开，并在工件加工过程中有突发事件发生，因此 动态车间调度要根据系统中当前工件的状况，不断地进行动态再调度。 动态车间调度虽然不能得到全局最优调度，但由于实时性好，能适应动态 的调度环境，所以更多地为生产实际所接受。 1 3 3 车问调度的研究与发展 1 车间调度的研究方法 由于调度问题的复杂性，引起了无数研究者的浓厚兴趣，在过去的5 0 年 里，大量的研究成果相继问世，在对车间调度问题的研究中，有许多方法在各 种有关决策研究的期刊中被报道，这些方法无一例外地吸收了近年来的一系列 先进技术。这些技术包括数学规划方法( 0 p t i m i z a t i o nm e t h o d ) 、启发式方法 ( h e u r i s t i cm e t h o d ) 、仿真方法( s i m u l a t i o nm e t h o d ) 、邻域搜索算法( l o c a l s e a r c h 埘e t h o d ) 和人工智能方法( a r t i f i c i a li n t e l l i g e n c e ) 。 ( 1 ) 数学规划方法 数学规划方法主要是采用数学规划( m a t h e m a t i c a lp r o g r a m m i n g ) 建立模 型，并用分支定界法( b o u n da n db r a n c h ) 等方法求解模型。 数学规划法在车间调度中被广泛的采用。调度问题可以用整数规划法 n 。m ”、混合整数规划法和动态规划法“3 1 来描述。由于调度问题属于n p 问题， 计算的复杂性使得这些方法的运用一直受到限制n ”，直到最近，随着新的先进 技术、更强有力的启发式规则和现代计算机所提供的计算能力，才使得这些方 法又焕发了青春活力。 ( 2 ) 启发式方法 启发式方法“5 ”针对调度问题的n p 特性，并不企图在多项式时间内求得 问题的最优解，而是在计算时间和调度效果之间进行折中，以较小的计算量来 得到近优或满意解启发式方法通常采用调度规则“ 来辅助求解调度问题“订 “”由于调度规则计算量小、效率高、实时性好，因而在动态调度研究中被广 泛采用 7 山东大学硕士学位论文 ( 3 ) 仿真方法 仿真方法是动态调度研究中常用的方法。该方法通过对实际生产环境的建 模，来模拟实际生产环境，从而避开了对调度问题进行理论分析的困难。 通过仿真方法，可分析在不同的调度方法下系统的性能，以便调整调度规 则。将某些方法应用于某个仿真环境，通过仿真评价现有方法之间或新方法与 现有方法之间的优劣，从而总结出各方法的适用范围，或根据结论数据建立知 识库或产生神经网络的训练样本。研究各种仿真参数对仿真结果的影响，以便 使仿真所取得的结论更全面、更有说服力。 ( 4 ) 人工智能方法 从上世纪八十年代初开始，一系列新的技术被用来求解车间调度问题。它 们通常被冠以人工智能的方法，该类方法利用人工智能的原理和技术进行搜 索，将优化过程转化为智能系统动态演化过程，基于系统动态的演化来实现优 化。这类方法包括禁忌搜索2 。m 1 1 ( t a b us e a r c h ) 、模拟退火 川2 2 州( s i m u l a t e da n n e a l i n g ) 和遗传算法( g e n e t i c8 l g o r i t h m s ) 、专家系 统删( e x p e r ts y s t e m s ) 、智能体( a g e n t s ) 州3 盯、神经网络( n e u r a l n e t w o r k s ) 和蚁群系统( a n ts y s t e m ) 等，在这里简要介绍一下本文将要应用 的遗传算法。 遗传算法是一种模仿生物群体进化过程的优化调度算法。给定一组初始解 作为一个群体，通过选择、交叉和变异等遗传操作来搜索最优解。从理论上讲， 遗传算法自身具有很好的鲁棒性，它不但可以解决多种问题，而且可以获得满 意的结果。遗传算法的主要缺点是不能保证总能获得最佳解，但随着遗传结构 的不断优化，它的有效性也在不断提高，这个缺点现在看来已不显得那么突出 了。 遗传算法可用来解决所有的组合优化问题，包括调度问题。遗传算法的最 早运用可以追溯到上世纪六十年代，但直到八十年代末期，随着g 0 1 d b e r g 研 究成果的发表乜“，遗传算法的运用才在工业界获得认可。 f a l k e n a u e r 和b o u f f o u i x 采用遗传算法分别研究了小规模、中规模和大规 模的车间调度问题n ”。他们不仅提出了一种较为合理的编码方式，而且提出了 一种新颖的交叉算子作用在该编码上，用一个估价函数来评价调度的结果。他 们的研究表明遗传算法比通用的启发式调度优越，在交叉算子中，l o x ( l i n e a r 窟 山东大学硕士学位论文 o r d e rc r o s s o v e r ) 比p m x ( p a r t i a l l ym a t c h e dc r o s s o v e r ) 效果好 r e e v e s 应用遗传算法来优化流水车间的生产周期强”他将所提出的算法 与启发式模型和模拟退火进行了比较，结果表明遗传算法获得的结果总是比经 典的启发式方法好。随着问题复杂性的增加，与模拟退火相比，遗传算法的良 好性能表现得更加明显 方剑和席裕庚研究了遗传算法和分派规则的结合“”，有效地处理了与操作 序列有关的工件安装时间和到期时间约束的车间调度问题。 为了解决遗传算法的过早收敛现象和计算速度较慢的问题，c h a ey l e e 等求助于并行遗传算法旺”。在并行遗传算法中，群体被分成若干子群，每个子 群独立地进化，并周期性地交换最优个体除和常规的遗传算法一样具有选择、 交叉和变异这三种遗传算子外，通讯是并行遗传算法特有的算符。按通讯的方 式分为全节点通讯和相邻节点通讯两种，前者是指每个子群和所有其他子群都 交换最优个体，而在后一种方式中只有相邻的子群才交换最优个体。 遗传算法比传统的搜索技术有更强的鲁棒性，因为它不仅能解决某一特定 的问题，而且可以适应不同的问题形式 2 问题讨论与发展 从车间调度问题5 0 年来的应用和发展看，有丰硕的成果，同时也暴露出 许多的问题从车间调度者的观察角度出发，不确定性是调度的最大难点，也 是任何现代化的工厂所无法避免的。比如，任何维护措施不能避免机床损坏， 不可能所有的加工在失控之前都能加以纠正，操作人员不可能总能记住正确的 步骤以及输入正确的数据，由此，实际加工过程的不确定性驱动着整个调度过 程。 传统方法中应用最多的是启发式规则和仿真方法，仿真方法几乎在每种方 法中都有应用。与数学规划方法相比，启发式方法具有计算效率高、实时性好 和算法灵活多变等优点，非常适用于动态调度。但启发式方法也有明显的缺点， 有可能出现所产生的解比全局最优解差很多的情况，而且差的程度总是不确 定，因而通常需要与其它先进技术结合使用。典型的研究方法通常把某种智能 方法、数学规划方法、调度规则和仿真方法结合起来使用 智能调度方法如专家系统、神经网络和遗传算法等，既有许多优点，也有 各自的缺点近年来迅猛发展的人工智能技术，为寻求新的智能调度算法提供 9 山东大学硕士学位论文 了新的途径。z p a w l a k 教授1 9 8 2 年提出的粗集理论( r o u g hs e t s ) 是一种处 理不精确性问题的新的数学工具，基于zp a w l z k 粗集理论，我国学者史开泉 教授提出的s 一粗集理论( s r o u g hs e t st h e o r y ) 与函数s 一粗集理论( f u n c t i o n s r o u g hs e t st h e o r y ) 3 7 1 3 8 1 。”“1 “7 1 是研究系统动态近似特性、知识挖掘和知 识发现的一种新的理论工具。我们把上述粗集理论与其它智能方法、数学规划 方法、调度规则和仿真方法相结合，研究了它们在生产车间调度领域中的应用。 1 。4 论文研究的工作意义，目的与主要内容 1 4 1 论文研究的背景及重要意义 车间作业调度( j s p ) 问题的研究不仅具有重要的现实意义，而且具有深 远的理论意义。车间作业调度就是根据产品制造需求合理分配产品制造资源， 进而达到合理利用产品制造资源，提高企业经济效益的目的。它是产品制造行 业中共存的问题，它与c i m s 中的工厂管理，产品制造层次紧密相关，是c i m s 领域中研究的重要课题。同时车间作业调度因其离散性，动态性，多机性，多 变量性和耦合性等典型的n p - h a r d 性，其研究必然会对n p 问题的研究起到有 意义的影响。 j s p 问题研究需要方法上的改进，尽管j s p 问题的各个研究流派提出了很 多研究方法，但这些方法在不同程度上存在着一定的缺点，若要进一步的研究 j s p 问题，就必须对这些方法进行改进。本文以改进的遗传算法作为求解j s p 问题的主要手段。 1 4 2 论文研究的主要内容及工作 本文首先提出了一种改进的混合遗传算法，以改进后的遗传算法为求解手 段研究了粗集理论在车间调度中的应用。研究了将一类改进的遗传算法应用于 车间调度，在静态车间调度仿真计算中证实了该算法的有效性，获得了较优的 静态调度结果。研究了在生产车间动态加工环境下，当发生设备损坏、急加工 工件到来、新加工工件到来和工件到期时间改变等突发事件时，动态调度窗口 1 0 山东大学硕士学位论文 工件的再识别和再调度，把粗集理论与数学规划和调度专家经验有机结合起 来，研究了其在车间动态调度建模中的应用，并基于改进后的遗传算法求解所 建立的动态调度模型。仿真结果验证了所提方法的有效性，与传统动态调度方 法相比，不仅能够获得较为满意的调度结果，而且能够减少再调度次数、提高 调度系统的稳定性。 本文的主要工作： 第一章绪论：对调度进行了概述，阐述了车间调度的概念和意义、研究 方法和发展方向，对车间调度的各种研究方法进行了简要的介绍，最后阐述了 本文的主要工作。 第二章遗传算法理论与实现技术：介绍了遗传算法的相关概念和定义， 遗传算法相对于其他启发式算法的优点，以及传统遗传算法的不足，介绍了遗 传算法的改进。 第三章基于改进型遗传算法的车间工件调度：研究了一类改进型的混合 遗传算法，建立了一般车闯静态调度数学模型，研究了改迸后的遗传算法在车 间静态调度中的应用，仿真实验结果表明了所提算法的有效性和正确性 第四章粗集及其相关理论：介绍了z p a 霄l a k 粗集理论的相关概念和定义， 及其属性表、等价关系和上下近似特性；介绍了s 一粗集理论及函数s 一粗集的 相关概念和定义，及其动态近似特性、元素动态迁移特性和其所特有的副集特 性 第五章基于粗集理论的车间动态调度：研究了粗集理论在车间动态调度 建模中的应用，基于粗集理论的近似特性，给出了一种车间动态调度窗口工件 识别方法，建立了基于粗集理论的车间动态调度模型，给出了基于改进遗传算 法的车间动态调度算法，通过仿真实验与传统动态调度方法进行了比较，验证 了该算法的正确性和优越性。 第六章总结与展望：总结了本文的主要工作，包括得出的主要结论以及 作者的主要贡献，最后指出了进一步研究的方向。 山东大学硕士学位论文 2 1 引言 第二章遗传算法理论与实现技术 遗传算法( g e n e t i ca l g o r i t h m g a ) 是j h o l l a n d 于1 9 7 5 年受生物进化 论的启发而提出的n ”。g a 的提出在一定程度上解决了传统的基于符号处理机 制的人工智能方法在知识表达、信息处理和解决组合爆炸等方面所遇到的困 难，其自组织、自适应、自学习和群体进化能力使其适合于大规模复杂优化问 题它摒弃了传统的搜索方式，模拟自然界生物进化过程，采用人工进化的方 式对目标空间进行随机化搜索。它将问题域中的可能解看作是群体的一个个体 或染色体，并将每一个体编码成符号串形式，模拟达尔文的遗传选择和自然淘 汰的生物进化过程，对群体反复进行基于遗传学的操作( 遗传，交叉和变异) ， 根据预定的目标适应度函数对每个个体进行评价，依据适者生存，优胜劣汰的 进化规则，不断得到更优的群体，同时以全局并行搜索方式来搜索优化群体中 的最优个体，求得满足要求的最优解g a 是一种通用的优化算法，其编码技术 和遗传操作比较简单，优化不受限制性条件的约束，而其最显著的特点则是隐 含并行性和全局解空间搜索。遗传算法的这些性质，已被人们广泛地应用于组 合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关 智能计算中的关键技术之一 2 2 遗传算法的发展与现状 遗传算法的产生归功于美国m i c h i g a n 大学的h 0 1 1 a n d 在2 0 世纪6 0 年代 初的开创性工作，其本意是在人工适应系统中设计的一种基于自然演化原理的 搜索机制。h 0 1 1 a n d 不仅设计了遗传算法的模拟与操作原理，更重要的是他运 用统计决策理论对遗传算法的搜索机理进行了理论分析，建立了著名的s c h e m a 定理和隐含并行性( i m p l i c i tp a r a l l e l i s m ) 原理，为遗传算法的发展奠定了 基础。将遗传算法应用于函数优化始于d ej o n g 臼”，他在博士论文中设计了 一系列的遗传算法的执行策略和性能评价指标，对遗传算法性能作了大量的分 1 2 山东大学硕士学位论文 析d ej o n g 的在线( o n l i n e ) 和离线( o f f l i n e ) 指标仍是目前衡量遗传算 法性能的主要手段，而他挑选的5 个实验函数( d ej o n g sf i v et e s tf u n c t i o n ) 也是目前遗传算法述职试验中用的最多的试验函数。 在h o l l a n d 和d ej o n g 的工作之后，遗传算法经历了一个相对平稳的发展 时期，逐渐被人们接受和利用。遗传算法的发展高潮开始于2 0 世纪8 0 年代末， 而且延续至今。人们对遗传算法的兴趣日益增长有两个背景：其一是工程领域， 特别是人工智能与控制领域，不断涌现出超大规模的非线性系统，在这些系统 的研究中存在着大量的经典优化方法所不能有效求解的问题，诸如神经网络连 接权重及网络拓扑结构的优化，模糊系统中模糊规则的选取及隶属函数的确 定、知识库的维护与更新等等；其二，遗传算法本身就是一种模拟自然演化这 一学习过程的求解问题方法，它能以独立的或其他方法相结合的形式用于智能 机器学习系统的设计中，经过1 0 年的努力，遗传算法不论在应用上、算法设 计上，还是理论基础上，均取得了长足的进展，已成为信息科学、计算机科学、 运筹学和应用数学等诸多学科所共同关注的热点研究领域h ”。 2 3 遗传算法的基本流程 通常，把遗传算法( g a ) 、进化规划( e p ) 、进化策略( e s ) 和遗传编程( g p ) 统称为进化计算( e c ) 。其中，g a 着重强调基因层次的进化g a 是一类随机优 化算法，但他不是简单的随机比较搜索，而是通过对染色体( c h r o m o s o m e ) 或 个体( i n d i v i d u a l ) 或串( s t r i n g ) 的评价和对染色体及其基因( g e n e ) 的作 用，有效地利用已有的信息来指导搜索有希望改善优化质量的状态。 标准遗传算法 ： 步骤1 ：令k _ o ，随机产生n 个初始个体构成初始种群p ( 0 ) 。 步骤2 ：评价p ( k ) 中各个体的适配值( f i t n e s sv a l u e ) 步骤3 ：判断算法收敛准则是否满足，若满足则输出搜索结果；否则执行 以下步骤。 步骤4 ：令m = o 。 步骤5 ：根据适配值大小以一定方式执行复制操作来从p ( k ) 中选取两个 个体。 1 3 山东大学硕士学位论文 步骤6 ：若交叉概率p a 0 ，1 ，则对选中个体执行交叉操