（企业管理专业论文）基于混合遗传算法的多目标多机并行作业车间高度问题研究.pdf

合肥工业大学 本论文经答辩委员会全体委员审查，确认符合合肥工 业大学硕士学位论文质量要求。 答辩委员会签名 主席：y 1 沙m 国科学技术大学教授 委员： 芝亨 合肥工业大学教授 导师： 币夺 月巴工业大学副教授 合肥工业大学教授 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究 成果。据我所知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已 经发表或撰写过的研究成果，也不包含为获得 金目曼王些太堂 或其他教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示谢意。 、 学位论文作者签字： 签字日期：易1 7 年争月刁日 学位论文版权使用授权书 本学位论文作者完全了解金目巴王些太堂有关保留、使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借 阅。本人授权 金目墨王些太堂 可以将学位论文的全部或部分论文内容编入有关数 据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文者签名：赵 签字日期舢年侈月矽日 学位论文作者毕业后去向： 工作单位： 通讯地址： 导师签名： 签字日期：年月日 电话： 邮编： 基于多目标多机并行作业车间调度问题的混合遗传算法研究 摘要 本文研究的是多目标多机并行作业车间调度问题的算法。作业车间调度 是一种典型的n p h a r d 问题。文章首先介绍了多机并行作业车间调度的基本 概念，在对国内外研究现状、发展趋势以及所存在的问题进行深入研究后， 对多目标多机并行作业车间调度问题进行数学建模并提出算法。 本文通过设计合适的编码方式和矩阵式的交叉变异算子，结合依角度聚 类和邻域局部搜索等操作改进了传统的遗传算法在该问题中的应用。最后分 别在五组仿真数据模拟求解，该算法具有较明显的优势。 关键词：多机并行；作业车间调度；多目标；遗传算法；聚类分析 h y b r i dg e n e t i ca l g o r i t h mo p t i m i z a t i o nb a s e dm u l t i o b j e c t i v e m u l t i m a c h i n ejo bs h o ps c h e d u l i n g a bs t r a c t i nt h i sa r t i c l es t u d i e st h ea l g o r i t h mf o rm u l t i o b j e c t i v em u l t i m a c h i n ej o bs h o p s c h e d u l i n gp r o b l e m t h em u l t i m a c h i n ej o bs h o ps c h e d u l i n gp r o b l e mi s ac l a s s i cn p - h a r d p r o b l e m a tf i r s t ，t h i sp a p e ri n t r o d u c e dt h eb a s i cc o n c e p to ft h em u l t i m a c h i n ej o bs h o p s c h e d u l i n g a f t e ri n d q ) t hs t u d yo ft h er e s e a r c hs t a t u sa n dd e v e l o p m e n tt r e n d ，ig i v ea m a t h e m a t i c a lm o d d i n ga n dt h e np r o p o s e daa l g o r i t h m t h i sr e s e a r c hp r o p o s e sah y b r i dg e n e t i ca l g o r i t h mb a s e do ns e q u e n t i a lc o d i n go f j o b s o nm a c h i n e sa n di n t e r l e a v e dm o d ei nm a t r i xf o r m ，a n di n t e g r a t e ss e a r c ha r e aa n dc l u s t e r a n a l y s i s ，m a k i n gt h ep a r t e os o l u t i o ns e tm o r ee f f e c t i v ei nq u a l i t ya n dd i s t r i b u t i o n k e yw o r d ：m u l t i m a c h i n e ；j o b - s h o ps c h e d u l i n g ；m u l t i - o b j e c t i v e ；g e n e t i ca l g o r i t h m ； c l u s t e ra n a l y s i s 致谢 毕业在即，此时此刻我的心中感慨万分。研究生三年时间转眼即逝，这三 年里我不仅在学识上有长足提高，更重要的是一种人生的经历。这是合肥工业 大学对我精心栽培的成果，也是管理学院诸位老师对我严格要求的成果，更是 决策科学与技术研究所所有老师对我谆谆教导的成果。 在这三年里我的导师刘心报教授对我的指导和关怀无处不在。在这里我要 向刘老师表示最衷心的感谢和祝福，是刘老师严谨的态度和学习作风给我以深 远的影响，让我受益匪浅。 在硕士期间，我的进步也离不开刘林老师在学术研究上对我的指导，实验 室里裴风老师、周谧老师、张夏梓师姐、裴军、张玉蕾、葛菲菲、孙博、王小 伟等同学给予我帮助。感谢你们。 同时还要感谢我的父母家人在生活上对我的照顾，感谢王蕾在学校生活中 对我的关照。论文在研究期间j 我的朋友郑新、张鹏杰在编程和算法上都给予一 我很大的帮助，谢谢! 同时感谢审阅我的论文和参与我的论文答辩的各位老师，感谢他们在百忙 之中帮助我完成硕士论文的最后一个过程，我荣幸之至! 作者：盛骢 2 0 11 年4 月 目习 第一章绪论1 1 1 课题研究背景及意义l 1 2 多机并行作业车间调度问题研究现状及存在问题。2 1 2 1 研究现状2 1 2 2 多机并行作业车间调度存在问题3 1 3 论文研究内容及论文框架4 1 3 1 论文主要研究内容4 1 3 2 论文框架5 第二章多机并行作业车间调度问题描述和建模6 2 1 作业车间调度问题描述。6 2 1 1 作业车间调度问题概念6 2 1 2 作业车间调度问题的特点7 2 1 3 作业车间调度的目标8 2 2 多机并行作业车间调度问题描述8 2 3 多机并行作业车间调度问题的建模。9 2 3 1 车间调度问题的建模方法9 2 3 2 多机并行作业车间调度的优化模型1 l 2 4 本章小结1 2 第三章求解多机并行作业车间调度问题的改进混合遗传算法1 3 3 1 作业车间调度问题的研究方法1 3 3 2 改进混合遗传算法。1 6 3 2 1 遗传算法的基本流程1 6 3 2 2 遗传算法的基本操作1 7 3 2 3 混合遗传算法的改进18 3 3 多机并行作业车间调度问题的改进混合遗传算法1 9 3 3 1 算法流程设定1 9 3 3 2 算法介绍2 0 第四章仿真算例及结果分析2 3 4 1p a r e t o 解集评价标准2 3 4 2 算法对比分析2 3 4 2 1 数据及参数设置2 3 4 2 2 实验结果。2 3 4 2 3 实验结果分析2 7 第五章总结与展望2 8 5 1 结论2 8 5 2 后续工作展望2 8 插图清单 图1 1 论文框架图5 图3 1 初始生成种群1 9 图3 2 依角度聚类2 0 图3 3 邻域搜索优化2 0 图3 4 粒子与优解交叉进化2 0 图4 1 ：8 6 1 2 规模下三种算法结果对比图2 3 图4 - 2 ：8 6 1 2 规模下p a r e t o 解之一甘特图2 4 图4 3 ：1 0 8 1 5 规模下三种算法结果对比图2 4 图4 - 4 ：10 8 15 规模下p a r c t o 解之一甘特图2 5 图4 - 5 ：2 0 8 1 5 规模下三种算法结果对比图2 5 图4 6 ：3 0 1 0 2 0 规模下三种算法结果对比图2 6 图4 7 ：5 0 1 5 3 0 规模下三种算法结果对比图( 注：y 值为同减少8 5 0 0 0 后的值) ：z 6 表格清单 表2 1 ：多机作业车间调度时间表。9 表4 1 ：算法质量、分布及最小值对比2 7 第一章绪论 1 1 课题研究背景及意义 随着经济全球化的趋势越来越明显，科学技术的发展越来越迅速，企业与 企业之间的市场竞争日益激烈，当前，全球工业的生产方式普遍朝向大规模、 一体化的方向发展，这就直接导致了企业的生产方式越来越复杂。白热化的市 场竞争也导致了生产方式的改变，目前，制造业的生产方式朝着产品种类多、 批次数量少的方向发展，这逐渐发展成当前制造业的主要方式。 时代的发展要求企业转变以往贯行的简单、低效的生产方式，努力寻找能 更加快速发展自身的高效的运作模式，以确保生产安全稳定的进行，从而提高 企业的生产力水平，改善企业自身的经济效益。社会生产由科技发展的水平及 其应用到生产工艺上的程度所决定，由此可见，企业生产过程和社会发展程度 越来越紧密的结合在一起，随着社会的发展，企业在社会经济发展变革的进程 中也面临越来越多的新问题，企业如何应对这样的发展潮流、应对生产工艺不 断更新的现状，从而实现自身的可持续发展，并使经济效益逐步增长从而占领 更多市场，这就需要我们对其作进一步的深入研究。 最早提出计算机集成制造系统( c i m s ：c o m p u t e ri n t e g r a t e dm a n u f a c t u r i n g s y s t e m ) 概念的是约瑟夫、哈林顿博士( j o s e p hh a r r i n g t o n ) 。1 9 7 4 年，约瑟夫、 哈林顿在其博士论文c o m p u t e ri n t e g r a t e dm a n u f a c t u r i n g ) ) 中明确，由诸如计 算机、网络和通信等科技资讯，对制造过程中所有系统进行整合与管理谓之计 算机集成制造系统。运用现代科技，c i m s 可以整合制造工厂内各独立的自动 化系统，使其发挥整体的效益，从而达到对整个制造企业进行整合的目的，以 提高组织和个人的效率。c i m s 需要特别强调的是，为避免形成产业上的自动 化孤岛，制造企业在进行生产时，其各个生产环节必须要紧密相连，形成一个 统一的不可分割的整体。 随着科技的不断进步、社会的日益发展，现代产品生命周期逐渐缩短，更 新的速度越来越快，使其在价格、品质上的竞争日趋激烈，在这种大的社会背 景下，计算机集成制造系统应运而生。计算机集成制造系统的运行，实质上是 加工和处理相关资料的过程，其系统集成化的全局效应相对于其他系统则更为 突出。设备不相容以及协定整合的复杂度太高的问题，在传统的机器制造以及 现代化的c i m s 都是存在的，寻找有效的计算机调度策略可以从一定程度上解 决这一难题，因此，调度问题的研究即有理论研究的意义也有现实需求的必要 性。 近3 0 年来，科技的进步不断影响和改变着社会环境，主要表现为微电子、 光电子及计算机等技术广泛应用于社会的各个领域。当前，制造企业的生产方 式己经发展成为密集信息的柔性自动化生产方式，这种智能自动化的方式是自 动化生产方式发展的必然趋势，它完全可以满足多品种、小批量的市场需求。 通过信息、制造工艺、管理及制造工艺等技术的有机融合，就形成了我们通常 所说的先进制造技术，它实际上是一类综合性的创新技术，具有智能、集成、 柔性、机电一体化等现代化特征。企业要增强自身的竞争力，对市场及用户的 需求变化迅速做出响应，就应该提升自身的反应能力，进而提升企业的响应能 力，逐渐引导企业在制造产品的技术方面树立形象，增强自身优势。 作业车间调度问题( j o bs h o ps c h e d u l i n gp r o b l e m ，j s s p ) 是已被证明的经 典的n p 难问题，作业车间调度也是柔性制造系统( f l e x i b l em a n u f a c t u r e s y s t e m ，f m s ) 中的经典问题。其所求方案的描述是将一组工件放在指定类型的 机器上运行，每个工件都有若干道工序需要操作，最终所需要确定的方案是这 些工件所用机器的分配和工件顺序的先后。目的是优化成本，节约时间等。 调度技术涉及的是资源的优化分配、综合利用的问题，好的调度技术在生 产管理的作用极其巨大。作业车间调度在生产方面的作用主要体现为亮点：一 是使生产效率保证在较高的水平；二是使企业生产能够具有较高的柔性。一个 企业的良好的生产调度策略可以合理分配生产资源，提高生产效率；降低生产 过程中的等待、运输、库存成本，从而提高企业的利润。随着改革开放深入和 经济高速发展，我国的一大批早期企业不能适应新的企业环境，一方面是机器 设备等硬件老化陈旧，处于淘汰的地步；同时另一方面，企业在生产管理调度 方面的管理方法落后，绝大多数的企业仍然采取人工管理、经验管理等落后模 式进行生产调度管理，这种方式在目前越来越复杂的生产环境下大大阻碍了企 业的进一步发展壮大。如何在当前的形势下解决企业面临的各种难题，直接关 系到企业的兴衰成败和生存发展，对企业未来的经营发展和提高企业的经济效 益有至关重要的作用。因此，研究企业的调度问题在企业的生产计划，生产的 管理方法，生产的控制方面具有重要的意义。 随着各种优化算法不断的发展，调度问题的解决也越来越优化。但由于作 业车间调度问题本身是n p 难问题，还没有找到完全有效的解法。这需要研究 人员不断在求解算法上进行创新和改进，因此本文关于多机并行作业车间调度 的研究具有一定的理论意义和现实意义。 1 2 多机并行作业车间调度问题研究现状及存在问题 1 2 1 研究现状 从国内外发展来看，车间调度已经有几十年的历史。早在1 9 5 4 年 s m j o h a s o n 提出了流水车间两台机器下排序问题的优化准则，提出了解决 n 2 f c m a x 和部分特殊的n 3 f c m a x 问题的优化算法，这代表调度理论研究的 开始，在这之后逐渐开始了对作业车间( j s s p ) 的广泛研究。一直到现在车间 调度问题的研究仍是大热点。 2 早期在对车间调度问题的求解方法上主要是如何通过运筹学方法来得到调 度问题的最优解。将调度问题简化为数学规划模型，再用分支定界或动态规划 方法进行求解。【3 0 】【3 1 1 。这类方法基于枚举的思想，但随着研究深入和问题的复 杂性提高，人们发现运筹学方法的致命缺点就是，随着调度问题规模的增加， 所消耗的计算时间及空间都呈指数增长。这种调度问题的n p h a r d 特性也在 1 9 7 6 年由m r g a r e y 等人证明【2 0 1 ，并且w e r n e r 等人与1 9 9 5 年指出，作业车间 调度问题是“最坏的 n p h a r d 问题之一【2 1 1 。 放弃搜索最优解，转向在较短时间内搜索适合的近优解是启发式规则方法 的目标。在面向特定问题时采用特定的经验方法，可以在较短的时间内产生良 好的解决方案。p a nw a l k e r 等人于1 9 7 7 年总结了1 1 3 个启发式调度规贝l j 3 2 1 ，将 其分为简单规则、复合规则和启发式规则。然而启发式规则也有没有普遍适用 性和难以评价结果的缺点。 随着人工智能算法的出现和成熟，人工智能算法一经使用就显示出这类方 法在n p h a r d 问题中的巨大优势。d a v i s 最早把遗传算法运用于车间调度的问 题中来，与1 9 8 5 年发表了把遗传算法成功应用于车间调度问题的论文。 d a v i d e ，g o l d b e g ，y a m a d a ，n a k a n o ，w l l i u e ，f a n g ，k o b a y a s h i 等学者在之后 提出了显著的改进，并解决了一些标准检测的问题，进一步证明遗传算法的有 效性。其他一些具有计算智能的局部搜索法也相继用于车间调度求解之中。如 禁忌搜索算法、模拟退火算法、粒子群算法、蚁群算法等。均在车间调度领域 有很好的效果。 常见的车间调度问题，根据生产的工艺路径要求的区别可以分为流水车间 ( f l o ws h o p ) 、作业车间( j o bs h o p ) 、开放车间( o p e ns h o p ) 几种方式，作 业车间由于其工艺约束的柔性更适应目前柔性化生产的需求，因而越来越多的 人关注柔性车间的调度问题。2 0 0 2 年，b a y k a s o g l ua 提出了一种更符合柔性化 生产的柔性作业车间调度模型【3 】，不仅考虑产品的排序还包括生产路径的选择。 提出了一种启发式的解决方案。多机并行作业车间时柔性作业车间的一种。近 年来，针对车间调度的柔性化特点展开的研究层出不穷。 1 2 2 多机并行作业车间调度存在问题 ( 1 ) 多机并行车间调度中多目标问题 车间作业调度涉及到了产品的交货期和成本等诸多因素，是一个多目标的 决策问题。通常实际的目标可以分为两大类：基于时间的目标和基于成本的目 标。这两类目标并不完全相互独立，其中的许多目标有明显的相关性。有的相 互促进、有的相互矛盾。因此，在实际的车间调度中，难以同时满足多个目标， 必须根据具体情况来确定哪个目标优先或兼顾各个目标确定各目标在总目标中 所占的权重。 3 另外在设计多目标算法时，由于权重本身的主观性难以明确确定，往往要 求要同时考虑若干目标同时优化，因此在多目标算法时通常采用随机权重和保 留非支配解集的策略，这种方法可以避免主观性的影响。但人工智能的搜索算 法在对每个进行搜索的过程中，需要对已有解集进行评价，比如遗传算法中的 自适应交叉迭代概率是和适应度相关的，这里也需要对个体的目标值进行融合。 多目标算法给出的结果是一组解集，最终对于决策者来说，任然需要对解集中 个体进行多属性决策，也就是对个体的各个目标值如何加权的过程。这与一开 始先设定主观权重再用融合后单目标算法求解出的结果有何不同，也是需要研 究的问题。 因此，对于多机并行作业车间调度的多目标特性，如何将多目标合理融合， 以及在算法处理的过程中何时进行加权合适，是对于多机并行作业车间调度问 题求解处理过程中的一个重要的问题。 ( 2 ) 多机并行作业车间调度求解方法选择 众所周知；对于调度问题求解的三种基本方法就是：运筹学方法，启发式 规则和带人工智能的搜索算法。每种方法都有其不可替代的优势和无法弥补缺 陷。运筹学方法能求出精确最优解但对于n p h a r d 问题在大规模时无法在有效 时间内完成：启发式规则简单有效求出近似解但应用有局限性；带人工智能的 搜索算法应用普遍，求解效率较高，但仍然存在1 局部搜索能力、全局搜索能 力和算法求解时间难以同时满足，2 求解质量只有相对优劣，难以精确比较。 可以看出单独的算法缺点突出，寻求2 种方法或者3 种方法结合的算法是 解决这类问题的一个出路。例如，启发式规则与运筹学方法的结合：利用启发 式规则缩小可行解的空间，将问题限制在一个比较小的范围之类，再用运筹学 方法进行求解。人工智能搜索算法与启发式方法的结合：可以结合启发式规则 的编码优化进化效率和缩小搜索空间。对于人工智能搜索算法本身，可以结合 全局搜索算法和局部搜索算法的特点，进行算法的改进。如何选择合适的方法， 算法之间如何结合，这是一项很有意义的研究工作。 1 3 论文研究内容及论文框架 1 3 1 论文主要研究内容 基于目前的研究现状及存在问题，本文的主要内容和结构如下： 第一章为绪论。主要介绍多机并行作业车间调度问题的研究背景及意义。 介绍目前作业车间调度问题的研究现状和存在的问题。 第二章为多机并行作业车间调度问题和模型描述。首先，介绍车间调度及 作业车间调度的概念，在此基础上描述多机并行作业车间调度问题，并对车间 调度的特点和目标做总结；再介绍常见的数学建模和图形建模方法，并对多机 并行作业车间调度问题进行数学建模。 4 第三章介绍求解的混合遗传算法。首先，介绍可用于车间调度求解的常见 方法；然后在总结各种方法优缺点的基础上选择混合遗传算法对问题求解。在 本章对遗传算法用于调度中的改进方式做总结，并对本文所采用的改进混合遗 传算法做详细介绍。 第四章是仿真算例分析。首先确定算法比较的评价标准，再通过若干不同 规模的仿真数据进行结果比较。 第五章为结论和展望。介绍本文的主要结论，和研究中仍然存在或需要解 决的问题进行展望，为后续研究指明方向。 1 3 2 论文框架 本文基本研究框架如下图所示： 背景及意义 研究现状和存在问题 ：j 【二 r - ： - 问题描述 数学建模 i ttt ；tt 车作业多机并 一 建模建模 间车间行作业 方法方法 调调度车问调 介绍 选择 度度 i ： ! “ 一- - - 解决车间调度问 遗传算法多机并行作业车间 题常见方法介绍 流程及改调度的改进混合遗 进方法传算法 确定解决方法 ( g a ) - i 二- 二i - 二玉二二- = ：= - - 二= j 算法 评价 i 算法对比分析 标准 图1 1 论文框架图 第二章多机并行作业车间调度问题描述和建模 2 1 作业车间调度问题描述 2 1 1 作业车间调度问题概念 2 1 1 1 车间调度问题的概念 车间调度问题简单地说就是对于有限的资源进行分配和在此基础上对产品 生产方式进行排序，从而在满足性能指标的约束并使时间和一些指定的指标尽 量优化。一般可以描述为：对于像产品制造业等可以分解的工作，在尽量满足 交货期、工艺路径、资源限制等约束条件的基础上，探讨如何安排生产；主要 是确定工件的资源分配、机器路径选择、工件加工顺序几个方面，从而降低生 产成本和优化生产时间。典型的车间调度问题需要包括一个要完成的工件集， 和工序集来确定工件按照何种工艺流程进行加工，以及机器参数集来确定机器 加工时间、所占用资源量等。调度的目标是将作业合理地安排到各机床，并合 理安排作业的加工次序和加工开始时间，使约束条件得到满足，同时优化性能 指标。【2 3 】 在理论研究中，车间调度问题又被称为资源分配或排序问题，统称为组合 优化问题。在理论表述时可以用数学规划的方法来表达。该数学模型在建立时 可以表述为一个或多个目标函数，多个不等式或等式约束条件。 车间调度的内容包括：分配决策，即工件在加工设备上的分配；路径决策， 即工件的加工顺序；以及时间决策，即工件在各工序的加工时间。 车间调度的最终目标是对车间的资源进行优化配置，使企业获得最大的综 合经济效益。车间调度的性能指标可以是加工成本最低、库存费用最少、生产 周期短、加工切换最少、生产资源利用率最高、三废最少、准时交货等。在传 统调度中，一般以最小平均流通时间、最短制造时间、满足交货期为调度目标， 而实际生产中由于提前完成的产品必须保存到交货期，而拖期产品必须交付违 约金，因此，在实际调度中更加重视提前或者拖期惩罚。 影响车间调度的因素有很多，正常情况下，如：产品的交货期、完成期、产 品的加工顺序、加工设备的生产能力和原料的可用性、批量大小、成本限制等， 这些都是车间调度的约束条件。有些约束条件是必须要满足的，比如交货期， 设备的生产能力等，而有些约束条件只要达到满意值即可，如生产成本等，这 些约束条件在进行调度时可以作为确定因素，而生产任务的变化、加工原料供 应的变化、设备故障等非正常情况，是不可预见的，可以作为不确定性因素来 加以考虑。在实际制造系统中，还要考虑人员、工装、物料搬运系统等的调度 问题。 2 1 1 2 作业车间调度问题概念 6 车间调度问题根据加工系统的复杂程度来划分可分为单机调度、多台并行 机调度、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 ) 调度问题中每个工件有特定的工艺路径，每道 工序在特定的机器上即兴，不同工件的工序间没有关系。作业车间调度是最具 普遍性的调度类型，现代车间调度中通常都是j o bs h o p 调度。 作业车间调度问题的研究的另外一方面增加企业生产的柔性化，它集中于 柔性制造系统( f m s ) 。柔性制造系统是一种能适应加工对象变化的自动化机械 制造系统。基础是数控机床或者加工中心，综合了信息控制系统、物料储运系 统以及数字控制加工设备。生产的柔性体现在设备使用和设备安排两个方面， 设备使用的柔性指可用于多个零件的多个工序的加工；设备安排的柔性是指工 件的设备加工路径不是固定和预先确定的，它有可选路径，可通过将若干设备 组作为一条或者多条生产线加工一种工件，使得该工件生产率最大。 2 1 2 作业车间调度问题的特点 实际生产中的作业车间调度的特点主要有以下几点： 1 复杂性：作业车间调度问题是一个综合的生产管理系统，包括运输系统、 存贮系统、加工系统、装载系统等各个部门。这些系统之间相互影响、相互作 用，共同影响了调度系统。调度中的每个产品又要考虑它的生产时间、准备时 间、交货期，需要决定产品的生产路径、生产顺序等，因而相当复杂。调度问 题是在等式或不等式约束下求性能指标的优化，是一个n p 难问题。即随着规 模的逐渐增大，求解最优解的计算量和计算时间呈指数增长，因此常规的数学 运筹学方法很难对大规模问题进行有效求解。 2 约束性：作业车间调度问题需要满足大量的约束条件。如工艺路径约束、 生产能力约束、库存能力约束、资源使用约束等。另外对于不同的管理人员可 能要求一些人为因素的约束，如各机器上的利用水平要求平衡等。 3 多目标性：作业车间调度问题是多目标问题。涉及的目标可以分为基于 时间的目标和基于成本的目标两大类，其中有上百种小的分类。这些目标相互 之间是可能有冲突的，因此作业车间调度的研究需要进行多目标决策。 4 动态随机性：作业车间调度中有很多随机和不确定性的影响因素，例如 紧急加单导致的加工任务改变，机器临时故障导致的生产排序更新等生。正是 由于作业车间调度有以上一些情况，所以在实际的调度工作中我们不仅需要考 虑多目标的平衡还要兼顾考虑生产调度的滚动计划，加强调度的灵活性来应对 随机事件的扰动。 7 2 1 3 作业车间调度的目标 作业车间调度是一个多目标的决策问题。m e l i o r 在1 9 9 6 年对调度问题的目 标做了综述，提出了2 7 个调度中所考虑目标，总结一下可以分为时间和成本两 类目标： 1 基于时间因素的目标： 作业车间调度中的时间目标可以分为基于完工时间的目标和基于交货期的 目标，是因为要在生产中快速的反应需求和对于客户制定交货期尽量满足。对 于基于完工时间的目标包括：最小化最大完工时间、最小化流经时间和最小化 等待时间等。这个目标表示为在尽量短的时间内完成任务，并有最充分的利用 率。对于基于交货期的目标是指完工时间尽量与交货期一致。过早的完工则会 造成大量的库存成本，而完工时间过晚则不能满足客户需求、有支付违约金或 市场份额丢失等危险。因而过早或过晚的完工也是不合理的。 2 基于成本因素的目标 在成本上，应该考虑降低资金使用和提高资源利用率。减少资金使用的目 标包括最小化在制品的数量以及最小化机器使用费用等。提高资源利用率的目 标包括机器利用率的总体最大化以及各个设备利用率要相对均衡等，避免出现 “瓶颈。 这两类目标并不完全相互独立，其中的许多目标有明显的相关性。有的相 互促进、有的相互矛盾。因此，在实际的车间调度中，难以同时满足多个目标， 必须根据具体情况来确定哪个目标优先或兼顾各个目标确定各目标在总目标中 所占的权重。 2 2 多机并行作业车间调度问题描述 这里所考虑的多机并行作业车间调度问题研究n 个工件，每个工件都有m 个工序，每个工件的工序顺序不完全相同，每道工序有可供选择的若干机器， 每台机器只能加工确定的工序，每个工件在不同机器上的加工时间不同，且不 同工件之间在不同机器上有不同的换模具时间，要求确定各机器上的工件分配 和加工顺序，从而使之满足目标要求。 该问题中的约束条件为： 1 按照工件的工艺要求，其工序有着顺序约束。 2 同一时刻，一台机器上只能加工一个工件，且一个工件某一时刻只能在- 一台机器上加工。加工不能中断。 3 不同工件之间没有优先关系 需要事先确定的信息如下：工件集j ，机器集m ，工序集o ，加工时间矩 阵t ，工件规定交货时间矩阵d ，提前拖期惩罚矩阵p ，工件准备时间矩阵s 。 本文所选择的目标为：1 ) 最小化最大完工时间；2 ) 最小化提前拖期惩罚 2 3 多机并行作业车间调度问题的建模 2 3 1 车间调度问题的建模方法 定量计算的方法由于其客观性和准确性在自然科学和工程技术等许多领域 中的应用愈来愈受重视。系统分析的方法已普遍适用。而模型是使用这些定量 方法开展工作的有效工具，这些定量方法开展的前提和基础就是问题的模型化 描述。作业车间调度问题的建模方法主要有以下两大类： ( 1 ) 数学分析的建模方法： 数学分析模型是将所要研究的系统的各个变量之间的关系使用数学关系式 的形式表达出来。数学分析模型中大多是描述性的模型，即在一组约束条件下 预测一个的可能数值。而另一类预测模型需要寻找或分辨出最符合目标值的最 优后果，即求出最优解或最优解集，在作业车间调度优化问题模型中就是要寻 找满足约束条件和目标函数的最优的调度方案。寻求最优解的过程常称优化， 这类数学模型称为优化模型。使用数学分析建模方法的基本优化模型如下所示： 9 s j & c 工，= 三) 包 c t i ， 遵循约束条件& ( 驯。每一个常数b i ，表示相应的约束条件函数& 【工) 必须满足 l o 2 3 2 多机并行作业车间调度的优化模型 2 3 2 1 目标函数： 本文中，综合考虑时间以及成本两个影响因素 1 ) 使最后完工工件的完工时间最小，即最小化的最大完工时间( m a k e s p a n ) m i n z l = m a x c 岫) 2 ) 尽量使工件的完工时间贴近交货期， 最小，拖期完工工件产生的惩罚成本最小。 罚系数以后以加权形式融合 m i n z 2 = ( c i d i ) p i l 口+ ( c i - d i ) p i 2 】 i = l 即使提前完工工件产生的库存成本 这两个以成本为目标的因素加上惩 p i l p i 2 分别表示提前和拖期的惩罚，口和是0 ，1 整数，若完工时间少于交货期则 口= 1 = 0 ，若完工时间大于交货期则相反。 2 3 2 2 约束条件： ， 生产车间作业调度问题还需满足以下约束条件： 1 按照工件的工艺要求，其工序有着顺序约束。 2 同一时刻，一台机器上只能加工一个工件，且一个工件某一时刻只能在 一台机器上加工。加工不能中断。 3 不同工件之间没有优先关系 根据作业车间调度模型的特点， b i j m c i ( j - 1 ) m b 日m c ( i 1 ) j m c i j m = b 细+ 毛。+ s i - i 2 m 定义如下约束 ( 3 1 ) ( 3 2 ) ( 3 3 ) x 诩，= i l (i工件的j工序在姚器上加工)(34，l x 独= 0 ( i 工件的j 工序不在姚器上加- r ) p 4 ) x i j l 【= l ( i = l 2 n ；j = 1 2m ) ( 3 5 ) f 1 2 仁 x i l j x i z j ( i l i s ) ( 3 6 ) ( 3 7 ) b i j m 表示i 产品的j 工序在m 机器上的开始时间，c j | j m 表示i 产品的j 工序 在m 机器上的结束时间，民m 表示i 产品的j 工序在m 机器上的加工时间。d i 表 示i 产品的交货期。s i , ；z 表示两个产品在m 机器上的换模具时间， 3 1 表示某 工序上后一工件开始时间大于前一工件的完工时间，3 2 表示某工件的后一工 序的开始时间大于前工序的完工时间。3 5 表示每个工件的一道工序只能在 l l 一个机器上加工 示第1 位生产， 最终需要确 x 。表示工件在工x “衣不上仟征上 2 4 本章小结 作业车间调 车间调度问题的 车间调度问题的 法也一直是学术 等方法运用普遍 1 2 第三章求解多机并行作业车间调度问题的改进混合遗传算法 3 1 作业车间调度问题的研究方法 ( 1 ) 基于运筹学( o r ) 的方法 运筹学方法基于枚举的思想，先用数学建模方法对作业车间调度问题进行 描述，再采用运筹学中的分支定界法( 分支定价法) 或动态规划方法进行求解 【3 0 】【3 1 1 。这类方法可以准确找出问题的最优方案，但由于生产调度本身是一种 n p 难的组合优化问题，随着问题规模的扩大，调度方案数会指数式增长，用运 筹学方法难以在有限时间内得到最优解。而且运筹学计算本身的局限性需要在 研究问题时进行理想化的假设，这对于解决实际问题也是有差距的。因此运筹 学方法通常用于解决小规模的调度问题或作为理论研究的方法来使用。 ( 2 ) 基于启发式规则的方法 启发式搜索方法最初是做为人工智能中问题求解程序的搜索器而开发出来 的一种方法，通过外部信息来对搜索过程进行优化。这种过程通常是直接系统 化的构造解或根据一定模式查找解。p a nw a l k e r 等人在1 9 7 7 年对于车间调度问 题总结了1 1 3 个启发式的调度规则【3 2 】，包括简单规则、复杂规则和组合规则。 启发式搜索方法利用了面向特定问题的特定经验和方法，因而能够在短时间内 快速解决问题，生成良好的调度方案但不一定是最优方案。启发式规则的明显 的缺点是难以对求得结果质量有效评估，且需要探索如何提高搜索效率并减少 内存使用以解决规模较大的问题。启发式规则面向特定的问题不具有普遍意义。 ( 3 ) 控制理论方法 由于车间调度问题的动态随机性特点，为了加强对不确定性的控制和对调 度计划稳定性的要求，会采用控制理论的方法来加强对系统稳定性的管理。调 度模型要求尽可能的减少机器的临时修理、需求订单临时变动、价格成本临时 变化等其他随机性事件对调度过程的影响。g e r s h w i n 等人从控制理论的角度出 发【3 3 1 ，较全面地阐述了控制理论调度方法的应用与进展。控制理论方法目前还 没有形成一套有效的调度模型表达、分析、设计技术，比较适合于定量地定义 基本问题。控制理论的模型描述能力有限，求解最优解的时间是随着问题规模 增加而呈现指数规律增加，应用范围有限。 ( 4 ) 基于人工智能( a i ) 的方法 人工智能的方法是建立在假设模型和已有的知识基础上，通过模拟方法为 决策提供支持，从而根据车间调度中的不同情况做出决策行为。近年来，人工 智能调度系统的研究取得了很大的进展，主要成果有智能调度专家系统、约束 规划及基于多代理( m u l t i a g e n t ) 技术的合作求解方法等。i s i s 3 4 】是第一个用 于解决j o b s h o p 调度问题的专家系统。人工智能调度系统很大程度上取决于对 已有知识或方法的总结，其知识总结和问题求解能力是有限的，在简单基础的 1 3 调度问题上效果突出。但对于大规模的复杂调度问题，收集人的经验以及认识 过程的建模的局限性表现明显，难以取得明显效果。人工智能的方法可以解决 普通的调度问题，但解决问题的能力收人为因素影响解，难以进行大规模问题 普及应由。 ( 5 ) 基于离散事件动态系统的解析模型方法 离散事件动态系统d e d s 的解析模型方法是基于离散事件系统的研究方 法，作业车间制造系统就是一类典型的离散作业系统。常见的离散系统研究方 法有极大代数法、动态规划法、p e t r i 网等。p e t r i 网具有动态、直观和并发等优 点使其在作业车间调度应用广泛，其中基于p e t r i 网的扩展模型还能够准确快速 地反映制造系统实时调度的离散性与随机性。 ( 6 ) 基于仿真的方法 建立仿真模型搜集数据，从而对实际系统的性能、状态等方面进行分析， 在此基础选择适当的控制方法来解决调度问题。仿真方法的优点在于测试不同 调度方案的性能时不受外界时空因素的影响，获得较优的调度方案，并且能够 对用分析方法去解决的问题寻求可行解。同时仿真实验本身需要仿真模型、仿 真数据和仿真方法共同作用，对仿真建模的要求有高依赖性，同时也依赖程序 员的判断能力。而且仿真的方法其难以总结一般性规律，缺乏理论基础，对于 调度问题的一般性推广缺少作用。 ( 7 ) 基于模糊数学理论的方法 作业车间调度问题的加工次数、约束数量、加工时间、资源占用等都有不 确定性的特点。模糊集理论用于车间调度问题建模和求解是非常有效的。模糊 系统可以运用高级知识进行表达，直接表示逻辑，逻辑功能强。同时由于模糊 系统本身不能够进行知识获取。依赖于进行指导的专家的知识水平，且规则确 定困难，研发周期长。 ( 8 ) 拉格朗日松弛法 拉氏松弛法近年来成为解决复杂生产调度系统问题理论研究的重要方法。 其能够对复杂的规划问题提供近优解，并且可以对近优解的有效性进行评估， 量化其与最优解的距离。文献【3 7 】在单机调度与多台并行机调度问题上使用拉格 朗日松弛法进行求解。但拉氏松弛法搜索效率低，需要进一步深入研究如何构 造可行调度。 ( 9 ) 神经网络优化法 神经网络优化算法应用于生产调度问题有三条途径：一是利用神经网络来 描述调度约束和调度策略，从而时间对生产过程中的可行或次优调度：二是神 经网络算法本身的并行计算能力，可以对调度的n p 完全问题有效解决；三是 神经网络的学习能力，可以从过程中学习调度知识，有效的优化调度方案。王 万良【3 8 】等人对作业车间调度问题提出一种基于改进的h o p f i e l d 神经网络方法 1 4 进行作业车间调度求解，通过对换位矩阵表示方法进行修改得到了较好的效果； sy a n g i 3 9 1 等人将神经网络方法和启发式搜索方法相结合，用混合神经网络方法 解决作业车间调度问题。人工神经网络在表达符号知识以及其他知识时较困难， 自学习效率低，计算搜索速度较慢，通常与其他方法结合使用，需要进一步改 进。 ( 1 0 ) 具有计算智能的局域搜索算法 高级局域搜索算法具有普遍适用性、且算法复杂性低容易学习，在近些年 得到广泛运用。具有计算智能的居于搜索算法主要有以下几类：一、禁忌搜索 算法( t a b us e a r c h ) ：禁忌搜索算法是一种通过邻域搜索解决复杂的组合优化问 题以获取最优解的方法，g l o v e r 在文献【4 0 】中阐述了它的基本原理。由于创建和 确定中诸多的构造因素需要一定的技术水平，在车间调度问题中的应用还很少。 二、遗传算法( g e n e t i ca l g o r i t h m ) ：遗传算法通过模拟生物进化过程中的选择和 遗传过程设计的算法。遗传算法通过对调度方案进行编码，将调度方案用染色 体形式表