（机械制造及其自动化专业论文）基于自适应遗传算法的模具企业车间作业调度研究.pdf

独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 关于论文使用授权的说明 2 0 o 乡3 0 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：虚塑导师签名： 摘要 摘要 模具工业是国民经济的重要组成部分，模具制造业的发展水平在一定程度上 代表国家制造业的水平。近十几年来我国模具生产水平取得了巨大的进步，但与 发达国家相比还存在较大差距。除制造技术方面的差距外，模具生产过程的复杂 多变造成管理上的困难也使我国模具企业在车间管理方面与先进国家存在较大 差距。 车间作业调度作为制造系统的一个研究热点，是影响制造业生产效率的重要 因素。优良的调度策略可以帮助模具企业做出准确的生产计划、合理安排资源的 使用、迅速处理生产中的不稳定因素和突发事件，对于提高生产系统的最优性、 提高经济效率，有着极大的作用。为此，本文围绕面向模具企业的车间作业调度 问题展开研究。 本文首先对车间作业调度问题和遗传算法进行了阐述，分析了遗传算法的编 码方式、交叉操作、变异操作等算子的特点以及遗传算子对算法求解精度的影响。 其次，在深入分析模具企业加工特点的基础上，通过简化，为模具企业车间 作业调度问题建立了数学模型，并在遗传算法基础上提出一种适合离散模具制造 企业的通用模型静态调度算法，详细阐述了算法的各项操作，对算法进行了实验 研究，并通过与其它算法的性能对比说明了算法的优化性能。 最后，考虑模具生产中的不确定因素，提出了局部更新和全局更新相结合的、 基于滚动窗口技术的动态调度策略。针对不同的扰动因素，采取不同的调度方案， 既保证调度性能的优化，又兼顾实时性的要求。 关键词模具；车间作业调度；遗传算法；动态调度 北京丁业人学t 学顾1 j 学他论丈 a b s t r a c t m o l di n d u s t r yi st h ei m p o r t a n tp a r to fn a t i o n a le c o n o m i e s ，a n dt h ed e v e l o p m e n t l e v e lo fm o l dm a n u f a c t u r i n gr e p r e s e m st h el e v e lo fn a t i o n a lm a n u f a c t u r i n ga ts o m e d e g r e e a l t h o u g ht h e r ea r es o m ea d v a n c e si nm o l dm a n u f a c t u r i n g ，y e tt h e r ee x i s t sa b i gd i s c r e p a n c yc o m p a r e d 、析mo t h e rd e v e l o p e dc o u n t r i e s b e s i d e st h ed i s c r e p a n c i e s i nm a n u f a c t u r i n gt e c h n o l o g y , a sm a n u f a c t u r i n gp r o c e s sb e c o m e sm o r ea n dm o r e c o m p l e x ，a n di tm a k e sv e r yd i f f i c u l tf o rt h em o l dm a n a g e m e n t ，t h u sw h i c hm a k e s o m ed i s c r e p a n c i e si nm a n a g e m e n tc o m p a r e dw i t l ls o m eo t h e rc o u n t r i e s a sap o p u l a rr e s e a r c hr e a l mi nm a n u f a c t u r es y s t e m ，j o bs h o ps c h e d u l i n g ( j s p ) i sa ni m p o r t a n tf a c t o rt oi n f l u e n c et h em a n u f a c t u r i n gi n d u s t r yp r o d u c t i o ne f f i c i e n c y a ne m i n e n ts c h e d u l i n gs t r a t e g yc a nh e l pt h em o l de m e r p f i s et om a k et h ea c c u r a t e p r o d u c t i v ep l a n ，t h er e a s o n a b l ea r r a n g e m e m sf o rt h eu s eo fr e s o u r c e sa n dh a n d l e st h e p r o d u c t i o no fu n c e r t a i n t y a n du n e x p e c t e de v e n t sr a p i d l y i ta l s o i m p r o v et h e o p t i m i z a t i o na n de c o n o m i ce f f i c i e n c yo fp r o d u c es y s t e m s o ，t h ep a p e rr e s e a r c h e so n t h em o l de n t e r p r i s e sj o bs h o ps c h e d u l i n gp r o b l e m f i r s t l y , t h ep a p e re x p l a i n st h ej o bs h o ps c h e d u l i n gp r o b l e m a n dg e n e t i ca l g o r i t h m ， a n a l y z e st h ee n c o d i n gs t r a t e g y , c r o s s o v e ro p e r a t o ra n dm u t a t i o no p e r a t o ro fg e n e t i c a l g o r i t h m a tt h es f l l t l et i m eg e n e t i co p e r a t o r si n f l u e n c eo ns o l u t i o np r e c i s i o nh a s b e e ni l l u s t r a t e d s e c o n d l y , t h r o u g ht h es i m p l i f i c a t i o n , t h ep a p e re s t a b l i s h e dt h e m a t h e m a t i c a l m o l lf o rt h em o l de n t e r p r i s e sj o bs h o ps c h e d u l i n gp r o b l e mb a s e do nt h o r o u g hs t u d y t h em o l de n t e r p r i s e sp r o c e s s i n gc h a r a c t e r i s t i c b a s e do nt h eg e n e t i ca l g o r i t h m ，i t p r o p o s e saa l g o r i t h mt h a ts u i tt h ed i s c r e t em o u l de n t e r p r i s e sj o bs h o ps c h e d u l i n ga n d g i v e st h ed e t a i l e dd e s i g n t h ee x p e r i m e n t a lr e s u l t ss h o wt h ea l g o r i t h mi sm o r e e f f e c t i v ea n db e t t e rc o m p a r e dw i t ho t h e ra l g o r i t h m s a tl a s t ，ad y n a m i c s c h e d u l i n ga l g o r i t h mb a s e d o nm o v i n gw i n d o wa n d c o n s i d e r a t i o no fl o c a la n dg l o b a lu p d a t ew a sp u tf o r w a r df o rt h eu n c e r t a i n t i e si nt h e a c t u a lm o l dp r o d u c t i o n l o c a lu p d a t i n gs t r a t e g yi sa d o p t e df o rt h o s et u r b u l e n c e st h a t h a p p e ni nh i g hf r e q u e n c yb u th a v el i t t l ee f f e c to nt h es c h e d u l i n g ；o t h e r w i s e ，g l o b a l u p d a t i n gs t r a t e g yi sa d o p t e d k e y w o r d sm o d d ；j o b - s h o ps c h e d u l i n g ；g e n e t i ca l g o r i t h m s ；d y n a m i cs c h e d u l i n g 目录 摘要i a b s t r a c t i i 第1 章绪论1 1 1 课题研究背景及意义1 1 2 国内外研究现状3 1 2 1 车间作业调度的国内外研究现状3 1 2 2 遗传算法的国内外研究现状4 1 3 课题来源及研究内容5 1 3 1 课题来源6 1 3 2 课题研究的主要内容6 第2 章车间作业调度问题研究7 2 1 调度问题描述7 2 1 1 生产调度问题描述7 2 1 2 车间作业调度问题描述8 2 2 车问作业调度问题的分类及特点9 2 2 1 车间作业调度问题的分类9 2 2 2 车间作业调度问题的特点1 0 2 3 车间作业调度的优化算法与策略1 1 2 3 1 车间作业调度的优化算法1 1 2 3 2 车间作业调度的策略1 2 2 4 本章小结1 3 第3 章遗传算法研究1 4 3 1 遗传算法描述1 4 3 1 1 遗传算法的生物学背景。1 4 3 1 2 遗传算法的基本思想1 4 3 1 3 遗传算法的基本内容1 5 3 1 4 遗传算法的特点1 5 3 2 遗传算法的数学基础1 6 3 2 1 模式定理及其意义1 6 3 2 2 积木块假设及其意义17 3 2 3 欺骗性问题。l7 3 2 4 隐式并行性1 8 3 2 5 收敛性分析18 3 3 遗传算法参数与操作的设计1 9 3 3 1 编码1 9 3 3 2 初始群体设定2 l 3 3 3 适应度函数设计2 l 3 3 4 遗传操作设计2 3 3 3 5 算法终止条件2 4 3 4 遗传算法的改进2 4 3 5 本章小结2 5 i i i 北京t 业人学t 学硕f j 学位论文 第4 章基于自适应遗传算法的车间作业调度2 6 4 1 基于工件加工的模具企业车间作业调度问题2 6 4 1 1 模具企业车间作业调度问题的抽象描述2 6 4 1 2 模具企业车间作业调度问题的约束条件2 7 4 1 3 模具企业车间作业调度问题的数学模型2 8 4 2 模型的调度算法设计2 9 4 2 1 确定模型的机器阵与时间阵2 9 4 2 2 编码方案3 0 4 2 3 解码方案31 4 2 4 适应度函数设计3 2 4 2 5 遗传操作算子设计3 2 4 2 6 算法设计流程3 6 4 3 调度应用实例及仿真实验3 7 4 3 ，1 应用实例3 7 4 3 2 算法的仿真实验3 8 4 4 本章小结4 0 第5 章模具企业车间作业动态调度研究4 2 5 1 模具生产过程中的不确定因素4 2 5 2 模具生产动态调度实现4 2 5 2 1 滚动窗口技术4 3 5 2 2 工件选取规则4 3 5 2 3 动态调度策略4 4 5 2 4 动态调度模型修正4 5 5 3 动态调度实例4 5 5 4 本章小结4 7 结论。4 8 参考文献4 9 附录if t 0 6 与f t l0 问题数据表5 3 攻读硕士期间所发表的学术论文5 5 致谢5 6 i v 筇1 章绪论 曼暑曼曼曼曼鼍曼曼曼! 曼! 曼曼曼曼曼皇曼i i_ i i i i i iii 曼曼曼曼曼皂曼舅皇 第1 章绪论 在现代机械制造业中，模具工业己成为国民经济中一个非常重要的行业，其 范围涉及到很多领域。在机械、电子、通讯、轻工、交通等行业，很多产品的零 部件都是用模具成型加工的。模具作为一种高附加值和技术密集型产品，其技术 水平的高低己成为衡量一个国家制造业水平的重要标志之一【l 】。 有资料表明【2 】：大力发展模具工业，提高模具制造水平，对于促进国民经济 的发展有着特别重要的意义，所以模具工业也被称为“黄金工业”，足以说明其 在国民经济中的重要地位。 1 1 课题研究背景及意义 近年来，我国模具工业发展很快，模具工业产值年均增长率约为1 7 3 。 目前，我国已建、在建和正在筹建的模具城( 模具园区) 已有近3 0 个，其中l o 多个己形成一定规模。据不完全统计，我国现有模具生产厂约3 万家，从业人员 近l o o 万人，比上世纪末增长近1 倍。 虽然按生产量和生产能力来看，我国现在己成为一个模具大国，其生产量仅 次于德国、日本，位居世界第三，但是按行业综合水平，特别是模具设计制造水 平和产品水平来看，我们还落后于许多工业发达国家，与世界先进水平相比，大 致要落后1 0 - 1 5 年。造成这种情况的因素除了技术上的差距外，模具企业管理 上的差距更加突出。 在模具生产管理方面，我国模具企业的管理技术水平普遍较低，尤其在车间 生产管理及组织方面还存在许多问题【3 】o 国内许多模具企业还沿用过去作坊式管 理模式，遇到问题时，往往依靠管理人员，特别是车间调度员凭经验处理。由于 无法准确掌握在制模具所有零件的加工进度，所以总是在某些模具接近交货期时， 将制造资源集中地分配给这些模具。这样做最终导致模具企业总是在不停地突击 加工即将到期的模具，极易出现超期，严重影响模具企业的信誉和经济效益。而 国际上许多先进的工业化国家已实现了信息化管理，从生产计划、工艺制定到质 一 检、库存、统计等，普遍使用了计算机。公司内各部门可通过计算机网络共享信 息。这样他们在短期内就可以了解模具生产动态，尽快做出反应。不仅如此，通 过信息化还可以很快了解国际上最先进的模具制造技术。 目前，我国模具企业车间管理主要存在以下几方面的问题【4 j ： 第一客户意图的多变性以及模具企业与客户对模具设计理解的差异导致模 具在生产过程中存在许多不稳定因素； ，i l 京t , i k 人! 芦t 学硕i j 学位论文 第二模具制造部门对于企业的资源( 包括人员，设备，物料) 状态无法及 时掌握，难于做出优化的生产制造计划，往往为了在交货期限内完成任务而采用 加班等办法，无形之中提高了生产成本； 第三不能对模具的每个生产阶段做出准确的生产计划，导致在后续的生产 阶段时间趋紧，同时也影响了整个模具生产过程的并行进行； 第四模具制造计划经常受到新订单、修模或设计变更的冲击，使整个制造 计划难以得到有效的控制； 第五没有有效的预警机制帮助制造部门确定生产计划变更对模具交付期的 影响。 随着科学技术的发展，生产规模越来越大，复杂性越来越高，近几十年来， 各类生产过程都已经发生了显著地变化，其主要特征就是生产规模的大型化和生 产过程的连续化。原来简单的、局部的、常规的控制和仅凭经验的管理已经不能 满足现代生产的要求了，企业管理者和控制工程师们面临的问题是：如何根据市 场上原料供应和产品需求的变化进行经营决策和组织生产；如何在生产计划改变 的情况下对生产过程进行控制，以便最大限度的发挥生产的柔性；如何在生产工 艺不做大的改变的前提下进行管理、决策，使企业产生最大的综合经济效益。 市场竞争越来越激烈，迫使企业必须改进生产管理技术和对生产过程的监控。 越来越多的企业认识到要进一步提高模具行业在国际上的竞争力，必须大力提高 模具企业生产管理水平，积极转变企业的生产制造模式，减少生产过程中不必要 的消耗和浪费，从而达到即精简节约，又高质高效生产高水平模具的目的，以获 得最大的经济效益。 敏捷制造作为2 1 世纪企业的先进制造模式，综合了1 i t 、并行工程、精益生 产等多种先进制造模式的哲理，其目的是要以最低成本制造出顾客满意的产品， 是完全面向顾客的。在这种模式下如何进行组织管理，包括如何组织动态联盟、 如何重构车间和单元、如何安排生产计划、如何进行调度都是面临的主要问题。 其中车间作业调度与控制技术是实现生产高效率、高柔性和高可靠性的关键，有 关资料表明，制造过程中9 5 的消耗发生在非切削过程中【5 】。因此，有效的调度 方法与优化技术的研究和应用，就成为先进制造技术( a m t ) 实践的基础和关 键。 在以信息化促进工业化的思想指导下，我国在模具企业车间作业调度方面展 开了大量研究。廖仁【6 】等研究了模具虚拟企业项目调度，为解决模具虚拟企业资 源受限的多项目调度问题，提出了多项目调度的数学模型，在此基础上采用了一 种混合遗传算法对问题进行求解。宋宏【7 】等研究了考虑冲突的模具生产计划调度 系统，重点研究了随机冲突的处理方法与过程。华中科技大学的熊禾根【8 】等重点 研究了模具企业车间作业计划管理，通过采用面向对象的方法，对模具企业生产 第1 驻绱论 皇曼曼曼曼皇曼曼曼曼皇! 曼曼! 曼! 曼曼曼鼍曼曼曼! ! ! ! 曼! 曼曼! 曼! 曼! ! 曼曼曼曼曼皇曼曼皇曼曼舅舅曼曼曼曼曼! 曼曼曼曼曼曼曼! 曼曼曼曼曼曼寰曼曼曼曼曼曼i i i i ! 过程中与车间作业计划有关的对象进行了详细地分析和描述，以此为基础，进一 步分析了模具企业车间作业计划中的优化目标和约束，建立了相应的动态车f 日j 作 业计划模型，为模具企业编制切实可行的车间作业计划奠定了基础，在充分考虑 模具生产的特点和生产活动之间并行性的基础上，建立了单副模具典型生产过程 的细化网络图，提出了一种基于并行工程，网络计划技术和最优化生产技术 ( o p t i m a lp r o d u c t i o nt e c h n o l o g y ，o p t ) 的模具生产进度计划编制方法【9 j 。 可见，生产调度为模具企业系统地解决车间层生产管理问题提供了有效的途 径。生产调度可以帮助模具企业做出准确的生产计划、合理安排资源的使用、迅 速处理生产中的不稳定因素和突发事件等。 1 2 国内外研究现状 1 2 1 车间作业调度的国内外研究现状 车间作业调度问题是一个经典而又传统的问题，对它的研究始于2 0 世纪5 0 年代。1 9 5 4 年，s m j o l l f l s o n 【l o 】对两台机床f l o w s h o p 型调度问题进行研究后， 提出了n 2 f c m 。和部分特殊的n 3 f c 。她问题的求解方法，这成为经典调度 理论诞生的重要标志。此后，随着制造业的发展，调度问题在生产中的重要性越 来越显现，引发了国内外学者对其进行了大量的探讨与研究，使得新的调度理论 与方法不断被发掘。其过程如下： 5 0 年代后期，这段时期调度理论的研究成果主要是提出了针对一些特殊情 况和规模较小的单机和简单的流水车间问题的解析优化方法，这些方法成为经典 调度理论的基石。 6 0 年代，这段时期主要利用混合或纯整数规划、动态规划和分枝定界法解 决一些有代表性的问题，而对于启发式算法的使用，还处于起步阶段。如s t o r y t l l j 提出采用整数规划方法来求解车间作业调度问题；g a v e t t 【1 2 】开始尝试使用启发式 算法研究车间作业调度问题。这段时期的研究工作，极大促进了调度理论的发展。 在6 0 年代后期，经典调度理论体系初步形成。 7 0 年代，由于调度问题的复杂性( 多数调度问题被证明属于n p - h a r d 问题， 难以找到多项式算法) ，人们开始了算法复杂性的研究。启发式算法在求解复杂 调度问题中凸显的优势引起人们关注。p a n w a l k a r 总结和归纳出了1 1 3 条调度规 则，并对其进行了分类【1 3 】。7 0 年代后期，经典调度理论趋向成熟。 8 0 年代初期，s t e p h e n 等人【1 4 】从多个方面对调度问题进行了重新考察，对未 来发展作了分析和预测，认为理论与实际的结合将会成为今后研究热点。这个富 有挑战性的课题吸引了机械、计算机、管理等诸多领域的学者，许多跨学科的方 法被应用到研究中。其中最引人注目的就是以c a r n e g i e m e l t o n 大学的m f o x 1 5 】 北京tq k 人学t 学硕i 学f _ 论文 为代表的学者们开展的基于约束传播的i s i s 研究，它标志了人工智能开始真正 应用于调度问题。8 0 年代后期，g i m e r 等人【l6 】总结了车问调度的理论和实践方 面的最新研究进展，从七个方面论述了车间调度的技术和方法，认为车问调度无 论在理论还是实践上都已突破了传统界限。 9 0 年代至今，随着计算机应用技术的发展，各种方法在车间调度问题的研 究中得到了充分的发挥，同时新的研究手段层出不穷，用模拟退火算法( s i m u l a t e d a 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 l n e t w o r k s ，a n n ) 、免疫蚁群算法( i m m u n ea n tc o l o n ya l g o r i t h m ) 和遗传算法 ( g e n e t i ca l g o r i t h m ，g a ) 等智能方法解决车间作业调度问题受到人们的高度关注。 人工智能、人工神经网络、基因遗传算法的作业调度方法等被广泛用于j o b s h o p 调度问题的研究【1 1 7 1 。j e f f c o a t 和b u l f i n 1 8 】应用模拟退火法解决资源受制约的调度 问题。l a n g u n a e l 9 】等中采用了并行禁忌搜索法以加快搜索进度，提高效率。姬耀 锋和张德贤【2 0 】提出了一种基于约束满足的自适应神经网络方法，求解车间作业调 度问题。宋晓江【2 l 】等对基于免疫蚁群算法的车间作业调度问题进行了研究。 由于各种车间作业调度算法都存在着不同程度的优缺点【2 2 1 ，所以，近年来， 人们开始将各种算法组合起来进行研究【2 3 j ，以扬长避短，达到优化调度的目的。 黄刚【2 4 】等将遗传算法与模拟退火算法结合在一起，对分批作业的调度问题进行了 研究。李淑娟【2 5 】等结合启发式算法和遗传算法的特点，提出了混合优化调度的方 法，建立了多资源约束的车问优化调度模型。黄吲2 6 】等研究了遗传算法和禁忌搜 索算法及它们的混合策略在车间调度优化问题中的应用现状。李桂芬和鞠彦兵【2 7 】 研究了基于仿真和遗传算法的车间调度优化方法，并通过实验说明了该集成优化 方法的有效性。 1 2 2 遗传算法的国内外研究现状 由于遗传算法的整体搜索策略和优化计算时适应度函数不依赖梯度信息，所 以尤其适用于处理传统搜索方法难以解决的复杂的非线形问题。它在组合优化、 模式识别、机器学习、规划策略、信息处理和人工生命等领域都得到了应用，确 定了它在2 1 世纪的智能计算领域的关键地位。 遗传算法的研究历史可以追溯到六十年代。从六十年代到七十年代中期，是 遗传算法的萌芽期。当时由于遗传算法本身还不成熟，以及这些方法需要较大的 计算量，而当时计算机还不够普及以及速度较慢，所以遗传算法并没有受到普遍 重视。八十年代之后，人们越来越认识到传统人工智能方法的局限性，随着计算 机速度的提高以及并行计算机的普及，遗传算法得到了不断发展，并且将其他算 法与遗传算法进行组合，从而得到混合遗传算法的研究在国际上受到广泛重视。 讹1h 。r 绢沦 1 9 8 5 年，d a v i s 首次将遗传算法用于解决车间作业调度问趔2 8 】，他在使用 g a 求解车间调度问题的研究中取得了近似最优解，并且发表了关于把g a 成功 应用于车间调度问题的论文，充分展示了g a 在解决车间调度问题中的前景。 19 8 9 年，d j g o l d b e r g 出版t ( ( g e n e t i ca l g o r i t h m si ns e a r c h ，o p t i m i z a t i o na n d m a c h i n el e a r n i n g ) ) 一书，总结了遗传算法的主要研究成果，全面完整地阐述了 遗传算法的基本原理及应用。 1 9 9 1 年，d a v i s 又对g a 提出了“h y b r i d i z ew h e r ep o s s i b l e ，同时出版了 ( h a n d b o o ko f g e n e t i ca l g o r i t h m s ) ) 一书，为推广和普及遗传算法起到了重要指 导作用。 19 9 5 年，d o m d o r t f 2 9 】等人用g a 进化工件分配的优先规则序列和s b ( s h i f l i n g b o t t l e n e c k ) 方法意义下的单机解序列。 1 9 9 9 年，c h e n g 3 0 】等介绍了一些求解j s p 的混合算法，包括自适应遗传算子、 基于启发式特征的遗传算子和混合遗传算法的设计。 2 0 0 0 年，h a j r i t 3 1 】等提出了一种受控遗传算法，他们采用并行机编码，用启 发方法产生初始种群，并利用多交叉操作，同时基于模糊逻辑和置信来估计遗传 操作的参数。h a r t 3 2 】等为了深入调查g a 对j s p 这类问题的优化性能，进而分析 g a 的优势与弱点，设计了一个可调整难度的可配置问题的发生器，其研究表明 g a 具有相当好的鲁棒性。k o o n c e l z 【3 3 】等利用数据挖掘算法从由g a 生成的调度 集中抽取知识，从而开发一个规则集调度器来逼近g a 的行为。d i m o p o u l o s p 4 j 等则认为混合遗传算法的研究无疑是一个新的发展方向。c a i 3 5 1 等结合局部搜索 方法和g a 求解j s p 问题。w 0 3 6 】等提出了g a 和成组技术的混合方法，成组技 术的应用降低了问题的复杂性，j s p 在一定程度上转化为f l o ws h o p 问题。 当前，遗传算法的研究背景主要集中在以下两方面：第一是工程领域，特别 是人工智能与控制领域，不断涌现出超大规模的非线形系统，在这些系统的研究 中存在着大量的经典优化方法所不能有效求解的优化问题，诸如模糊系统中模糊 规则的选取及隶属函数的确定、神经网络连接权重等；第二，遗传算法本身就是 一种模拟自然演化这一学习过程的求解问题方法，它能以独立的或与其他方法结 合的方式用于智能机器学习系统的设计中，经过多年发展，无论在应用、算法设 计方面，还是理论研究方面，都取得了长足进步，已成为信息科学、计算机科学、 运筹学和应用数学等诸多科学所共同关注的热点研究领域。 1 3 课题来源及研究内容 车间作业调度问题( j o b s h o ps c h e d u l i n gp r o b l e m ，简称j s p ) 是机械加工制 造行业中共存的问题，它与c i m s q b 的工厂管理、产品制造层次紧密相关，是c i m s 北京t 业人学t 学顾卜学f ? ，论文 领域中研究的重要课题。j s p 问题已被证明是属于n p ( n o n p o l y n o m i a lc o m p l e t e p r o b l e m s ) 难题，被公认为是最困难的组合优化问题之一。对它的研究不仅具有 重大的现实意义，而且具有深远的理论意义。 1 3 1 课题来源 本课题来源于北京市科学技术委员会“汽车发动机轴类零件高效精密加工生 产线成套技术研究与应用 。 1 3 2 课题研究的主要内容 本论文的工作就是在国内外学者的研究基础上，对基于自适应遗传算法的车 间作业调度问题作深入的研究。关注的对象是模具企业的车间作业调度问题，针 对目前模具制造企业中作业计划调度工作的粗放式管理现状，结合企业生产特征， 提出基于遗传算法的调度方法，求解车间作业调度问题。全文共分为五章，各章 主要研究内容如下： 第一章绪论。阐述了本文研究课题的背景及意义，对调度问题和遗传算法 的国内外研究现状进行了说明，最后给出了本文的研究内容和论文的结构安排。 第二章车间作业调度问题研究。描述了车间作业调度的概念、车间作业调 度问题的分类及其特点；概述了车间作业调度问题的优化算法和策略。 第三章遗传算法研究。对遗传算法的产生发展、基本概念、基本思想进行 分析，并对遗传算法的基本原理进行了深入研究，包括遗传算法的操作流程，选 择、交叉、变异等主要遗传操作、理论基础等。 第四章基于自适应遗传算法的车间作业调度。对模具企业车间作业调度问 题进行分析，通过抽象建立出一个有效通用的求解模型，并给出详细的调度算法 设计，并将设计的调度算法应用于具体的生产实例。 第五章模具企业车间作业动态调度研究。详细分析了影响模具生产过程的 动态扰动因素，将滚动窗口技术和作业车间静态调度算法相结合，以事件驱动和 周期性驱动的动态调度策略，作为车间动态调度的实现技术，并应用于具体生产 实例。 第2 “i i i + 乍问f 1 q p 州度问题州究 曼i i iii i 曼曼璺曼曼曼曼皇曼曼皇曼皇皇皇曼曼曼曼曼曼舅舅曼鼍曼曼曼曼皇曼曼曼曼曼曼鼍曼! 蔓曼曼曼曼曼曼皇曼曼曼曼曼曼皇曼曼舅舅曼曼曼曼曼皇曼曼曼曼曼 第2 章车间作业调度问题研究 生产调度问题是生产管理的核心问题和关键技术，是制造系统中最基本、最 重要的问题之一。它在工厂经营管理、产品制造这两个层次上都占有极其重要的 地位和作用，对它的研究主要来源于制造业生产的实际需要。 图2 - 1 显示了生产调度在企业c i m s ( 计算机集成制造系统) 中的位置。 信息控制i + i 标 决策层 管理层 调度层 监控层 控制层 陋够昨鼍拳策j ：习相最天 f jl 广一 鹂仁、l 笪蒋幻 爿嚣喜登l 彳厂儿 一 厨归 jl 堕鳋叠 f 、 图2 - ic i m s 结构模型 f i g 2 - 1t h es t r u c t u r eo f c i m s 2 1 调度问题描述 2 1 1 生产调度问题描述 生产调度问题是在一定的时间内，进行可用共享资源的分配和生产任务的排 序，以满足某些指定的性能指标【3 7 , 3 8 】。一般可以描述为：针对某项可以分解的工 作，在一定的约束条件下，如何安排其组成部分( 操作) 所占用的资源、加工时 间及先后顺序，以获得产品制造时间或者成本等最优。 影响调度问题的因素很多，正常情况下有：产品的投产期、交货期、生产能 力、加工顺序、加工设备和原料的可用性、批量大小、加工路径、成本限制等。 这些因素都是调度问题的约束条件，在进行调度时可以作为确定性因素考虑。而 对于设备故障、原料供应变化、生产任务变化等非正常情况，都是事先不能预见 的，在进行调度时大多作为不确定性因素考虑。 ，i l 京t 业人学t 学坝l 学位论_ _ = 调度中涉及的工厂资源包括：原料、设备( 加工、运输、存储) 、人力、资 金、能源等。资源的详细分配受到产品的生产工艺的限制。 调度的性能指标，大致可以归结为三类： ( 1 ) 最大能力指标包括最大生产率、最短生产周期等，它们都可以归结为 在固定或者无限的产品需求下，最大化生产能力以提高经济效益。在假定存在连 续固定需求的前提下，工厂通过库存满足产品的需求，因此，调度问题主要的目 标为提高生产设备的利用率、缩短产品的生产周期，使工厂生产能力最大，因此， 这类生产调度问题可以称为最大能力调度问题。 ( 2 ) 成本指标包括最大利润、最小化运行费用、最小投资、最大收益等。 ( 3 ) 客户满意度指标包括最短的延迟、最小提前或者拖后惩罚等。 在传统的调度中，一般以平均流通时间最小、制造周期最短、满足交货期为 调度目标，而在实际生产中，由于提前完成的产品必须保存到交货期，而拖期产 品必须交付违约金，因此，在实际调度中更加重视提前或者拖后惩罚调度。 2 1 2 车间作业调度问题描述 生产过程一般按照其输出的产品是呈现连续的产品流、离散的批量、离散的 数量三种情况，分为连续生产过程、间隙生产过程和离散生产过程。 机械加工就是典型的离散生产过程。在离散生产过程中，产品通常是分批( 原 料相同、加工工序相同的一组产品) 制造的，一定数量的产品作为一个工件组， 并且在各台机器之间传输，而且，每个工件都有独立的个性。因此，车间作业调 度就是对一个可用的加工机床集在时间上进行加工任务集分配，以满足一个性能 指标集。 典型的车间作业调度问题包括一个要完成的工件集，每个工件由一个工序集 组成，各操作的加工需要占用机床或其它资源，并且必须按一些可行的工艺次序 进行加工；每台机床可加工工件的若干工序，并且在不同的机床上能加工的工序 集可以不同。调度的目标是将工件合理地安排到各机床，并合理地安排工件的加 工次序和加工开始时间，使约束条件被满足，同时优化一些性能指标。图2 2 显 示了车间作业调度的原理。 第2 章乍问作q p 渊度题研究 ( ，顽藁) - j ( 超爷塞) 二= r 研粟，f 爿 q 勇在嘲 图2 - 2 车间作业调度原理图 f i g 2 - 2t h ep r i n c i p l eo fj s p 在生产中，一台机器在每个时刻只能加工某个工件的某道工序，而且只有该 工件的上道工序完成后才能开始下一道工序。前者是调度问题必须满足的占用约 束，后者称为顺序约束。 车间作业调度问题的决策内容包括分配决策( 工件的加工顺序) 和时间决策 ( 工件各工序的加工时间) 以及路径决策( 工件各工序的加工设备的分配) 。 在实际制造系统中还需要考虑到多个工件在有限的机器上加工，每台机器在 切换不同工件生产时需要一定的准备时间。切换加工次数增加有利于减少工件的 库存，但导致生产率下降。因此，需要在库存成本和工件切换加工频率之间取得 平衡。 生产的柔性体现在设备使用和设备安排两方面，设备使用的柔性是指设备可 用于多个工件的多个工序的加工；设备安排的柔性是指工件的设备加工路径不是 固定和预先确定的，具有可选的路径。 2 2 车间作业调度问题的分类及特点 2 2 1 车间作业调度问题的分类 车间调度问题的分类很多，g r a v e s 等人对它进行了分类整理，按照不同的分 类标准，主要有以下几种类型p 州： ( 1 ) 根据加工系统的复杂程度可分为单机调度、多台并行机调度、 f l o w s h o p 调度和j o b s h o p 调度。单机调度是指所有的操作任务都在一台机器上 完成，它需要对现有任务进行优化排队；多台并行机调度是指多台机器并行加工 工件，而且并行加工的工件和机器是类似的；f l o w s h o p 调度是假设所有的工件 都在相同的设备上完成，并且加工流程都是一致的：j o b s h o p 调度是最一般的调 度类型，它是指由m 个不同的机器加工n 个有特定工艺路线的工件，不同的工件 集一 丌塑 优一 厂l 北京t 业人学t 学f 西! i 学他论文 具有不同的加工操作和加工顺序，不同工件的工序间没有顺序约束，工件加工不 能中断。现代车间调度中通常都是j o b 。s h o p 调度。 ( 2 ) 根据性能指标分为基于调度费用和调度性能两大类。调度费用包括为 了实现调度方案所消耗的各种费用和所造成的损失；调度性能主要包括设备利用 率、最大完成时间、拖延加工任务的百分比等。在实际的生产中，通常需要综合 考虑调度费用和调度性能两方面的因素。 ( 3 ) 根据生产环境的特点可以将调度问题分为确定性调度和随机性调度两 类。确定性调度是指加工时间和其他参数是确定的，已知的；而随机性调度的加 工时间和有关参数是随机的。 ( 4 ) 根据作业的调度特点可将调度分为静态调度和动态调度两种类型。静 态调度是指所有待安排加工的工作均处于待加工状态，因而进行一次调度后，各 作业的力n - r _ 时间都被确定，在以后的加工过程中不再改变；而动态调度是指作业 依次进入待加工状态，各种作业不断进入系统接受加工、同时完成加工的作业又 不断离开，另外还要考虑作业环境中不断出现的动态扰动。因此，动态调度需要 根据系统中作业、设备等的状况，不断进行调度。实际的车间调度通常是j o b s h o p 类型，并且是动态随机调度的。 2 2 2 车间作业调度问题的特点 车间作业调度问题是非常复杂的问题。通常是多约束、多目标、随机不确定 优化问题。求解过程的计算量随问题的规模呈指数增长，已被证明是n p 完全问 题，其特点如下： ( 1 ) 复杂性从原材料到产品，各操作任务相