（计算机软件与理论专业论文）基于免疫遗传算法的车间作业调度问题研究.pdf

摘要 生产与运作管理的核心是车间作业调度问题能否高效地获得优化解，因此，车间 调度策略一直是制造业研究的重点之一。有效的调度方法与优化技术的研究和应用， 对于制造企业提高生产效率、降低生产成本等方面起着重要作用，越来越受到学者们 的关注。 遗传算法作为应用最广泛的进化计算方法之一，在调度的优化研究方面具有不可 替代的优势。本文根据生命科学中免疫系统的信息处理机制，在一般遗传算法的基础 上，将免疫计算和遗传算法相结合，建立了一种用于车间调度的免疫遗传算法。该算 法通过接种疫苗提高抗体的适应度，通过免疫选择防止种群的退化，同时提出了基于 矢量矩作为选择概率，同时引入免疫疫苗，对该算法进一步加以改进。通过作业车间 调度典型标准问题验证，文中所述免疫遗传算法是可行的，较现有一般遗传算法在收 敛效率和准确性等方面有很大改进与提高。 关键词：车间作业调度遗传算法免疫遗传算法疫苗 a b s t r a c t t h eo p t i m a lp r o d u c t i o ns c h e d u l i n gb e i n gi st h ec o r ei np r o d u c t i o na n d 叩e r a t l o n a l m a i l a g e m e n tt om a x i m i z eb u s i n e s sp e r f o r m a n c ew i t hh i g he f f i c i e n c y a n dl o wp r o d u c t l o n c o s t s c o n s e q u e n t l y , t h er e s e a r c ha n dt h ed e v e l o p m e n t o fa d v a n c e dp l a n n i n ga n ds c h e d u l i n g h a sb e e na na t t r a c t i v es u b i e c ti na c a d e m i ca n di n d u s t r i a lc o m m u n i t i e s g ai so n eo ft h em o s tw i d e l ye v o l u t i o n a r yc o m p u t a t i o n m e t h o d si ns c h e d u l i n g o p t i m i z a t i o nh a si r r e p l a c e a b l ea d v a n t a g e s a c c o r d i n g t ot h ei n f o r m a t i o np r o c e s s t a g m e c h a n i s mo fa l li m m u n es y s t e mi nb i o t i cs c i e n c e ，o nt h eb a s i so fs i m p l eg e n e t i ca l g o r i t h m ， w ep r o p o s ean e wi m m u n eg e n e t i ca l g o r i t h mf o rj o b - s h o ps c h e d u l i n gt h r o u g hc o m b l n l n g i m m u n ea l g o r i t h mw i t hi m p r o v e dg e n e t i ca l g o r i t h m n e wa l g o r i t h mb a s e d0 1 1s e l e c t l o n p r o b a b i l i t yo fv e c t o rd i s t a n c ei sp r o p o s e da n dt h eg e n e r a le x p r e s s i n gf o r mo f t h ek i n do f s e l e c t i o np r o b a b i l i t yi sg i v e n m e a n w h i l et h ei m m u n ev a c c i n ei s i n t r o d u c e di n t o1 m m u n e g e n e t i ca l g o r i t h mo ns e l e c t i o np r o b a b i l i t yo fv e c t o r d i s t a n c et op r e v e n tt h ea l g o n t i u n d e g e n e r a t i v ed u r i n gt h ep r o c e s so fo p t i m i z a t i o n f i n a l l yw ev e r i f y t h ec o n v e r g e n c e e f f i c i e n c ya n da c c u r a c yo ft h e i m m u n eg e n e t i ca l g o r i t h mi ns o l v i n gs t a n d a r dj o b 。s n o p s c h e d u l i n gp r o b l e m s t h ev e r i f i c a t i o nr e s u l t si n d i c a t e t h a ti ti sb e t t e rt h a ns i m p l eg e n e t l c a l g o r i t h m 。 k e yw o r d s ：j o b - s h o ps c h e d u l i n g v a c c i n e g e n e t i ca l g o r i t h m i m m u n eg e n e t i ca l g o r i t h m 长春理工大学硕士学位论文原创性声明 本人郑重声明：所呈交的硕士学位论文， 基于免疫遗传算法的车间作业调度 问题研究是本人在指导教师的指导下，独立进行研究工作所取得的成果。除文中 已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的作 品成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。 本人完全意识到本声明的法律结果由本人承担。 作者签名： 一五乡 长春理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“长春理工大学硕士、博士学位论文版权 使用规定，同意长春理工大学保留并向中国科学信息研究所、中国优秀博硕士学 位论文全文数据库和c n k i 系列数据库及其它国家有关部门或机构送交学位论文 的复印件和电子版，允许论文被查阅和借阅。本人授权长春理工大学可以将本学位 论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫描等复 制手段保存和汇编学位论文。 作者签名： 指导导师签 年l 月毕同 年乡月炒 第一章绪论 1 1 研究的背景与意义 生产调度就是组织执行生产进度计划的工作。生产调度以生产进度计划为依据， 生产进度计划要通过生产调度来实现。生产调度是c i m s ( c o n t e m p o r a r yi n t e g r a t e d m a n u f a c t u r i n gs y s t e m ，现代集成制造系统) 中的一个复杂而且重要的部分，也是实现 企业c i m s 的关键部分。它在c i m s 中的位置处于整个体系结构的中间，发挥两方面 的作用：一方面接受企业决策层的综合生产计划( 含生产、能源、库存、运输、设备等 综合信息) ，经静态计划分解，向下面的设备控制层发布调度命令，即各种生产设备和 原材料用量的设定值；另一方面，接受设备控制层上报的实时状态信息，依次进行动 态调度来改变部分设定值，并把计划执行情况上报企业决策层。生产调度直接影响生 产成本和资源的合理利用，决定着生产过程的顺利进行，生产资源的合理配置和优化。 因此，调度决策水平的提高己经成为现代制造企业中决定生产经营过程能否稳定高效 地运转的决定性因素之一。在过去的几十年里，随着产品制造业市场竞争性的加剧， 不断地激励着人们寻找新的生产调度策略和优化算法，以提高资源的生产率及操作管 理的相对水平，生产出更具有竞争性的产品。车间的调度优化工作，因其在提高生产 效率、降低生产成本等方面所起的重要作用，正越来越受到学者们的关注。 车间作业调度是根据产品制造需求合理分配产品制造资源，进而达到合理利用产品 制造资源、提高企业经济效益的目的。车间生产调度的重要性在于：车间生产调度是 制造系统生产管理的核心，生产管理任务顺利实施与完成，最终要靠合理的生产调度 来保证。它研究的是如何合理地配置加工过程的各种资源，减少零件的加工准备、等 待与传送时间，从而提高设备利用率与生产效率，降低生产成本。因此，及时准确的 生产调度对生产系统的高效运行有着重要的影响，主要表现在生产调度可以保证：生 产计划的有效实施；高效低耗地使用主产资源；均衡主产，减少在制品的资金占用。 缩短产品生产周期、确保产品交货期、降低主产成本，以适应多变的市场需求，对企 业来说是至关重要的，在多品种、中小批量生产环境下的主产调度问题更加复杂和重 要。 目前我国的生态破坏和环境污染已经达到自然生态环境所能承受的极限，为了使经 济增长可持续，缓解巨大的环境压力，必须以环境友好的方式推动经济增长。节能减 排就是要从源头预防污染产生，最有效地减少资源消耗，不排放废弃物，从而真正解 决当代中国的发展困境。近年我国以增加供应为主要目的建设的钢铁、有色金属、电 力、化工、建材等项目相继上马，势必增加能源消耗和废物排放，因此车间作业调度 应该将机器的能源消耗作为一个考虑条件。 在各种车间调度题中，j s s p ( j o bs h o ps c h e d u l ep r o b l e m ，车间作业调度问题) 是最具 代表性的类型，也是f m s ( f 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 调度的核心问题仍是要解决生产车间资源与作业匹配问题，而且 解决这一问题的迫切性较传统生产车间环境要大得多。另外，由于f m s 是c i m s 的基 本组成部分，所以车间作业调度的研究对f m s 的应用，乃至c i m s 的发展都具有重大 的意义。 此外，由于车间作业调度问题属于典型的n p h a r d ( n o n d e t e r m i n i s t i cp o l y n o m i a l ， 非确定性的多项式 ) 问题，而我们周围的现实世界存在许多的n p h a r d 问题。如多任务、 多处理机的分配问题，该问题的解决将对进一步推动物流技术的发展，还有f m s 中机 器人的路径规划问题，该问题的解决同样将对f m s 的应用和发展起到促进作用。所以 说车间作业调度的研究还具有重大的现实意义。 1 2 国内外研究现状 1 2 1 车间作业调度问题的研究现状 车间作业调度问题的研究起源于上世纪5 0 、6 0 年代，调度问题的基础理论仍然是 经典调度理论，s m j o h n s o n 于1 9 5 4 年对n 2 f c m a x 和部分特殊的n 3 f c m a x 问题的 求解是经典调度理论诞生的重要标志【。上世纪5 0 年代后期的研究成果主要是提出了 针对一些特殊情况和规模较小的单机和简单的流水车间问题的解析优化方法，这成为 经典调度理论的基石。 6 0 年代，都是利用混合或纯整数规划、动态规划和分枝定界法解决一些有代表性 的问题。s t o r y 提出采用整数规划方法来求解车间作业调度问题，同时g a v e t t 开始尝试 用启发式算法研究车间作业调度问题。6 0 年代后期，经典调度理论体系初步形成。 7 0 年代，人们开始了算法复杂性的研究，多数调度问题被证明属于n p h a r d 问题， 难以找到多项式算法，因此开始关注启发式算法。p a n w a l k a r 总结和归纳出了1 1 3 条调 度规则，并对其进行了分类。随着7 0 年代后期各类调度问题与调度理论研究的深入及 各种杂交学科的发展，又涌现出了许多新的车间调度理论与方法，如：基于运筹学方 法、基于控制的方法、基于启发式规则的调度方法、基于人工智能的方法、基于知识 的调度方法、确定性最优化方法、整数规划、仿真调度方法等【2 j 。7 0 年代末期，经典 调度理论趋向成熟。 在上世纪8 0 年代初期，s t e p h e n 等人从多个方面对调度问题进行了重新考察，对 未来发展作了分析和预测，认为理论与实际的结合将会成为今后研究热点。这个富有 挑战性的课题吸引了机械、计算机、管理等诸多领域的学者，许多跨学科的方法被应 用到研究中。其中最引人注目的就是以c a r n e g i e m e l t o n 大学的m f o x 为代表的学者们 开展的基于约束传播的i s i s 研究，它标志了人工智能开始真j 下应用于调度问题。8 0 年 代后期，g i f f l e r 等人总结了车间调度的理论和实践方面的最新研究进展，从七个方面 论述了车间调度的技术和方法，认为车间调度无论在理论还是实践上都已突破了传统 界刚3 1 。 2 九十年代至今，随着计算机应用技术的发展，人工智能、人工神经网络、基因遗 传算法、禁忌搜索算法、模拟退火算法等被广泛用于j o b - s h o p 调度问题的研究。基于 遗传算法的车间作业调度，国外已有研究，如f l o r i d a 大学的j j e b i e g e l 和j j d a v i s 提出的用于“车间作业调度的遗传算法 等，但这些研究都不是直接对j s s p 应用遗传 算法而是通过成组技术来对车间作业调度应用遗传算法，这就使得j s s p 研究具有一定 的局限性，即受到成组技术研究与其适应性的限制。t s u ji m u r a 等对三种编码方式：基 于持续的表示、随机键表示和基于工序的表示对求解j s s p 问题进行了比较研究。王锡 禄给出了优化模型和遗传算法求解j s s p 的一般算法框架，但它对遗传算法求解j s s p 的内部具体实现方法探讨很少车间作业调度的遗传算法【4 1 。谢胜利等采用分段结构染色 体编码、可行调度判断和应用修正算子等改进算法求解j s s p 问题。该算法具有较好的 稳定性，但遗传算子和修正算子的选取需要经验或反复试验【5 】。c h ib i n 等提出了两种 改进的自适应遗传算法及相应的编码方案；并比较了6 种不同算法求解j s s p 问题的情 况。文章得出结论：自适应遗传算法优于非自适应遗传算法1 6 j 。苏子林设计了适应路径 柔性调度问题的基于工序的编码。在遗传过程中引入修正种群，实现多种群杂交，以保 持种群的多样性，算法稳定可靠，运行效率大大提高【7 】。 1 2 。2 免疫遗传算法的研究现状 在生命科学领域中，人们早已对遗传与免疫等自然现象进行了广泛而深入的研究。 六十年代，b a 舀e v 和r o s e n b e r g 等先驱在对这些研究成果进行分析与理解的基础上， 借鉴其相关内容和知识，特别是遗传学方面的理论与概念，并将其成功应用于工程科 学的某些领域，收到了良好的效果。1 9 7 5 年美国m i c h i g a n 大学的j h h o l l a n d 提出了 “遗传算法”的概念，并将该算法用于自然与人工系统的自适应行为的研究。时至八 十年代中期，j h h o l l a n d 等人不仅对遗传概念进行了总结与推广，而且给出了简明、 清晰的算法描述，并由此形成了目前人们一般意义上所说的“遗传算法”。 在免疫遗传算法的研究上，美国新墨西哥大学的s f o r e s t 和洛斯阿拉莫斯实验室 的a p e r e l s o n 首先提出了免疫系统的建模方法。c h u n 等基于体细胞理论和免疫网络提出 了一种免疫算法，在这个算法中，将抗原作为目标函数、抗体作为解答、抗原和抗体 之间的亲和力作为解答的联合强度。t a z a w a 等将免疫遗传算法用于超大规模集成电路 的设计，其中主要利用y d , 生境技术【8 】。s h y h j i e r 等利用平均信息熵计算了抗体的亲和 力，再结合简单遗传算法( s g a ) 的交叉和变异算子设计了免疫遗传算法优化燃料调配和 热量生成问题【9 l 。g a o 等提出了一种基于免疫多样性的选择算子，该选择算子依赖于 串的稠密度和适应值，串的稠密度越大，其保留下来的可能性越小，并实验证明该改 进算法的有效性l l o j 。而在控制工程应用方面：t a k a h a s h i 和t a k a y u m i 根据免疫系统中t 细胞免疫回路调节理论设计出一个p i d 型免疫遗传反馈控制器，并用于控制带有非线性 干扰的d c 伺服马达系统，验证了其有效性和稳定性【l 。 在国内，西安电子科技大学的王雷、焦李成等人设计了一种模拟自我免疫机制的 3 免疫遗传算法( i g a ) 应用于t s p 问题的优化求解，并证明了该算法的全局收敛性，其算 法的核心是加入了最优保持操作。王熙法等模拟免疫行为中的抗原识别、抗原记忆和 抗体的抑制、促进等免疫行为并设计出相应的免疫模块，应用于t s p 优化，实验表明： 该算法提高了遗传算法的全局和局部搜索能力，并能够改善未成熟收敛的缺陷。周伟 良等提出了基于浓度控制的i g a 并应用于b p i 陬j 络的辅助设计和解决x o r i h l 题1 1 2 j 。刘克 胜等模拟免疫行为中的浓度限制现象设计了融合熵以及抗体亲和力的i g a 。王忠等在免 疫遗传算法中充分利用最优个体的信息，以最优个体的进化来代替群体的进化，通过 标准差的调整，把局部搜索和全局搜索在进化过程中有机结合起来。该算法的实现手 段着重体现在最优个体的保留、生殖以及标准差的动态调整上，研究表明，该算法具 有搜索效率高和不易陷入局部最优解的优【1 3 l 。罗小平，韦巍有效模拟免疫重组、免疫 记忆、混沌增殖等免疫行为设计出了免疫遗传算法以更好地对多峰值函数的寻优进行 探讨，结果表明免疫遗传算法具备有效地解决局部搜索和全局搜索的能力、有效维持 种群多样性、较好地防止早熟等优点，对实际规划和设计工作能够起到良好的促进和 帮助作用【1 4 1 。 目前对免疫遗传算法的操作步骤还没有统一的说法，王磊等所提出的免疫思想主 要是在合理提取疫苗的基础上，通过接种疫苗和免疫选择两个步骤来完成的。前者是 为了提高适应度，后者是为了防止群体的退化。理论证明了免疫算法是收敛的，结合 t s p 问题，给出了免疫疫苗的选取与免疫算子的构造方法。与通用遗传算法相比较，结 果表明免疫算法不仅是有效的，也是可行的，并较好的解决了已有算法中出现的退化 现象，且使收敛速度有显著提高。严心池等将类似免疫遗传算法进行改进，在合理提 取疫苗的基础上，采用了设置“远亲指针 及交叉变异概率的自适应策略，并将改进 后的免疫遗传算法应用衍架结构的优化中，得到了较好的收敛效果。但是这种方法“提 取疫苗”是个难点，需要对待求问题具备或多或少的先验知识以提取问题基本的特征 信息，通用性不强。刘明辉，李为吉则将类似免疫遗传算法应用架结构的优化设计， 得到的优化结果较遗传算法有所提高。运用类似方法的杨唐胜等提出了人工免疫算法， 算法中没有遗传算法中必有的交叉组合过程，新抗体由高频变异产生，克服了遗传算 法的随机漫游现象，可以保证搜索到全局最优解。增加了记忆细胞，能够对类似抗原 入侵会产生迅速高效的二次免疫应答。 由以上可以看出目前免疫遗传算法尚无统一的进化步骤，在模拟免疫机理上也不 统一，但是它作为一种寻优的思想已经得到应用并显出了强大的搜索能力，因此对免 疫遗传算法进行研究，对工程优化和计算、网络、控制、学习等方面都有重大意义。 目前，将免疫遗传算法应用于在车间调度中的文章尚不多见。 1 3 本文主要完成工作 针对车间作业调度这种典型的组合优化问题，本文主要完成工作如下： 1 系统地研究了调度、车间调度的理论及其发展状况，并加以概括总结。 4 2 深入研究了调度理论的混合优化算法，主要包括遗传算法和免疫算法的定义、 发展状况和研究现状。 3 在对遗传算法基本原理和性能分析的基础上，通过引入生物免疫系统的部分信 息处理机制，并借鉴和吸取现有免疫算法的一些特点，提出一种改进的免疫遗传算法。 着重对遗传算法的改进方法、免疫算子的构造以及算法的整体实现进行深入的研究。 4 用改进的免疫遗传算法解决车间作业调度的问题。全面地剖析了车间作业调度 的问题之后，给出了解决该问题的免疫遗传算法的具体实现步骤。 5 针对车间调度中的典型问题，分别利用标准遗传算法、改进的免疫算法进行了 计算、比较。 1 4 本文内容安排 免疫遗传算法是模拟生物界自然选择和遗传机制的高度并行的、基于多点搜索的 自适应搜索算法，同时它借鉴免疫系统对病毒强大的免疫能力，能实现算法的群体收 敛性和个体的多样性间的动态平衡，从而避免陷入局部最优解。免疫遗传算法结构简 单，对目标函数不要求可微、连续，能方便地处理离散变量，具有良好的全局收敛能 力和收敛速度，所以免疫遗传算法比传统方法具有更广泛的应用。针对车间作业调度 问题的复杂性，随机性等特点，用免疫遗传算法来对它进行求解是一个很好的选择。 本论文共分六章加以阐述，其结构如下： 第一章：绪论，介绍了课题研究的背景与意义、国内外研究现状、主要研究内容 等，主要包括车间作业调度与免疫遗传算法的研究现状，指出本文的主要研究内容是 提出一种新的免疫遗传算法及利用该算法解决车间作业调度问题。 第二章：车间作业调度问题，描述了车间作业调度的概念、车间作业调度问题的 分类及其特点；介绍了车间作业调度的性能指标等问题；概述了车间作业调度问题的 研究方法和调度策略。 第三章：免疫遗传算法的研究，介绍了遗传算法、免疫遗传算法，针对算法的不 足，对免疫遗传算法进行了改进。提出了基于矢量距为选择概率的免疫遗传算法，并 在算法中引入免疫疫苗，对该算法进一步加以改进。定性地分析了改进的免疫遗传算 法的收敛性。 第四章：该章是本文的一个重点，主要介绍了改进的免疫遗传算法求解作业车间 调度问题。本章首先建立了作业车间调度的数学模型，将改进的免疫遗传算法运用到 作业车间调度问题中，并对算法进行详细的分析和设计，详细阐述了算法的步骤。 第五章：通过具体的实例证明改进的免疫遗传算法的有效性。 第六章：结论与展望。对本文的工作做了全面总结，并对进一步的研究方向和研 究意义作了展望。 5 第二章车间作业调度问题的描述 2 1 车间作业调度问题 r o d a m m e r e ae ta 1 j a c k e kb e la l 对j s s p 调度方法、复杂性分析和数学规划模型 进行综述。解决j s s p 调度问题的方法基本上可以分成两大类：精确算法和近似算法。 在精确算法中，分枝定界法是初期解决j s s p 调度问题的最重要方法，其中m c m a h o n g b 提出的改进的分枝定界方法在相当产的时间内一直是最好的精确的求解方法。冲突与 错误是两个不同的概念。冲突处理是应用程序应该包含的一部分，而且冲突允许并发， 甚至在无锁定的状态下仍然如此。 由于实际调度问题的复杂性，精确调度算法难以得到应用，因此，在实际应用中， 往往需要某种近似算法求解调度问题的近似解。优先权规则调度和启发式算法以及基 于局部搜索的算法是最常用的近似算法，a d a m sj e t a l 的移动瓶颈启发式算法是解决 j s s p 问题的一个比较有效的方法。近几年，模拟退火算法、禁忌搜索、遗传算法以及 基于多智能矩阵的方法相继被应用于解决j s s p 问题。 2 1 1车间作业调度问题描述 车间作业调度问题一般可以描述为：对一个可用的加工机床集在时间上进行加工 任务集分配，以满足一个性能指标集。具体而言，就是针对某项可以分解的工作，在 一定的约束条件下，如何安排组成部分( 操作) 所占用的资源、加工时间、及先后顺 序，以获得产品制造时间或者成本等最优，描述如图： 图2 1 车间作业调度描述图 典型的车间作业调度问题包括一个要完成的作业集合，每个作业由一个操作集组 成，包含一个工序集合，各操作工序的完成需要占用机床或其它资源，并且必须按一 些可行的工艺路线、工艺次序进行加工，每台机床可加工零件的若干操作，并且在不 同机床上能加工的操作集可以不同。研究的目的是确定一个调度过程，在约束条件下， 6 该调度将每个工序分配到对应机器的某个时间段，使得完成所有作业所需的加工持续 时间( 制造周期) 最小。在实际车间作业调度研究中，不考虑资源分配，而将资源作为约 束处理。 影响调度问题的因素有很多，正常情况下有：产品的交货期完成期、产品的加工 顺序、加工设备的生产能力和原料的可用性、批量大小、成本限制等，这些都是所谓 的约束条件。有些约束条件是必须满足的，如交货期、生产能力等，而有些达到一定 的满意度即可，如生产成本等，这些约束在进行调度时可以作为确定性因素。而对于 设备故障，原料供应变化、生产任务变化等非正常情况，都是事先不能预见的，在进 行调度时大都作为不确定性因素考虑。 2 1 2 车间作业调度问题特点 1 建模与计算复杂性。车间中机器、工件、缓存搬运系统之间关系复杂，它们之 间又相互影响相互作用。每个工件之间又要考虑它的加工时间、完成时间以及安装时 间和操作顺序等，因而车间作业调度问题显得相当复杂。调度问题往往是通过等式或 不等式约束条件来计算的，属于典型的n p 。h a r d 问题。随着问题规模的加大，计算量 也急剧加大，所以调度问题往往没有精确的解，通常是在解答过程中寻求其最优解或 满意解。 2 动态随机性。调度中存在很多随机性和不确定性，如工件的交货期变更，工件 的加工完成时间，工件的到达时间。另外一些突发事件也增加的调度的难度和随机性， 如机器故障、作业交货期的变更等。 3 多约束性。调度中受到很多约束条件的限制，如缓存容量、资源数量、工件到 期时间与操作顺序等。此外，还有人为的附加因素，如机器负荷平衡等等约束条件。 4 多目标性。调度的目标很多，目标之间往往又相互冲突。主要有基于作业交货 期的目标、基于作业完成时间的目标、基于生产成本的目标三类目标。 正是由于车间作业调度问题具有以上的特点，近年来，众多领域的研究人员都对 其产生了浓厚的兴趣，包括数学、机械、管理、计算机等相关学科的学者，他们用不 同的技术和方法对此进行了广泛、深入、细致的研究，取得了丰硕的成果。 2 1 3 车间作业调度问题分类 对于车间调度问题，g r a v e 等人进行了分类整理，按照不同的分类标准可分为以下 四种f 1 5 】： 1 根据加工系统的复杂程度，可分为单机、多台并行机、f l o ws h o p 和j o bs h o p 。 单机调度问题是所有的操作任务都在单台机器上完成，为此存在任务的优化排队 问题；多台并行机的调度问题更复杂，因而优化问题更突出：f l o ws h o p 型问题假设所 有作业都在同样的设备上加工，并有一致的加工操作和加工顺序；j o bs h o p 是最一般 的调度类型，不同的作业具有不同的加工操作和加工顺序，并不限制作业的加工设备。 7 现在车闻调度类型往往是j o bs h o p 类型的。 2 根据性能指标，分为基于调度费用的指标和基于调度性能的指标两大类。 3 根据生产环境的特点，可将调度问题分为确定性调度和随机性调度问题。 4 根据作业的加工特点，可将调度问题分为静态调度和动态调度。 静态调度是指所有待安排加工的作业均处于待加工状态，因而进行一次调度后， 各作业的加工时间被确定，在以后的加工过程中就不再改变；动态调度是指作业依次 进入待加工状态、各种作业不断进入系统接受加工、同时完成加工的作业不断离开， 还要考虑作业环境中不断出现的动态扰动、如作业的加工超时、设备的损坏等因素。 因此动态调度要根据系统中的作业、设备等状况，不断地进行调度。 2 2j s s p 性能指标及正规性和活动调度 车间作业调度问题的目标是对企业资源进行优化配置，提高企业的经济效益。车 间作业调度的性能指标可以使成本最低、库存费最少、生产周期最短、生产切换最少、 设备利用最高、三废最少等。一个好的调度方案，一般应能做到：均衡生产、在制品 库存量少、操作人员的等待时间或空闲时间少、准时交货、准备时间短、准备费用少 和完成产品的总需求时间短等。实际生产调度的性能指标可以归结为三类： 1 最大能力指标，包括最大生产率、最短生产周期等，他们都可以归结为在固定 或者无限的产品需求下，最大化生产能力以提高经济效益。 2 成本指标，包括最大利润、最小运行费用、最小投资、最大收益等。其中收益 指产品销售收入，运行费用包括库存成本和缺货损失。 3 客户满意度指标，包括最短的延迟，最小的提前或者拖期惩罚等。 定义2 1 对于一个调度问题，设q 为工件的加工完毕时间，称性能指标函数r 是 正规的，若对于满足不等式关系c 1s c l c n sc n l 的任意两组加工完成时 c i 和 c i ) ，对r 必满足r ( c i ，n ) 墨r ( c 1 c n ) 。可以验证最大完成时间m a k e s p a n 为正规性能指标，对于正规性能指标下的调度问题，其求解过程可以简化。 定义2 2 对于j o bs h o p 调度问题，称两个性能指标a 和b 是等价的，若性能指标 a 下的最优调度也对应性能指标b 下的最优调度，且反之亦然，即a 的最优性蕴含了 b 的最优性，同时b 的最优性蕴含了a 的最优性。 容易验证，对于j o bs h o p 调度问题，最大完成时间m a k e s p a n 、平均正在加工工件 数和平均机器空闲是等价的。 j o bs h o p 调度中在正规性能指标下还经常涉及三种调度，即活动调度、半活动调 度和非延迟调度，其定义如下： 定义2 3 称一个调度为活动调度，如果在不推迟其他操作或破坏优先顺序的条件 下，其中没有一个操作可以提前加工。 定义2 4 称一个调度为半活动调度，如果在不改变机器上加工顺序的条件下，其中 没有操作可以提前加工。 8 定义2 5 称一个调度为非延迟调度，如果至少存在一个工件等待加工时，对应地不 存在相应的处于空闲的机器。 上述定义表明，若j o bs h o p 处于非活动调度下，则一定可以找到某些操作，使其 可以更早地加工。当然，有时只能通过改变机器上工件的加工次序来做到。譬如当一 个操作在前道工序完成后，可将其插入到同一机器中操作时间比它长而出现时刻比它 早的另一个操作之前，也即在那个操作还未开始加工前插入到机器的空闲时间内。显 然，通过将非活动化调度转化为活动化调度，正规性能指标必然有所改善。 它们的包含关系如图2 2 所示【1 6 l 。其中f e a s i b l e 指可行解空间，s e m i a c t i v e 指半活 动调度集，a c t i v e 指活动调度集，n o n d e l a y 指活动调度集，o p t i m a l 指问题的最优解空 间。 对于正规化指标最大完成时间，已证明最优调度必为活动调度。因此，如果将搜 索空间限于活动调度集，不仅能保证最优调度的存在，而且能够提高优化效率。 图2 2 三种类型调度及解空间关系图 2 3 车间作业调度问题的研究方法及策略 由于车间作业调度在调度问题中的代表性，很多领域的学者都把各自领域的组合 优化问题抽象为车间作业调度问题。因此，众多学者就车间作业调度问题展开了深入 广泛的研究，特别是机械、管理、计算机、自动化和数学等学科的交叉，带来了车间 作业调度领域众多的新理论和新方法。 2 3 1 车间作业调度问题的研究方法 在对车间调度问题进行研究的方法上，最初是集中在整数规划、仿真和简单的规 则上的，这些方法不是调度结果不理想就是难以解决复杂的问题。随着各种新的相关 学科与优化技术的建立与发展，在调度领域也出现了许多新的优化方法，比如神经网 9 络、模拟退火法、遗传算法、禁忌搜索法等，使得调度问题的研究方法向多元化方向 发展。总结起来，现有调度问题的研究方法大体上可以分为以下几种类别【协2 2 1 。 1 基于运筹学的方法 运筹学方法是将生产调度问题简化为数学规划模型，采用基于枚举思想的分枝定 界法或动态规划算法进行解决调度最优化或近优化问题，属于精确方法。这类方法虽 然从理论上能求得最优解，但由于其计算复杂性的原因，因而不能获得真正的使用。 对于复杂的问题，由于约束和整数变量随着问题规模的增加而呈指数增长，这种纯数 学方法有模型抽取困难、运算量大、算法难以实现的弱点，仅适合较小规模的调度问 题，对于生产环境的动态适应性较差，解决不了动态及快速响应市场需求的问题。 2 基于规则的方法 基于启发式规则即决策规则的调度方法是应用最早，也是目前应用最为广泛的一 种制造系统调度方法。从实用的角度来看，对生产加工任务进行调度的最传统的方法 是使用调度规贝, l j ( d i s p a t c h i n gr u l e s ) ，因为调度规则简单、易于实现、计算复杂度低等原 因，能够用于动态实时调度系统中，在实际中得到了比较广泛的应用，并且不断涌现 出许多新的调度规则，可将其分为三类：简单规则、复杂规则、启发式规则。虽然启发 式规则常被用于实际当中，但它们一般不具有全局优化的特点。许多学者分析了这些 规则对系统性能( 如作业的平均等待时间、设备的平均利用率、总加工时间等) 的影响， 并得出了在诸多约束条件下达到较为有效的调度方法。例以合理的额外计算时间为代 价，换取比单纯启发式规则所得到的更好的调度。在这方面比较有代表性的有移动瓶 颈方法( b o t t l e n e c kp r o c e d u r e ) ，用来解决以最小化制造间距为目标的离散制造型调度问 题，它通过不断地对移动的瓶颈设备进行单机调度，来获取更好的次优解。 3 系统仿真的方法 基于仿真的方法不单纯追求系统的数学模型，而是侧重对系统运行的逻辑关系的 描述，能够对生产调度方案进行比较评价，分析系统的动态性能，并选择系统的动态 结构参数。由于制造系统的复杂性，很难用一个精确的解析模型来进行描述和分析。 通过运行仿真模型来收集数据，可对实际系统进行性能、状态等方面的分析，从 而对系统采用合适的控制调度方法。仿真方法逐渐发展为一种支持人机交互的柔性仿 真工具，并用来进行生产调度。这样就能通过仿真动态地展现离散制造型车间的状态， 分析在不同的调度方法下的系统性能，并运用知识和经验去选择合适的调度方法( 规 则) ，从而改善调度性能。 纯仿真法虽然可以包含解析模型无法描述的因素，并且可以提供给使用者一个调 度性能测试的机会，以便于在调度中加入人的智能，增强系统对动态环境的适应性， 但其不可避免的存在应用仿真进行生产调度的费用高，仿真的准确性受编程人员的判 断和技巧的限制等问题。 4 控制理论方法 g e r s h w i n 等人从控制理论的角度出发，较全面地阐述了控制理论方法在制造系统 1 0 的应用情况。控制理论方法比较适合定量地定义基本问题，但还没有形成一套有效的 调度模型表达、分析设计的技术。其缺点是模型描述能力有限，建模时不得不对真实 环境进行大量的简化，求得最优解的时间随着问题规模的增大而呈指数规律增长。因 此也只适合对小规模的系统求解。 5 基于人工智能渊) 的方法 人工智能的方法是通过提高调度方法的智能来解决各类生产调度问题方法的总 称。由于受实际需要的推动，单一的数学方法和工具不足以解决实际的调度问题，基 于知识的智能调度系统和方法的研究取得了很大进展，主要包括智能调度专家系统、 基于智能搜索的方法及基于多代理技术( m u l t i a g e n ts y s t e m 简称m a s ) 的合作求解的方 法等。其特点是：在支持某些活动发生的资源条件具备时( 称为决策点) ，根据系统当时 所处的属性状态，决定采取何种规则( 策略) ，确定或选择活动发生的顺序和时间，即状 态指导的智能调度方法。人工智能和专家系统的出现对解决调度的实时性和智能性提 供了新的辅助手段。它们用于调度可以克服数学规划和仿真方法的不足，根据系统当 前的状态和给定的优化目标，对知识库进行有效的启发式搜索和并行模糊推理机制， 避开了繁琐的计算，并选择最优的调度策略，为在线决策提供支持。在基于知识和规 则的调度系统中，常用的知识表示法有产生式规则、语义网络、框架等；常用的调度 技术有生产规则、探试法搜索、机会主义的推理、仿真和分级式的分解等。 基于多代理技术的合作求解方法是较新的智能调度方法，它提供了一种动态灵活、 快速响应市场的生产调度机制，它以分布式人工智能( d i s t r i b u t e da r t i f i c i a li n t e l l i g e n c e 简称d a j ) 中的多代理机制作为新的生产组织与运行模式，采用“分而治之”的策略，通 过代理( a g e n t ) 之间的合作以及m a s 系统协调来完成生产任务调度，并达到预先规定的 生产目标及生产状态。由于m a s 固有的对客观世界的强大模拟能力，这种系统多年来 一直是人工智能领域研究的热点。8 0 年代初，m a s 和合同网协议的结合，更加展示了 m a s 在解决复杂动态问题方面的潜力。那以后，m a s 成了车间调度研究中的一个热 门话题。 6 基于离散事件动态系统( d e d s ) 的解析模型方法 该方法主要应用于f m s 生产线。由于制造系统是一类典型的离散事件系统，因此， 可以用研究离散事件系统的解析模型和方法去探讨生产调度问题，诸如排队论、极大 极小代数模型、p e t r i 网等。 极大代数法、动态规划法等都只适合于制造系统的性能分析。p e t r i 网除具有并发、 动态、直观等优点外，还有能够准确快速地反映制造系统实时调度的离散性与随机性 等特点，所以它与其他方法相结合在调度问题中得到了广泛的应用。作为一种图形建 模工具，p e t r i 网可以形象地表示和分析f m s 生产线中加工过程的并发和分布特征以及 多项作业共享资源时的冲突现象，对于描述系统的不确定性和随机性也具有一定的优 越性。在制造自动化领域，利用p e t r i 网及其扩展形式的模型进行死锁分析、调度决策 和性能评价等已有大量理论研究文献目前，p e t r i 网用于制造系统调度存在以下问题： 节点语义的单义性，使得所携带的系统信息不够丰富；重用性差；当调度规则或方法 复杂时，建模困难。 7 基于模糊数学理论的方法 客观现象具有确定性与不确定性两个基本方面，经典数学表达的是现象的确定性； 不确定性一方面表现为随机性，另一方面表现为模糊性。正是利用此特点，许多学者 把它引入了调度领域。但与专家系统相似，这种方法同样存在开发周期长、需要丰富 的调度经验和知识等缺点。 8 拉氏( l a g r a n g i a n ) 松弛法 拉氏松弛法由于其在可行的时间里能对复杂的规划问题提供好的次优解，并能对 解的次优性进行定量评估，近年来已成为解决复杂车间调度问题的一种重要方法。同 时，还可以通过松弛和分解的策略降低问题的求解复杂性，但需要合适选取或调整相 应的算法参数，大多数情况下需要对所得到的解进行再加工，才能够得到可行的较满 意的调度。并且，拉氏松弛法其对偶问题存在搜索效率低、可行调度的构造有待于迸 一步研究等问题。 9 神经网络( n t , 0 优化法 n n 用于车间调度主要有三类方式：1 利用其并行计算能力，求解优化调度，以克 服调度的n p 难问题。2 利用其学习能力，从优化轨迹中提取调度知识。3 用n n 来描 述调度约束或调度策略，以实现对生产过程的可行或次优调度。h o p f i e l d 神经网络模型 的提出为求解各种有约束优化问题开辟了一条新途径，用h o p f i e l d 网络解决t s p 问题 就是其在组合优化问题中的最成功的应用之一。 1 0 具有计算智能的邻域搜索法 邻域搜索方法是一类新兴的近似寻优技术，它的思想是对调度问题的解进行编码， 编码与问题的调度方案相对应。搜索过程从任一有效编码出发，通过对其邻域的不断 搜索和对当前序列的替换来实现优化。这类方法的应用场合通常是规模较大、传统方 法难以求解的问题。这类方法虽然是近似算法，但在解决n p 完各问题时已经展现出惊 人的优越性。近年来，一些高级局域搜索法由于具有普遍适应性和较低的经验复杂性 等优点，因而在工程中得到了相当广泛的应用。主要有以下几种比较流行的邻域搜索 方法： ( 1 ) 遗传算法( g e n e t i ca l g o r i t h m ，g a ) g a 原理和操作简单、通用性强、不受限制条件的约束，且具有隐含并行性和全局 解空间搜索能力，在机器学习、模式识别、控制工程、优化等领域，尤其是在生产调 度领域得到广泛的应用。与其它搜索算法相比，遗传算法优越性主要表现在：在搜索 过程中不易陷入局部最优，即使在所定义的适应度函数非连续不规则的情况下，也能 以极大的概率找到全局最优：具有固有的平行性，使得它非常适于大规模并行分布处理： 易于和别的技术相结合，形成性能更优的问题求解方法。g a 的早熟和搜索效率低问题 是它的主要缺陷。如何利用g a 高效求解调度问题，一直被认为是一个具有挑战意义 1 2 的难题并成为研究的热点，近年来涌现出大量论文并取得较大进展。 ( 2 ) 禁忌搜索( t s ) 算法 禁忌搜索( t a b us e a r c ht s ) 是解决复杂组合优化问题的一种搜索策略和方法，由 g l o v e 等人提出、完善和发展。对于复杂的组合优化问题，禁忌搜索也是一种通过领域 搜索以获取最优解的方法，禁忌搜索是一种迭代方法，它开始于一个初始可行解s ，然 后移动到邻域n ( s ) 中最好的解s ，即s 对于目标函数e ( s ) 在领域n ( s ) 中是最优的。然