（机械制造及其自动化专业论文）制造车间生产调度及其算法研究.pdf

武汉理t 大学硕士学位论文 摘要 随着市场经济的发展，市场竞争日趋激烈，多品种、多工序和小批量的情况 已成了现代制造业的主要生产特点，因此，就要求制造企业能够合理安排工序， 高效地利用资源，减少工期，降低生产成本。有效的生产调度方法和优化技术 的研究和应用是实现先进制造和提高生产效益的基础和关键。车间调度问题越 来越受到人们的关注。作业车间调度问题属于n p - h a r d 问题，是典型优化问题 中最难求解的问题。 遗传算法是通过选择、交换和变异等操作使群体进化来进行全局优化搜索 的，虽然它具有具有通用性的一面，但单纯的遗传算法在实际工程应用中常会 存在不成熟的过早收敛。为了克服遗传算法在实际工程优化计算中出现的早熟 收敛问题，以提高遗传算法的全局搜索能力，本文试图将遗传算法和免疫算法 相结合，免疫遗传算法可以有选择、有目的地利用待求解问题中的一些特征信 息来保持个体的多样性，避免早熟收敛和提高求解最优解的收敛速度。用改进 的免疫遗传算法来求解作业车间调度问题。 首先，对本论文的研究背景和意义进行了概述。研究了现代制造车间生产的 现状和特点，以及目前所存在的突出问题，并在此基础上对遗传算法和免疫算 法的研究现状和发展趋势进行了探讨。 其次，对制造车间生产调度的相关问题和理论进行了较为详尽的阐述，对相 关的调度算法进行了初步探讨。 然后，本文对经典遗传算法和免疫算法，以及两者的有机结合进行了研究和 探讨。对两种算法的原理和设计进行了研究，对一些关键的参数和算子提出了 改进方案；重点对两种算法的结合和结合后的优化进行了探讨，并设计了适合 于本文调度实例的改进免疫遗传算法。 最后，本文对改进免疫遗传算法的应用进行了研究。通过测试b e n c h m a r k s 算例，数值实验表明算法收敛速度快，仿真结果较好；将免疫遗传算法( i m m u n e g e n e t i ca l g o r i t h m ，i g a ) 植入实际调度系统，求解了浙江某制造企业的一个简 化生产车问调度实例，调度结果比较理想，达到了预期的效果，从而验证了本 文提出算法的有效性和快速性。 关键词：作业车间调度，遗传算法，免疫算法，免疫遗传算法 a b s t r a c t 、m t he c o n o m i co fm a r k e td e v e l o p m e n t ，t h ec h a r a c t e r i s t i c s o fm u l t i s p e c i e s ， m u l t i - p r o c e s sa n ds m a l lq u a n t i t yh a sb e c o m et h ef o c a lp o i n to ft h em a r k e tw h i c h m a n u f a c t o r vr a c i n gt oc o n t r 0 1 t h e r e f o r e ， m a n u f a c t u r ee n t e r p r i s e ss h o u l db ea s k e dt o r a n g r es e q u e n c e sr a t i o n a l l y , t a k ea d v a n t a g eo fr e s o u r c ee f f i c i e n t l y , s h o r t e nt i m el i m i t f b rap r o j e c ta n dr e d u c et h ec o s to fp r o d u c i n g t h er e s e a r c ha n da p p l i c a t i o no f e f i e c t i v ep r o d u c t i o ns c h e d u l i n gm e t h o d sa n do p t i m i z a t i o nt e c h n i q u e sa r et h ek e y e l e m e n t st oi m p l e m e n tm o d e mm a n u f a c t u r ea n dp r o m o t ep r o d u c t i o ne f f i c i e n c y a n d p e o p l ep a i dm o r ea t t e n t i o n t ot h ej o bs h o pp r o b l e m ( j s p ) m o r ea n dm o r e j s p b e l o n g i n gt on p h a r dp r o b l e mi st h eh a r d e s ts o l v i n gp r o b l e mi n c l a s s i co p t i m i z a t i o n p r o b l e m g e n e t i ca l g o r i t h m ( g a ) i sag l o b a ls e a r c ha l g o r i t h mb yc h o o s i n g ，c r o s s o v e fa n d m u t a t i o no p e r a t i o n st oo p e r a t et h ep o p u l a t i o n a l t h o u g hi t i sac o m m o na l g o r i t h m ， t h es i n g l eg aw h i c hi sa p p l i e di nr e a lp r o j e c tc a nr e s u l t i nt h ep r o b l e mo fe a r l y c o n v e r g e n c e f os o l v et h i sm a t t e ra n di m p r o v et h ea b i l i t yo fg l o b a ls e a r c h ，g a a n d l m m u n ea l g o r i t h m ( t a ) a r ec o m b i n e dt o g e t h e ri n t h i sp a p e r i m m u n eg e n e t i c g o r i t h m ( i g a ) c a nu s et h e f e a t u r ei n f o r m a t i o ns e l e c t i v e l ya n dp u r p o s e f u l l yt o m a i n t a i nt h ed i v e r s i t yo fi n d i v i d u a la n da v o i de a r l yc o n v e r g e n c e ，a n dt oi m p r o v et h e c o n v e r g e n c es p e e d t h e n i ti sd e v e l o p e da n di su s e dt os o l v ej o bs h o pp r o b l e m f i r s t l v ，is u m m a r i z e dt h er e s e a r c hb a c k g r o u n da n ds i g n i f i c a n c eo ft h i sp a p e r i t c o n t a i n st h a tr e s e a r c h i n gt h es t a t u s ，t r a i t sa n do u t s t a n d i n gp r o b l e m so fm o r d e r n s h o p m a n u f a c t u r i n g t h e nis t u d i e dt h er e s e a r c hs t a t u sq u o a n dd e v e l o p m e n tt r e n d so fg a a n di a s e c o n d l v t h et h e o r yo fj o bs h o ps c h e d u l i n gw a ss t u d i e dd e t a i l e d l y a n di t s a l g o r i t h mw a s d i s c u s s e dp r i m a r i l y a n dt h e n t h ec l a s s i c a lg aa n di a , a n dt h e i ro r g a n i cc o m b i n a t i o n w e r e r e s e a r c h e da n dd i s c u s s e d t h ep a p e rr e s e a r c h e dt h et h e o r ya n dd e s i g no ft h et w o a l g o r i t h m s s o m ep o s s i b l ei m p r o v i n gf a c t o r sw e r ea r g u e d o n e o ft h em o s ti m p o r t a n t p a r t si nt h ep a p e rw a st h ec o m b i n a t i o no ft h et w oa l g o r i t h m sa n d i t si m p r o v i n g i d e s i g n e dt h ei g a w h i c hi sf i tf o r t h ee x a m p l e o ft h ep a p e r 武汉理工大学硕士学位论文 f i n a l l y ，t h ea p p l i c a t i o no fi m p r o v e di g a w a sr e s e a r c h e d b yt e s t i n gb e n c h m a r k s i n s t a n c e s ，t h er e s u l t ss h o w e dt h en e wa l g o r i t h mw a ss a t i s f a c t o r y i g aw a sa p p l i e d i n t oar e a l w o r l d s c h e d u l i n gs y s t e mo f am a n u f a c t u r i n ge n t e r p r i s ei nz h e j i a n g p r o v i n c et os e t t l eas i m p l i f i e de x a m p l e t h er e s u l to ft h i se x a m p l ew a sa l m o s tp e r f e c t a n dv e r yq u i c k l y k e y w o r d s ：j o bs 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 ，i m m u n ea l g o r i t h m ，i m m u n e g e n e t i ca l g o r i t h m 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人 已经发表或撰写过的研究成果，也不包含为获得武汉理工大学或其它教育机构的 学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示了谢意。 期：姻二量t 垒 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即学校有权保 留、送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：厦蹩鳖导师签名：吴披日期：恕内分s p 武汉理工大学硕士学位论文 第1 章绪论 1 1 论文的研究背景和意义 随着我国加入w t o 以来，全球经济一体化的步伐进一步加快，世界范围内的 竞争日趋激烈。可以说，2 1 世纪一个重要特征就是全球经济一体化，企业的竞 争领域是全球市场，企业之间的竞争日趋激烈，越来越多的企业认识到企业管 理是企业在竞争中生存的一个重要因素。制造业更不例外。面对市场环境的瞬 息万变，制造企业要想在国内外的市场竞争中立于不败之地，就必须采用各种 先进的技术手段，采用先进的生产运作和管理模式，对客户和市场的要求做出 快速及时的响应，按市场的要求实现低成本、高质量、。短交货期地把产品交付 到客户手中。现在用户对产品的质量以及服务质量的要求越来越高，已不满足 于从市场购买标准化的产品，他们希望得到按照自己要求定制的产品和服务， 这些变化导致产品生产方式革命性的变化。面向订单、多品种、中小批量、高 质量、交货期短以及低成本等已逐渐成为制造业明显的生产特征。其中特别要 说的是，作为现代制造企业的代表，汽车零部件生产企业的状况，由于面向的 客户问题，因为汽车的个性化生产导致所需要的零部件总类日益增加，而每种 零部件所需求的量在持续的减少，因此，上述的生产特征更为明显。 现代制造型企业的主要活动之一是生产管理，即利用企业资源，根据生产 任务和任务顺序约束制定和执行生产计划。生产管理是企业管理中最重要的部 分，而生产管理的大部分工作最终要落实到车间，因此必须加强对车间生产的 管理和控制，从而提高企业的竞争力l 。而生产管理完成的好坏取决于生产计划 的制订。有效的生产调度方法和优化技术的研究和应用，是实现先进制造和提 高生产效益的基础和关键。随着市场竞争的激烈，工厂品种不断增多，批量不 断减少，生产计划不但要以市场需求和客户个性化的要求来确定，还要根据企 业制造资源的实际能力和库存、生产进度的动态变化来调整，制造过程的优化 和监控成为提高企业核心竞争力不可回避的环节1 2 ，3 j 。 制造车间作业调度系统是生产管理的重要职能，是实现生产计划和生产作 业计划的重要手段。车间生产过程的调度问题，是制造系统运筹技术、管理技术 与优化技术发展的核心。车间作业调度与控制技术是实现生产高效率、高柔性 和高可靠性的关键。有效实用的调度方法和优化技术的研究与应用已成为先进 武汉理工大学硕士学位论文 制造技术实践的基础。有关资料表明，制造过程9 5 的时间消耗在非切削过程。 有效的调度方法和优化技术可使车间设备和工人是得到充分利用，生产秩序正 常进行，在制资金减少到最低限度。所以做好生产计划和调度是企业发展要进行 的一项重要任务。即，对制造企业的资源进行有效科学的调度至关重要。 目前，我国的制造业除了设备技术水平相对落后外，更突出的问题是企业管 理模式的落后，尤其是小批量、多品种生产类型车间的生产组织和控制方式已 成为企业发展的障碍。这是因为多品种单件小批生产的企业，产品品种多、每 种产品的数量少、生产重复性小专业化程度不高，设计质量与工艺质量不易提 高。我国大多数制造企业仍采用传统的手工方式编制生产作业计划，并根据主 观的经验来实现调度。这种静态的、工作量极大的计划会因生产过程中每一要 素的变化而受到限制，而调整一般只能通过生产调度员的经验来进行，因此， 整个生产作业计划的编制具有很大的盲目性。2 0 世纪7 0 年代以来我国企业管理 水平有了很大的提高。但还存在很大问题，主要有1 4 j ： 1 管理基础薄弱，缺乏科学的管理方法和工具。例如，在组织生产时，工 艺流程，工时定额等应当齐备，但实际执行是，往往出现工艺路线，工时定额 不完善等情况，造成生产计划与调度严重以来历史经验，而无科学依据。 2 部门间缺乏有效的沟通，造成严重的资源浪费。例如，设计部和市场部 的不协调，造成所生产出来的产品与市场需求有一定的距离，给企业带来的损 失，影响企业的形象。 3 缺乏有效的生产监控机制。包括生产计划监控、零件进度监控与产品或 订单进度监控都是由人工进行统计汇报，由于零部件众多，工作量大，而且很 难能够及时反馈，缺乏动态更新，很难对生产进度实现有效控制和管理，超差 品常常得不到及时补救与处理。生产中采用较为分散的组织管理体制，由于零 件品种多，很多零件属一次性加工，其基础信息如工艺等多凭经验获得，存在 一定的误差，往往造成装配时才发现互相不匹配，导致订单不能按时完成。 4 车间调度效率低。很多企业基本完全依赖管理者的经验、技巧编制各类 生产计划，比较粗放，不仅工作量大，而且不够准确，不能保证生产能力的平 衡，通常缺乏科学性和合理性；计划均衡性差，生产发生变化时计划调整困难， 响应速度慢，不能满足快速响应的要求，且灵活性差。 此外，类似的问题还很多，这些问题归根结底是因为管理不科学，不严格造 成的。 随着市场竞争的加剧，企业的生产正朝着多品种、小批量方向发展。在离散 2 武汉理t 大学硕士学位论文 制造企业里，由于生产的产品品种多、批量小，生产组织工作复杂，尤其是企 业的生产作业计划安排工作难度很大，加上计划的编制往往凭主观经验，计划 的及时性、应变性差，导致产品生产周期长，在制品占用量大，机床利用效率 低等，从而影响了多品种、小批量生产的经济效益。 企业的目的是要以最低成本制造出顾客满意的产品，因此如何进行生产的组 织管理，包括如何组织动态联盟、如何重构车间和单元、如何安排生产计划、 如何进行排产都是目前面临着的问题。生产排产作为车间控制系统( s h o pf l o o r c o n t r 0 1 ) 的重要功能，它主要解决资源的最优安排，优化计划安排，为计划的 执行和控制提供指导。生产排产位于计划的最低层次，它直接决定生产任务是 否能稳定和有序的执行，良好的生产排产能够预先解决生产中的干扰，能够缩 短产品在车间的流动时间，减少在制品库存，保证准时交货。制造系统的生产 排产是针对一项可分解的工作( 如产品制造) ，探讨在尽可能满足约束条件( 如交 货期、工艺路线、资源情况) 的前提下，通过下达生产指令，安排其组成部分( 操 作) 使用哪些资源、其加工时间及加工的先后顺序，以获得产品制造时间或成本 的最优化1 5 。 在我国有众多的面向订单的多品种单件小批生产的汽车零部件生产企业，这 类企业根据订单组织生产，不仅生产品种不断地变化，而且在客户就是上帝的 口号下，已经安排好的生产计划也会突然由于客户需求的改变而改变，于是生 产计划也逐渐变为纷繁复杂的日常工作。面对激烈的市场竞争，落后的管理手 段和较低的管理水平，使企业巨资引进的先进设备也难以发挥出应有的效率， 而一些实力比较雄厚的企业所拥有的e r p 等信息化管理软件也对生产调度显 得无能为力或支持力度不够，企业迫切需要能够提供一种方法帮助其进行有效 的生产计划与管理。 总之，制定满足企业资源约束( 设备、人员等) 的高效的生产计划是企业当 前面临的主要问题，制订合理的生产计划和排产方案，对于制造企业核心竞争 力的提升、对企业的经济效益的提升、对客户满意度的提升，都有着非常重要 的意义。该问题的解决，将解决企业发展的瓶颈，为企业快速发展提供良好的 保障。它对降低生产成本、缩短制造周期、提高生产效益均具有重要的意义。 1 2 车间生产调度理论和优化算法的现状和发展趋势 1 2 1 制造车间生产调度理论的现状和发展趋势 3 武汉理工大学硕士学位论文 作业车间调度问题( j o bs h o ps c h e d u li n gp r o b l e m ，j s s p ) 是一类满足任务 配置和顺序约束要求的资源分配问题，是最困难的组合优化问题之一，同时也 可以视为排序问题，应该说它是生产过程中最古老的问题之一，伴随着大生产 的进程而产生。但真正的发展是近几十年的事，特别是管理成为制约现代企业 发展的重要因素的情况下，人们逐渐认识到生产计划调度成为生产过程中的关 键瓶颈之一，从而引起了广泛的重视。因此，调度理论源于对制造车间生产计 划与控制的研究。而企业车间的生产计划与控制问题在所有调度问题中最具典 型性，所以对车间调度问题的研究一直在调度理论中占居主导地位，仍然以制 造业的生产车间为主要研究对象，所用到的基本术语和问题描述方式大部分都 来自于生产车间各要素的描述。从数学规划的角度看，车间调度问题可表达为 在等式或不等式约束下，对一个或多个目标函数的优化。现代典型的车间调度 问题是：将作业均衡地安排到各处理机上，并合理地安排作业的加工次序和开始 时间，使约束条件被满足，同时优化一些性能指标1 6 j 。 从国内外的发展看，对这一领域的研究主要在如下几方面： 1 排序理沦和调度优先规则的研究。调度问题的研究始于2 0 世纪5 0 年代， 自j o h n s o n 提出了解决n 2 f c m a x 和部分特殊的n 3 f c m a x 问题的优化算法， 建立起第一个排序问题数学模型以来，此后5 0 多年中，广大学者进行了大量的 研究工作，取得了可喜的成绩，提出多达几百条调度和排序的优先规则，象s p ，i ( s h o r t e s tp r o c e s st i m e ) m o r ( m o s to p e r a t i o nr e m a i n i n g ) 等等正在实际生 产的调度系统中被广泛应用。 2 对调度结构和方法的研究。由于调度问题的复杂性和现实世界的多样性， 任何一个调度系统都很难解决所有加工车间的调度问题。因此，广大研究工作 者不断探索各种调度方法和结构以解决实际生产中的调度问题，而且不断提出 新的调度控制结构，如多级多层控制结构、多黑板结构、分布式调度结构等等， 这些方法和结构的出现为解决不同的调度问题提供了有力的工具。 对车间调度领域的研究已有几十年的历史，但至今尚未形成一套完整的方法 和理论，并且多数研究的问题规模较小，或略了很多重要的因素，在建模时对 真实环境进行了大量的简化。离实际应用尚有不小的差距。随着应用数学领域 的进一步发展，生产调度理论必然朝着集成化，多目标化，动态实用化，高度 次优化方向发展【7 1 。其中，对调度问题的复杂性研究已成为工程背景很强的一个 应用数学分支。 生产调度的研究主要可分为建模和调度算法的设计两方面。车问制造系统 4 武汉理工大学硕士学位论文 的建模与描述是研究调度问题的出发点，由于制造过程的复杂性，且纯仿真模 型、数学规划、控制论、图与网络的建模方法各有优缺点，所以目前尚难建立 一个很有效的模型。现行的研究可分为两种趋势，用纯仿真模型、p e t r i 网等来 研究往往能较好的考虑系统的实际因素，然而它们对调度多用启发式规则而不 是寻求一些全局最优的方法。用数学规划方法描述调度问题一般都从优化的角 度来搜索最优或次优解，由于描述方法的限制，忽略了很多实际因素，而且现 行的研究大多只关心工件的调度问题，而对其他资源分配问题像刀具、物料储 运系统的研究不多。因此，如何将这两种思路结合起来是一个值得注意的问题， 目前已有研究者开始此方面的工作【引。 1 2 2 制造车间生产调度算法的发展现状和趋势 在对车间制造系统建立模型后，就要构造相应的调度算法来进行问题的求 解。经过近5 0 年的发展，车间调度问题的研究方法经历了从简单到复杂、从单 一到多元的过程。 总结起来，现有调度问题的解决方法大体上可以分为以下几种类别1 6 j 基于运 筹学( o r ) 方法；基于启发式规则的方法；控制理论方法；基于人工智能( a i ) 的 方法；基于d e d s 的解析模型方法；基于仿真的方法：神经网络( n n ) 优化；基于 模糊数学理论的方法；拉氏( l a g r a n g i a n ) 松弛法；具有计算智能的局域搜索法； 组合调度方法等。也可以区分为精确求解方法和近似求解方法，其中精确求解 方法包括解析方法、穷举方法、分支定界等；近似求解方法包括基于规则的构 造方法、领域搜索方法等。 - 在算法研究方面，基于知识的方法和算法技术相结合的趋势正变的日趋显 著，概率分析方法在算法效率和性能方面的研究日益增多。对于难以求得最优 解的问题，给出了多项式时间的搜索方法具有很大的现实意义，同样算法的随 机性能分析也是比较有效的分析手段。算法研究中，最优化性能的渐进性分析 具有理论指导性，而基于启发式算法的误差估计来确定次优度则无疑具有很大 意义。由于约数条件的存在导致难以建立数学模型，寻求满足约束条件的快速 有效的优化算法正变得更有现实意义【9 1 。在过去二十多年中，近似算法得到了很 大的进步，此类算法兼顾了求解的速度和精度，在合理的时间内寻找尽可能好 的满意解和尽可能大的规模。 求解的方法以启发式算法为主，基于优先权规则。即从未排序的工序特定 子集中选用工序的规则。如枚举法，这种策略计算量大不适于大规模计算；移 5 武汉理工大学硕士学位论文 动瓶颈法( s h i f t i n gb o t t l e n e c k ，s b ) ，这种策略能取得很好的优化结果，但 算法的实现过程相当复杂，不适于工程移植；模拟退火，禁忌搜索等算法的求 解依赖于参数的设定，运算时间长；鉴于精确方法仅适合于小规模问题，构造 性方法优化质量较差且缺少柔性，先进的邻域搜索方法等智能优化算法在生产 调度领域受到广泛重视和研究，其中以遗传算法的研究居多。其操作的基本思 想是预先排出由工序组成的序列( 初始种群) ，对这些序列进行遗传操作，以达 到优化调度的性能指标。当前解决作业车间调度问题最高效的算法通常是混合 式算法，以多种算法共同决策。优先调度规则算法仍是目前首选算法。此外， 由于具有鲁棒性和并行性的优点在车间作业计划研究中也受到非常广泛的青 睐，相比与优先调度规则来说，可以得到更为优化的调度解，且对于中小规模 的实际问题来说，其调度时间也是基本可以接受的【l o 。现在流行的改进型领域 搜索算法有模拟退火算法、禁忌搜索、混沌搜索、便领域搜索、巢分区、隧道 法和进化计算等。遗传算法是一种比较通用的优化算法，其有编码技术与遗传 操作比较简单，优化不受限制性的约束的特点，其有全局寻优的能力。 调度算法的研究主要有两个方向：一个是继续将一些在其它领域得到成功 应用的算法引用过来；另一个是将这些基本调度算法运用一定的技巧组合起来。 目前算法研究更多的是后一种方法【1 1 j 。 在遗传算法研究方面，应用广泛，是一个通用程序，具有并行性，从多个 点开始寻优，容易获得最优解，因此，人们广泛地应用遗传算法解决各种实际 优化问题，如组合优化设计，系统工程，自适应控制，规划设计等。文献【1 2 】内 容既涵盖了遗传算法在传统优化问题中的新进展，又涉及了目前在供应链和物 流研究中相当热门的话题。文献1 1 3 】对遗传算法和启发式算法作了简单的比较； 文【1 4 】采用一种改进遗传算法设计最优交会控制器，建立了自动交会线性二次型 最优控制模型，设计了多操作变异等改进措施，结果表明，改进遗传算法可以 成功地完成参数交会控制器的最优设计，且优于m a t l a b 工具箱和经典遗传算法； 文献【9 j 将机器学习原理应用到解决车间调度问题的遗传算法中，使初始种群中的 每条染色体都有较高的适值，从而使进化过程在经过很少的迭代次数后可达到 稳定；文1 1 5 j 介绍了遗传算法在制造系统设备布局中的应用，首先根据实际布局 情况，将布局归纳为单行和多行两种类型，分别建立相应的布局数学模型，然 后采用遗传算法进行求解，并给出了一个算法求解实例，计算表明文中采用的 遗传优化算法切实可行，有较高搜索效率；文1 1 6 j 提出了一种基于遗传算法的公 交车辆智能调度方法，采用最小费用作为目标函数，考虑了车辆配置、时间、 6 武汉理工大学硕士学位论文 运营效率及资源利用等方面因素，通过选择、交叉及变异等遗传操作，得到了 最优的调度排序方案，仿真结果表明，利用g a 解决车辆调度问题具有可行性、 先进性和快速性；文【1 7 】提出了一种新的中值一开闭滤波器结构，并以此为基础 设计了自适应中值一开闭滤波器。该滤波器由一个中值一开闭滤波器和学习优 化模块组成；等等，均表明，遗传算法的应用不仅具有广泛性，而且很有进一 步研究的价值。 免疫算法研究方面，s f o r r e s t 和a p e r e ls o n 首先提出了免疫系统的遗传 建模方法。k a z u y u k i 等( 1 9 9 8 年) 提出了免疫优化算法并用于解决自适应调度问 题，该算法中，抗体亲和力的计算使用的等位基因和信息嫡，同时还使用交叉 和变异算子生成新个体以保持抗体的多样性【1 8 l ；2 0 0 0 年，g a o 等提出一种基于 免疫多样性的选择算子；国内最早开展免疫优化算法研究的是西安电子科技大 学的王雷、焦李成等人( 1 9 9 8 ) ，他们设计了一种模拟自我免疫机制 ( s e l f - i m m u n i t y ) 的免疫遗传算法i g a 应用于t s p 问题的优化求解，并证明了算 法的全局收敛性，其算法的核心就是加入了最优保持操作1 1 9 】：文献f 冽将生物免 疫算法与遗传算法相结合，提出了一种基于免疫遗传机理的优化计算模型，避 免了遗传算法易出现早熟、搜索效率低及不能很好保持个体多样性等问题；2 0 0 0 年，刘克胜等模拟免疫行为中的浓度限制现象设计了融合嫡以及抗体亲和力的 i g ；文献1 2 1 】将免疫遗传学的基本思想引入到优化设计中。 今后的研究要与数学建模相结合，在实践中不断改进和完善。针对性地研 究企业车间级生产管理和计划( 如车间作业计划、车间监控等) 的研究很少。 突出问题是车间级生产管理【1 0 】。还要对各种算法作进一步的改进。混合算法将 是研究j s p 问题的一个重要发展趋势。调度问题的求解越来越多地用到其它领 域的理论、技术和方法，如控制理论、d e d s 理论、人工智能和系统仿真技术等， 调度理论的研究已经成为一种跨学科和多领域的课题。调度方法的搜索效率和 搜索效果是相互矛盾、相互制约的，通常根据实际情况，需要在两者之间作出 折衷的选择。总之，对车间调度领域这一具有n p - h a r d 特性的研究，随着应用 数学理论的进一步发展，将会朝着集成化、多目标化、动态实用化、高度次优 化方向深人探索。总的来说，调度研究仍然停留在经典调度理论的面向问题框 架之内，还没有出现重大的理论性突破。 1 3 本文的主要工作 7 武汉理工大学硕士学位论文 遗传算法在解决制造车间生产调度问题的研究上有比较成熟的理论，且关于 遗传算法的研究居多。同时，遗传算法更加易于理解和操作。另一方面，免疫 算法作为一个独立的研究分支也尤其独特的优势，它借鉴了生命科学中的免疫 原理。将两者结合产生的免疫遗传算法，利用待求解问题中的一些特征信息来 抑制优化过程中退化现象的出现，可以有效解决遗传算法的早熟收敛等不良影 响，快速收敛于全局最优解。本论文试图用免疫遗传算法解决j s p 调度问题， 总结了遗传算法和免疫算法的基本情况后，提出了一种基于免疫的遗传算法， 将机器学习原理运用在该算法中，并用实际车间数据进行了验证，结果表明该 算法在作业车间调度中能有效地提高调度的效率，加快了进度，不失为一种好 的算法。 本文的研究得到了湖北省数字制造重点实验室基金( 编号：s z 0 4 0 4 ) 的资助。 本文的主要工作为： 1 系统地研究了调度、车间调度的理论及其发展状况，并加以概括总结； 2 深入研究了经典遗传和人工免疫算法的基本情况和操作算子，并在此基础 上提出了一些改进的可能因素； 3 提出了免疫遗传算法的设计，并给出了经典的算法流程图。在此基础上给 出了求解作业车间调度问题的改进免疫遗传算法； 4 利用b e n c h m a r k s 测试集中典型的f t i o ( 1 0 1 0j s s p ) 算例来验证改进 的免疫遗传算法的性能，并利用改进的免疫遗传算法求解某企业生产调度问； 5 最后对本文进行了总结和展望。 8 武汉理 二大学硕士学位论文 第2 章制造车间生产调度问题 调度问题通常指对生产过程的作业计划，譬如工件在机器上的加工顺序、生 产批量的划分等。如今，车间调度主要是针对一项可分解的工作( 如产品制造) ， 探讨在尽可能满足约束条件( 如交货期、工艺路线、资源情况) 的前提下，通过 下达生产指令，安排其组成部分( 操作) 使用哪些资源、其加工时间及加工的先 后顺序，以获得产品制造时间或成本的优化【2 j 。车间调度的内容包括：1 ) 车间进 度的调整与平衡；2 ) 在制品占用量的调整与控制；3 ) 生产技术准备的督促与协 调；4 ) 劳动力的合理调配：5 ) 生产中物资供应的控制与调剂；6 ) 生产设备运行 的调整与控制；7 ) 厂内运输的调配与协调。随着集成化程度的加深，人工智能， 实时反馈等手段的运用，作业车间调度将不在仅仅局限于车间一机器一工件一工序 这样的关系，会与制造企业的信息流、组织结构、决策方式关联起来。 车间生产调度问题的特点可以归纳为：1 ) 建模复杂性；2 ) 计算复杂性；3 ) 动态随机性；4 ) 多约束性；5 ) 多目标性。 若同一机器上既没有任意两个时间区间的重叠，也没有分配给同一个工件的 任意两个时间区间重叠，并且满足调度问题的一些特殊工艺约束，则称一个调 度为可行( f e a s i b l e ) 调度。进而，称使得调度准则或指标最优的可行调度为 最优调度( o p t i m a l ) 。对于m 台机器( m a c h i n e ) m l ，m m ) 对n 个工件( j o b ) j l ，j n 的加工过程，所谓调度就是分配各个工件在各机器上的加工时间， 使调度结果符合某一指标。以一个3 个工件3 个机器的j s s p 为例说明，表2 1 中 每个括弧中第一个数据表工件在哪台机器上加工，第二个数据表示加工时间， 对各个工件的加工顺序进行排序，使所有工件加工完毕后所用的总时间最小。 表2 - 1 一个3 3j s s p ( 3 工件，3 机器) 问题 2 1 车间生产调度问题的分类 9 武汉理工大学硕士学位论文 对于车间生产调度问题，根据应用环境的不同而有不同的类型。按照职能区 分调度问题的标准： 1 开环车间和闭环车间：根据需求的不同，生产调度问题分为开环车间和闭 环车间。在开环车间中，调度问题基于订单，而不考虑库存。在闭环车间里， 调度问题基于现有库存。显然，闭环调度问题较开环调度问题要复杂。 2 过程复杂度：考虑过程复杂度，根据工作阶段和工作位置的不同，生产调 度问题为单机( s i n g l em a c h i n e ) ，单机调度问题是所有的操作任务都在单台机 器上完成，为此存在任务的优化排队问题；多台并行机( p a r a l l e lm a c h i n e ) ， 多台并行机的调度问题更复杂，某个加工操作可在多个机器上加工，因而优化 问题更突出；流水作业调度( f l o ws h o p ) ，流水作业调度假设所有作业都在同 样的设备上加工，并有一致的加工操作和加工顺序；作业车间调度( j o bs h o p ) ， 作业车间调度是最典型的调度类型，不同的作业具有不同的加工操作和加工顺 序，并不限制作业的加工设备。 3 约束标准：约束标准说明了车间调度要达到的目标，车间调度问题的约束 标准有很多，并且非常复杂，有时还互相冲突。经常使用的调度约束标准主要 有：总延迟最小、系统资源效率最优、误工最少、生产效率最高和资源使用平 衡等。 4 参数可变性：参数可变性即调度问题中可变参数不确定的程度。如果参数 波动的数量级比参数本身要小很多，那么这个调度问题可以称为是确定性的； 反之则称为不确定性的，或称随机的。 5 调度环境：调度环境定义了一个调度问题是静态的还是动态的。静态，是 指任务的数量和相关特性并不随着时间改变；反之，如果任务的数量和相关特 性随着时间不断的变化，则称这个问题是动态的。 2 2 车间生产调度问题的计算复杂性 衡量一个算法的好坏，主要有两个标准：一是占用存储的大小，二是所用的 时间的多少。前者称为空间复杂性，后者为时间复杂性。算法的时间和空间复 杂性对计算机的求解能力有重大影响。按照计算复杂性理论研究问题求解的难 易程度，可把问题分为p 类、n p 类s h n p 完全类。作业车间调度问题不仅是n p 难解， 还被认为是最难的组合最优化问题之一，至今没有找到可以精确求得最优解的 多项式时间算法1 2 2 】。 1 0 武汉理工大学硕士学位论文 求解一个问题的算法所用时间的多少，不仅与算法需要多少次运算有关，而 且与所使用的计算机、编制程序的语言和技巧及程序的运行环境等有关。只有 第一个因素能说明算法本身的好坏，所以用算法所执行的运算次数来表示算法 的运行时间p l 。 通常把算法按其复杂程度分成两大类：多项式和非多项式算法。多项式算法 的复杂性都可以以某个多项式为上界；非多项式算法的复杂性不能以多项式为 上界，其执行时间随着问题规模的增大急剧增加，即使中等规模的问题也难以 解决。因此人们常常称多项式算法为有效算法，而认为非多项式算法不是有效 的【1 l l 。所以在理论上，求解的问题按其复杂性可分为三类： 第1 类：存在多项式算法的问题，一般称为p 类问题。 第2 类：不存在多项式算法的问题，一般称为n p 类问题。 第3 类：未找到多项式算法，也不能证明其不存在多项式算法的问题。 其中，在一个集合中，一旦有一个元素被确定归属于第一或第二类问题，那 么集合中的所有元素都属于该类，这个子类就是n pc o m p l e t e ( n p c ) 问题类。 还有一类问题它不比n pc o m p l e t e 容易，任何n p 类的问题都可归约为它，该类问 题被称为n p - h a r d ( n p h ) 问题。绝大部分调度问题是n p h a r d 问题。 2 3 制造车间生产调度问题的描述方法 2 3 1 析取图表示法 析取图是描述j s p 的常用工具，对于7 个工件、历台机器( 共个操作) 的j s p ， 所对应的析取图仁化4 如图2 - 1 示。其中，矿为所有操作构成的顶点集，包 括o 和胖，两个虚拟操作( 分别表示加工开始和结束) ；爿为7 条子边构成的边集； f 为历条子边构成的弧集。 ， 若以最大完成时间为指标，则对j s p 的求解就归结为到各弧( 即机器) 上作 为优先决策的各操作的一组顺序( 即走向) ，当同一机器上有多个操作出现冲突 时，上述顺序用于决定各操作的先后，最终得到各操作间没有冲突的一个有向 非循环图，其关键路径长度即为最大完成时间。 2 3 2 甘特图表示法 甘特图( g a n t tc h a r t ) 是在1 9 1 7 年由亨利甘特( h e n r yl a u r e n c eg a n t t ) 开发的1 2 引。它基本上是一种线条图，横轴表示时问，纵轴表示要安排的活动， 武汉理工大学硕士学位论文 线条表示在整个期间上计划的和实际的活动完成情况。甘特图直观地表明任务 虚线表示同一机器上加 - 实线表示加工路径 图2 13 工件3 机器析取图 m z m i l 0 i 以3 l 3 l 乃。圈i l-lii 图2 23 工件3 机器甘特图 表2 - 2 一个3 3j s s p ( 3 工件，3 机器) 问题 计划在什么时候进行，以及实际进展与计划要求的对比。甘特图使车间的计划 安排情况一日了然成为管理人员了解全局，安排车问进度的有效工具。对于历 台机器 个工件的加工过程，分配各工件在各机器上的加工时问，调度通常用 1 2 武汉理工大学硕士学位论文 甘特图表示。 以一个3 个工件3 个机器的j s s p 为例说明，表2 - 2 中每个括弧中第一个数 据表工件在哪台机器上加工，第二个数据表示加工时间。该实例的一个可行调 度如图2 - 2 所示。 2 3 3 车间生产调度的优化目标 鉴于j o bs h o p 的代表性，本节以m 台机器、n 个工件的j o bs h o p 为例给 出调度性能指标。制造车间生产调度的性能指标费用、质量、时间、数量都可 以作为目标。选择什么样的指标作为优化目标取决于实际需要，因为生产是基 于时间，其它相关目标，费用等目标都可在时间目标上衍生1 9 1 。 1 给出工件完成时问，c 表示工件在系统中存在的时间( 即工件在最后一 台机床上完成加工后的时间) 。定义最大完成时间为 c 一一m a x f ， ，j 一1 2 ，。埘，等于最后一个工件完成加工后离开系统的时间， 极小化最大完成时间通常暗示机器的最大利用率。 2 最大滞后时间m a x i m u ml a t e n e s s ( u 。定义最大滞后时间为 三一一m a x l ，】，歹a1 ，2 ，l 。它测量最大完成期( 最迟完成时间) 。 3 基于库存的性能指标。平均待加工工件数n w ；平均为完成工件数n u ；平 均已完成工件数n c ；平均正在加工工件数n ，；平均机器空闲时间i ；最大机器 空闲时间1 一。( 4 ) 多目标综合性能指标。流经时间和总拖后时间的综合 i + m c 一+ 罗面 台f ，其中入为权重；m a k e s p a n 与总拖后时间的综合 何 。 2 4 调度算法的设计 调度算法的设计通常有以下几个方面的内容： 1 初始条件或初始状态的确定。主要涉及到了车问的生产环境，相同的作 业在不同的生产环境下所用的调度方法可能不同。 2 目标函数的确定。调度问题的目标函数往往不止一个，大多数情况下无 法满足所有的目标函数都达到最优，必须对目标函数进行优先级的确定，以保 持综合最优化。这样以来，又涉及到了如何分析各目标函数问的耦合关系，以 1 3 武汉理工大学硕士学位论文 什么标准来评定是否达到综合最优化的问题。 3 对算法的数学描述。 4 对算法的分析。算法的分析主要有两种方式：一是问题复杂性分析；另 一种是同已有算法的比较分析。其中，前一种比较成熟。 2 5 经典调