两机无等待流水车间调度问题与仿真说明书

本科毕业设计论文题 目：两机无等待流水车间调度问题与仿真专业名称 机械设计制造及其自动化 学生姓名 指导教师 毕业时间 2014 年 6月 毕业 任务书一、题目两机无等待流水车间的调度与仿真二、指导思想和目的要求毕业设计（论文）是培养学生自学能力、综合应用能力、独立工作能力的重要教学实践环节。在毕业设计中，应独立承担一部分比较完整的工程技术设计任务。要求学生发挥主观能动性，积极性和创造性，在毕业设计中着重培养独立工作能力和分析解决问题的能力，严谨踏实的工作作风，理论联系实际，以严谨认真的科学态度，进行有创造性的工作，认真、按时完成任务。针对两机无等待流水车间调度问题, 提出目标函数最大完工时间最小化的快速算法, 并给出算法的复杂度.分析两机无等待流水车间调度问题的排列排序性质,证明了两机无等待流水车间调度问题的可行解只存在于排列排序中,排列排序的最优解一定是两机无等待流水车间调度问题的最优解.最后研究了同时包含普通工件和无等待工件的两机流水车间调度问题的复杂性,为进一步研究两机无等待流水车间调度问题提供了理论依据。三、进度和要求第一阶段：（共计 5周）第一周及第二周，翻译并完成教师指定的英文文献翻译； 第三周及第五周，对所研究课题有个全面的了解。第二阶段：（共计 5周）完成方案的提出，学习和用已知的方案方法进行实际问题的解决方案的提出和仿真。第三阶段：（共计 5周）撰写论文及评阅。四、主要参考书及参考资料设计论文1 S.M.Johnson.optimal Two-and Three-Stage Production Scheduling with Set-up Time IncludedJ. Naval Research Logistics Quarterly.1954, 1:61-682 Story A.E, Wagner H.M.Computational Experience whit Integer Programming for Job-shop Schdeling.Industrial Scheduling,Chap.14,Prentice-Hall,19633 Gavett J.W.Three Heuristic Rules for Sequencing Jobs to a Single Production FacilityJ. Mgmt.Sci.1965,11:B166-1764 S.Panwalker,Wafik Iskander.A Survey of SchedulingJ.Ops.Res.1977, 25(1):45-615 Stephen,C.Graves.A Review of Production SchedulingJ.Ops.res.1981,29（4）:646-6756 M.S.Fox.ISIS:A Retrospective Intelligent Scheduling.Intelligent Scheduling,Kaufmann, ed:Michael B.Morgan,1994:3-287 B.Giffler,GL.Thompson.Algorithms for Solving Production Scheduling ProblemsJ.Ops Res.1960,8:487-5038 董海，梁迪设施规划与物流分析北京：机械工业出版社20059 Baker K R.A Comparative Study of Flow Shop Algonithms J.Ops Res.1975(23）:62-7310 王伟玲，马正元，王玉生生产调度问题研究的动态与趋势J管理技术，2005 年第 5期11 郑璐，顾鑫生，不确定条件下的零等待 Flow Shop生产调度问题J华东理工大学学报 2004，30（2）：188-19412 S.Panwalker, Wafik Iskander.A Survey of SchedulingJ.Ops.Res.1977, 25（1）:45-61.13 谢源，谢剑英，郑小龙混合有限月苏下带模糊交货期的单机调度问题的研究J信息与控制 2005，34（3）：369-372 14 Glover F. Future paths for integer programming and links to artificial intelligenceJ. Computer and Opreations. Research. 1986, 13:533-549.15 卢冰原，陈华平，顾春生等，模糊环境下的柔性工作车间调度模型的研究J运筹与管理2004，1316 李福明，朱云龙，尹朝万等.基于遗传算法的模糊调度研究J.信息与控制2004，33（6）：703-70817 吴仪，刘民等.JSSP 基本约束特点分析及调度算法J.清华大学学报(自然科学版)2004，44(10)：18 Kinkpatric S, Gelatt CD, Vecchi M P.Operational by simulated annealingJ.Science.1983, 220:671-680.19 吴梅，陆金桂.遗传算法的研究进展综述J机床与液压2008，36(3)20 孙卓明，余彬遗传算法计算机时代2004 年，第 1期21 陈国良等遗传算法及应用北京：人民邮电出版社，1996学生 指导教师 系主任 I摘 要流水车间(Flow Shop)调度问题无论是在工厂经营管理还是在产品制造中都具有广泛的应用，因此对流水车间调度问题进行研究具有重大的理论意义和实际意义。本文首先对车间调度问题国内外研究现状和发展趋势进行了系统的阐述。其次，对遗传算法的基本理论进行了详细的论述。然后对 Flow Shop调度问题建立数学模型。再次，在掌握了遗传算法的基础之上给出了基于遗传算法求解Flow Shop调度问题的编码方案，遗传算子的设计。然后基于遗传算法对调度问题进行了实例分析。最后对上述两种调度的结果进行了分析，结果表明本文提出的方法是有效可行的。关键词：生产调度，流水车间调度，遗传算法。IIABSTRACTFlow Shop (Flow Shop) scheduling problem in both factory management and has wide application in the product manufacturing, so the study of Flow Shop scheduling problem is of great theoretical significance and practical significance.This article first to the workshop scheduling problem research status and development trend at home and abroad systematically in this paper.Secondly, the basic theory of genetic algorithm in detail in this paper.Then the Flow Shop scheduling problem to establish mathematical model.Again, in the mastery of the genetic algorithm based on genetic algorithm is given based on the Flow Shop scheduling problem of coding scheme, the design of genetic operators.Then based on the genetic algorithm for scheduling problems on the instance analysis.Finally, the results of the two kinds of scheduling are analyzed, the results show that the proposed method is effective and feasible.Key words: production scheduling;Flow shop scheduling;Genetic algorithm;III目 录摘 要 .IABSTRACT.II目 录 .III第一章 绪 论 .11.1 引 言 .11.2 国内外车间调度问题的研究现状和存在的问题 .11.2.1 国内外车间调度问题的研究现状 .11.2.2 研究中存在的问题 .21.3 研究意义与目的 .31.4 本文的工作 .4第二章 车间调度问题 .52.1. 车间调度问题的描述 .52.2 车间调度问题的特点 .62.3 车间调度问题的分类 .62.4 Job Shop 与 Flow shop 比较 .72.5 调度问题的研究方法 .82.6 两机无等待流水车间调度 .132.6.1生产周期的计算 .132.6.2生产周期的快速算法 .14第三章 遗传算法 .163.1 遗传算法的形成与发展 .163.2 遗传算法的基本思想 .173.3 遗传算法的特点 .173.4 遗传算法的过程和流程 .193.5 求解调度问题的遗传算法 .223.5.1 遗传算法的设计步骤 .223.5.2 编码方式 .22IV3.5.3 适配值函数 .243.5.4 遗传算子的设计 .243.5.5 编码参数 .263.5.6 遗传算子 .263.5.7 算法的终止条件 .26第四章 两机无等待流水车间调度问题仿真 .274.1 流水车间调度问题的描述与数学模型 .274.2 基于 Johnson法则的两机无等待流水车间调度问题仿真 .284.3 遗传算法的设计 .314.3.1 编 码方案 .314.3.2 群体的确定 .314.3.3 适应度函数 .314.3.4 遗传算子的设计 .314.4 基于遗传算法的两机无等待流水车间调度问题仿真 .324.5 结果分析 .32第五章 全文总结 .33参考文献 .34致 谢 .36毕业设计小结 .371第一章 绪 论1.1 引 言伴随着用户对产品需求的快速变化，以及市场竞争的日趋激烈，现代制造企业需要进行多品种、小批量生产，这种生产方式使生产计划、组织和控制变得更加复杂。另外，要求企业对生产过程中所出现的各种信息进行及时反馈和处理，因此，生产调度问题作为生产管理系统的核心内容和关键问题，其研究具有重要的理论和实用价值。企业要进行改革，结合企业的现状，研究改进遗传算法在车间调度的应用，从而合理分配企业资源、提高劳动效率。研究改进遗传算法在车间调度的应用，从而合理分配企业资源、提高劳动效率。1.2 国内外车间调度问题的研究现状和存在的问题1.2.1 国内外车间调度问题的研究现状调度问题的研究始于 20世纪 50年代，S.M.Johnson 提出了解决n/2/F/Cmax和部分特殊的 n/3/F/Cmax问题的算法，这是调度理论的开始：直至五十年代末期，许多研究成果主要是针对规模较小的单机和简单的流水车间的问题，提出了解析优化方法，许多研究成果主要是针对规模较小的单机和简单的流水车间问题，提出了解析优化方法，研究范围较窄，但是这些研究却成为经典调度理论的基石。六十年代，多是利用混合或纯整数规划和分支定界法解决一些有代表性的问题，如 Story的研究。同时也有人开始尝试用启发式算法研究此问题，如Gavett提出的方法。六十年代末期，经典调度理论体系初步成型。七十年代，人们开始了算法复杂性的研究，多数调度问题被证明属于 NP完全问题或 NP一难问题，难以找到多项式算法，因此开始关注启发式算法。Panwalkar 总结和归纳出了 113条调度规则，并对其进行分类。七十年代末期，经典调度理论趋向成熟。八十年代初期，Stephen 等从三个方面对调度进行了从新考察，对未来发展做了分析和预测，认为理论与实际的结合将会成为研究热点。这个富有挑战2性的课题吸引了机械、计算机、管理等诸多领域的学者，许多跨学科的方法被应用到研究中。其中最引人注目的就是以 Carnegie-Mellon大学的 M.Fox为代表的学者们开展的基于约束传播的 ISIS研究，它标志了人工智能开始真正应用与调度问题。八十年代后期，Giffler 等人总结了生产调度理论和实际方面的最新研究进展，从七个方面论述了生产调度的技术和方法，认为生产调度无论在理论还是实践上都已突破了传统界限。九十年代至今，各种方法在生产调度问题的研究中得到了充分的发挥，同时新的研究手段层出不穷。 而 Davis是最早把 GA(GeneticAlgorithm，遗传算法)应用于车间调度问题的学者之一，他在使用 GA求解车间调度的研究中取得了近似最优解。1985 年，Davis 发表了关于把 GA成功应用于车间调度问题的论文，充分证明了 GA在解决车间调度问题中的可行性。此后，很多学者就给予遗传算法的车间调度方面做了大量研究，发表了大量卓有成效的论文，对车间调度这类 NP问题的解决提出了具体方案。这些论文中提出了一些具有突破性的新方法，改进并完善了传统 GA车间调度中的应用方法，同时通过在解决一些著名的标准检测问题(Ben 和 nark)的过程中取得了最优(或接近最优)解，进一步证明了遗传算法在解决 NP问题方面的有效性。国内对车间调度的研究起步比较晚，始于 90年代。很多企业由于技术上的制约，基本上是靠调度人员的经验进行车间作业分配和调度。随着遗传算法在车间调度方面的应用热潮，在这方面也产生了大量的研究成果，不过，研究工作主要集中在清华大学等等 CIMS国家重点实验室，但离形成系统的理论和开发出成熟的软件系统还有很长一段距离，因此还在投入大量的人力和物力进行该方面的研究，特别是在开展对车间作业作业调度算法的研究方面，目前尚处在实验研究阶段。车间调度问题的高度复杂性和现有计算机条件的局限性决定了不可能一开始就考虑到实际调度问题中的所有因素，因此，实际研究通常是对车间系统进行简化和抽象来解决实际问题。正是在这些现有的理论成果上不断加上约束条件，使得研究问题近似于实际问题。总而言之，随着各种特殊调度问题的攻克和新方法、新设备的出现，车间调度研究正向动态、敏捷、多资源、智能化的方向发展。31.2.2 研究中存在的问题由于在实际生产过程中会出现诸多不确定因素，而且调度问题己经被证明NP难题，因此寻找具有多项式复杂性的最优算法几乎是不可能的。从目前文献的研究来看，对于资源分配也没有提出一个切实可行的解决方案，往往都是从某一方面入手，在若干假设的基础上，得出一种理论上的可行解。各种启发式方法、诸如基于规则的算法等，由于能在合理的时间内产生比较满意的调度，因此广泛应用于实际调度中，但其往往对所得到的调度解的次优性不能进行评估。因此，有必要探索更好的近似最优调度算法，可以考虑通过增加合理的计算时间来提高解的次优性。各种基于统计优化的方法，诸如模拟退火法、遗传算法等，提供了一种解决调度优化问题的新途径，但与别的优化算法类似，也存在着一定程度的枚举、一般来说收敛到最优解较慢，对于判断解的最优性也很困难，在这方面也需要做进一步的研究。1.3 研究意义与目的有史以来，有限资源的合理配置和优化利用问题始终是人类社会所面临的最基本经济问题，这个问题贯穿于社会生活的各个方面。从一个国家、社会的宏观经济运行到具体企业的微观经济活动，都要受资源条件的限制。对企业来说，能否对现有资源进行合理配置和充分利用将直接影响到产品的制造成本，进而成为影响企业效益的重要因素。企业资源的合理配置和优化利用很大程度上体现在车间一层的生产活动中，所以加强车间层的生产计划与控制一直在企业生产经营活动中占有十分重要的地位。车间生产调度是制造系统生产管理的核心，是生产管理和控制系统实现管理技术、运筹技术、优化技术和自动化技术发展的核心。及时准确的生产调度对生产系统的高效运行有着重要的影响。生产管理任务能否顺利的实施与完成，最终要靠合理的生产调度来保证有效。实用的调度方法和优化技术的研究与应用己成为先进制造技术实践的基础。因此，研究生产调度问题，不仅具有较大的理论意义，而且具有相当大的实用价值。一方面，生产调度问题的研究不仅可以推动相关算法的研究，如遗传算法、神经网络、人工智能等，而且还能在此基础上提出新的算法，这为其他领域类似问题的解决提供了条件和手段；另一方面，一个好的生产调度方案不仅可以降低生产成本，而且可以提高企业产品的准时交货能力，从而增强企业的4竞争力。随着科学技术的发展，制造行业的生产规模变得越来越大，产品越来越多样化，车间生产情况的复杂性也越来越高。同时，由于加工系统的复杂性和多样性，目前还没有一种通用的、全面的方法解决各种生产方式的优化调度问题。制造企业迫切希望能有一个结合其自身特点的实用而有效的调度支持系统，这就需要根据企业的实际状况和生产变化，从以获得工程满意解的实际需求出发，选取调度目标，应用能满足要求的快速有效的优化算法，满足企业的实际需求，实现优化调度。1.4 本文的工作第一章 绪论，从课题的研究背景到车间调度的国内外的研究现状再到车间调度存在的问题及解决途径来引出遗传算法对车间调度问题研究的重要性。描述了车间调度问题。进而描述了关于车间调度的较常见的几种研究方法及它们的应用领域。第二章 车间调度问题综述，先介绍车间调度问题其中包括车间调度问题的描述、特点、分类、job shop 与 flow shop 比较然后追寻调度问题研究方法(数学规划法、近似算法、智能搜索算法、模拟退火方法、Multi-agent 方法、模糊逻辑、蚂蚁调度算法、神经元算法)，从而找到一些解决这些问题的办法。第三章 遗传算法，先介绍遗传算法的形成与发展，然后再介绍遗传算法的基本思想和特点，阐述一下遗传算法的过程和流程，最后求解调度问题的遗传算法其中包括遗传算法的设计步骤、编码方式适配值函数、遗传算子的设计、编码参数、遗传算子和算法的终止条件。第四章 基于遗传算法的流水车间调度问题，首先介绍流水车间的背景，然后对流水车间调度问题进行描述与建立数学模型，进行遗传算法的设计其中包括编码方案、群体确定、适应度函数、遗传算子的设计，并且进行了仿真。5第二章 车间调度问题2.1. 车间调度问题的描述生产调度通常是生产过程的作业计划， 例如某机器上工件的加工顺序，以及要加工点的工件如何划分批次。从本质上分，调度问题可以为开环调度和闭环调度。所谓开环调度是指研究工件加工的顺序，所有的客户订购的产品，在机器上排序生产，不考虑其他的因素，闭环调度是指，除了考虑工件的加工顺序之外，还要考虑产品批次的大小等。显然闭环调度的复杂性远远大于开环调度的复杂性，目前对闭环调度的处理通常使用近似方法，首先确定批量大小，然后再确定加工顺序。生产调度的问题基本上可以概述为：对于某一项可分解生产任务，在特定的约束条件下，分派生产所需要的资源，安排子任务的生产时间，并对子任务进行排序，目标是产品的最短的制造时间，或者最低产品成本。其中生产所需要的资源主要包括：人力资源、资金、生产原料、生产设备等，评价目标好的的指标一般有：产品的生产周期短，总成本低和生产设备利用率低等。生产调度的形式可以描述为：n 个工件，m 台机器加工，每一个工件需要在m台中的一台或者多台加工，假设第 i个工件 ，在第 j台机上加工ni1加工时间为 Pij，加工操作位 Oij没一个工件的准备时间为 Rij，工件j1的交货期为 Dij，交货期是指必须在规定的时间内交货，每一个工件有相应的工艺流程，工件按照工艺的约束在机器上按顺序加工。所谓调度可以看做是，在一定的约束条件下工件如何分配到机器上加工，本质上来说调度就是将工件在机器上排序，其要符合以下两点要求：1.符合产品工艺上的约束（可行调度） ；2.对应的执行的目标调度是最优的；生产调度问题是一类复杂的问题，研究难度非常大，给学者的研究带来了6不小的困难，当前生产调度的研究还有很多问题没有解决，很多实际的生产调度还停留在理论层次，大部分生产调度的算法研究只做了一些简单的假设，过于简单，与实际的生产差距较大。目前很多企业的调度还是靠人工完成，耗费了大量的人力物力，不利于企业成本的控制。2.2 车间调度问题的特点车间调度的基本特点是：建模的复杂性，计算的复杂性，动态的随机性，多约束性，多目标性。1.复杂性：车间中工件、机器、缓存和搬运系统之间相互影响、相互作用。每个工件要考虑它的加工时间、安装时间和操作顺序等因素，因而相当复杂。调度问题是在等式或不等式约束下求指标的优化，在计算量上往往是具有 NP特性，随着问题规模的增大，其计算量急剧增加，使得一些常规的方法无能为力，对于这一点已经证明。2.随机性：在实际的作业车间调度系统中存在很多随机的和不确定的因素，环境是不断变化的，在运行过程中会遇到多种随机干扰，比如工件到达时间的不确定性、作业的加工时间也有一定的随机性，而且生产系统中常出现一些突发偶然事件，如设备的损坏、修复、作业交货期的改变等，故作业车间调度过程是一个动态的随机过程。3.多约束性：车间调度问题中资源的数量、缓存的容量、工件加工时间以及工件的操作顺序等都是约束。此外还有一些人为的因素，如要求各机器上的负荷要平衡等。4.多目标性：实际的车间调度问题是多目标的，而且这些目标之间往往是发生冲突的。调度目标分为三类：基于作业交货期的目标、基于作业完成时间的目标和基于生产成本的目标。2.3 车间调度问题的分类车间调度问题的分类，根据研究的侧重点不同有多种分类方式。1按照资源约束种类和数量划分：(1) 单资源车间调度(single resource constrained)：只有一种资源制约着车间力。(2) 双资源车间调度(dual resource constrained)：同时有两种资源制约7着车间力。机床设备往往是制约资源之一，车间有时会缺乏有经验或一技之长的工人，也有可能某种类型的刀具数量有限，因此这两种资源可以是机床设备和工人或刀具。(3) 多资源车间调度(multiple resource constrained)：同时有两种以上的生产所制约着车间的生产能力。这些资源包括员工、机床设备、机器人、物料运送系统和辅助资源，如货盘、夹具和刀具等。单资源车间调度是双资源车间调度的特例，双资源车间调度又是多资源车间调度的特例。所以多资源车间调度问题是最复杂的一种。2按照零件和车间的构成划分：(1) 流水车间调度(Flow shop)：在这种车间中，每个零件都有相同的加工路径。这样，机床设备的布局如同流水线一样，零件一次从流水线的一端进入，最后从另一端流出。(2) 作业车间调度(Job shop)：在这种车间中，机床设备的布局可以是任意的，因此零件的加工路径也是任意的，并且各零件的工序内容和数量也是任意的。这是一种最一般的车间调度形式。(3) 开放式车间调度(Open shop)：每个零件的工序之间的加工次序是任意的。零件的加工可以从任何一道工序开始，在任何一道工序结束。(4) 单车间调度(Single shop)：在这种车间中，每个零件只能有一道工序。3按照零件的加工特点划分：(1) 静态车间调度(Static scheduling)：所有的零件在开始调度时刻已经准备间的调度不考虑零件在加工过程中出现的意外情况，如机床突然损坏、零件的交货期提前、有更紧迫的零件要求被加工等等。(2) 动态车间调度(Dynamic scheduling)：车间的调度要求考虑零件在加工的各种意外情况。这种调度方式要求调度能随时相应车间能力的变化，在有突发事件出现后，能立即根据当时的车间加工能力，对待加工的零件重新展开调度，以确保在任何时候，都能保持车间的加工性能指标处于最优或次优状态。2.4 Job Shop 与 Flow shop 比较1.Job Shop 与 Flow shop的共性8Job Shop 与 Flow shop调度问题是目前调度问题的两大类型，其目标均是通过科学的调度，使车间调度问题最优化。基本约束条件均为：(1) 同一时刻同一台机器只能加工一个零件；(2) 每个工件在某一时候只能在一台机器上加工，不能中途中断每一个操作；(3) 同一个工件的工序之间有先后约束，不同工件的工序之间没有先后约束；(4) 不同工件具有相同的优先级。2、Job Shop 与 Flow shop的个性对于上述约束条件，当增加约束条件：每台机器只有单一加工功能，且各工件中的任意一个工序只能在所有机器中的一台机器上操作且各工件的技术约束条件（加工方法、加工时间、加工设备、加工顺序等）相同时，该问题则转化为 Flow Shop问题；当增加约束条件：每台机器只有单一加工功能，各工件中的任意一个工序只能在所有机器中的一台机器上操作时，该问题转化为 Job Shop问题。Flow shop型问题假设所有作业都在同样的设备上加工，并有一致的加工操作和加工顺序；Job shop 是最一般的调度类型，不同的作业具有不同的加工操作和加工顺序，并不限制作业的加工设备。现代车间调度类型往往是 job shop型的，本文的研究就是针对 job shop 型的调度问题展开。2.5 调度问题的研究方法生产调度问题的研究最初集中在整数规划、仿真和简单的规划等方法上，这些方法不是调度结果不理想，就是难以解决复杂的问题。 随着机器数和工件数的增加，调度方案呈指数增长，怎样才能尽快地得到最优调度方案，这一问题吸引了国内外许多学者和实际生产调度人员的关注，提出了很多的解决方法。近年来，在生产调度领域出现了许多新的优化方法，比如神经网络法、模拟退火法、遗传算法等，使得生产调度问题的研究方法走向了多元化。1精确算法一数学规划法数学规划法主要是通过对车间调度问题建立一个整数规划模型，采用枚举方法寻求调度问题的最优解。数学规划方法往往采用基于枚举思想的分枝定界法或动态规划算法进行求解。分枝定界法基本思想是先求出对调度整数规划模9型所对应的线性规划问题的最优解，如果解不能满足调度问题的整数条件，则对应的线性规划问题的最优解必是调度问题的目标函数值的上界，而调度问题的任意可行解的目标函数值则是其最优解的下界，然后将对应的线性规划问题的可行域分成子域，通过不断减少上界和增大下界，最终寻找到最优解。分枝定界法的实现方法是动态构造一个表示调度问题所有可行解的树，通过对树的搜索寻找调度问题的最优解。分枝定界法只适合于小规模的调度问题，并且对实际问题比较敏感，因此限制了它在调度问题上的应用。动态规划方法的优点是任务分配和排序的全局性比较好，所有的选择同时进行，因此可以保证求解问题的全局优化。但是，动态规划方法是一种精确求解方法，它需要对调度问题进行统一的建模，任何参数的变化会使得算法的重用性很差，因此，对于复杂多变的生产调度来说，单一的数学规划模型不能覆盖所有的因素，存在求解空间大和计算困难等问题。2近似算法由于数学规划法的局限性，从 20世纪 70年代开始出现了启发式算法，这些算法基本上是在一些信息和规则的启发下进行推理和计算，从而获得调度问题的近似最优解。启发式搜索方法的优点是利用了面向特定问题的知识和经验，因而可以产生好的解决方案，求解时间也可以接受。而对于如何提高搜索效率并减少内存使用以解决规模较大的问题，还需要进一步探索。启发式算法主要有：(1) 基于启发式规则的调度算法启发式规则的调度算法也称调度规则，是最早的近似算法。其本质是给每一个生产任务和操作赋予优先级，优先级高的生产任务和操作优先考虑。由于其具有简单、易于实现、计算复杂度低的特点，调度规则在调度问题上得到广泛的应用，同时不断有新的调度规则产生。Panwalkar 等人总结了 113条规则，并将它们分为三类：简单规则、复合规则、式规则，其中属于简单规则有 30多条，如先进先出、最短加工时间、交付期最早等经常使用的规则，其它规则基本上是简单规则的组合或加权组合；另外，调度规则经过适当的组合和变形后，往往可以得到很好的调度效果。调度规则的缺点在于其精确度不够高。随着计算机运算速度的飞速提高，人们希望寻找新的近似调度方法，以合理的额外计算时间代价，换得比单纯启发式规则所得到的调度更好的调度。10(2) 启发式图搜索法启发式图搜索法主要有宽度优先、深度优先、Beam 搜索及 A或者 A算法等。启发式图搜索法的缺点在于计算复杂度较高，如 A*算法的计算复杂度为 D(2n-1)(n为搜索图中结点数)，在调度问题的离散图中结点数为 nxm。对于此类方法如何提高搜索效率、减少内存使用，以能解决比较大的规模的问题，还需要进一步探索。(3) 拉格朗日松弛算法LR算法由于其在可行的时间里能对复杂的规划问题提供较好的最优解，并能对解的最优性进行定量评估，近年来已成为解决复杂生产调度问题的重要方法。但不可避免的是，LR 算法存在搜索效率低，可行调度的构造有待于进一步研究等问题。3智能搜索算法计算智能是通过神经网络、模糊系统、进化计算的有机融合而形成的新的科学方法，也是智能理论和技术发展的崭新阶段。(1) 遗传算法遗传算法(genetic algorithm 简称 GA)是一种崭新的并行优化搜索方法。它是模仿物群体进化过程的一种优化算法，给定一组初始解作为一个群体，通过选择、交叉和变异等遗传操作来搜索最优解。遗传算法对求解问题本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价，并根据适应性进行选择，使适应性好的染色体比适应性差的染色体有更多的繁殖机会，经过反复迭代，直到达到某种形式的收敛。遗传算法尤其适用于处理传统搜索方法难以解决的复杂的非线性问题，可广泛用于组合优化、机器学习和规划设计等领域。遗传算法已经成为一种比较通用的优化算法，主要原因是编码技术和遗传操作比较简单，优化不受限制性条件的约束。但遗传算法也有明显的不足之处：对于大规模的组合优化问题，由于搜索空间大，搜索时间较长，往往会出现早熟收敛的情况；对初始种群很敏感，初始种群选择不好会影响解的质量和算法效率。为了进一步改进遗传算法，人们主要从两方面入手：一是对遗传算法本身进行改进；二是与其它算法结合，取长补短。(2) 禁忌搜索算法11对于复杂的组合优化问题，禁忌搜索也是一种通过邻域搜索以获取最优解的方法。算法的基本过程如下：它从一个可行解 S出发，产生的领域，如果 F为目标函数，选取所有领域中使 F(si)为最优的状态作为下一个状态，并把这一移动的反向移动存入一个称为禁忌移动(Ta bu Move)的表中。列在表中的移动在以后若干步内不允许再产生，这样可免搜索退回去。每搜索一次，更新一次禁忌移动表。由于禁忌移动表的限制，有可能跳出局部极小，从而提高了算法的运行效率。可见，禁忌搜索算法的基本要素是初始解、移动、邻域和禁忌表。禁忌搜索算法没有自然性的终止条件，对求解的问题，目标函数和搜索空间没有任何特殊的要求，计算速度较快。因此，它在调度问题上有着广泛的应用前景。(3) 人工神经网络“人工神经网络是一种模拟人脑神经系统的结构和功能，运用大量的处理部件经广泛互连而组成的网络系统。Hop field 应用神经网络方法求解旅行商问题获得成功，从而为组合优化问题求解开辟了新的途径。人工神经网络的优点是：具有很强的分布式存储能力和很大的存储空间，具有自学习能力，再者容错性好，特有的高维空间使多体效应更加复杂和显着，易于分类。但是，人工神经网络在实际生产中的应用不是很多，而且存在学习效率比较差、难以表达符号知识、计算速度比较慢和精度低等缺点，这些都需要进一步改进。特别是对于求解大规模问题有一定难度。目前，神经网络优化应用于生产调度中，主要有三种方式：一是利用其并行计算能力，求解优化调度；二是利用其自学习能力，从优化轨迹中提取调度知识；三是用神经网络来描述调度约束或调度策略，以实现对生产过程的可行或次优调度。(4) 模拟退火方法模拟退火算法(SA)来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。用固体退火模拟组合优化问题，将内能 E模拟为目标函数值 f,温度 T演化成控制参数 t，即得到解组合优化问题的模拟退火算法：由初始解 i和控制参数初值 t开始，对当前解重复“产生新解一计算目标函数差一接受或舍弃一的迭代，并逐步衰减 t值，算法终止时的当前解即为所得近似最优解，这是基于12蒙特卡罗迭代求解法的一种启发式随机搜索过程模拟退火方法已经应用到许多领域。模拟退火算法显示出了求解优化问题的强大威力，它可以突破局域搜索的限制，转移到代价较高的解答，而且如果选择参数得当，会在很快的时间内收敛。但是，模拟退火算法在实际应用中往往不能产生较优的结果，而且各个参数选择起来比较困难，如果选择不得当，就会使得计算时间很长，而且可能得不到好的结果，模拟退火算法和其它算法结合使用会得到很好的效果，如和遗传算法、人工神经网络结合等。(5) Multi-agent方法多代理通过一系列分散的智能单元(Agent)间进行协调来解决问题，这些单元有各的目标和自治的行为，并且可以有子单元，但是没有一个单元能够解决全局问题，因而它们之间必须进行协调。每个 Agent至少应有以下三个组成部分：1).知识库。包含 Agent执行其功能所必需的知识和数据。2).控制功能。根据环境状态及与其它 Agent间的相互作用，从知识库中提取知识来完成调度功能。3).通讯功能。用来与其它 Agent和环境之间进行信息传递。Multi-agent特别适合解决复杂问题，尤其是那些经典方法无法解决的单元间有大互作用的问题。(6) 模糊逻辑1965年，美国控制论专家 Zadeh教授首先提出模糊集合的概念，发表了开创性论文糊集合论。他提出模糊数学的核心思想就是运用数学手段，仿效人脑思维，对复杂事物进行模糊处理。1973 年，Zadeh 教授又提出模糊逻辑的理论，并积极倡导将模糊理人工智能方向发展。模糊集理论对于建模和求解车间调度问题是非常有用的，因为它就具有许多模糊特征，比如不确定的加工次数、不确定的约束数量以及不确定的加工时间等(7) 蚂蚁调度算法蚂蚁选择路径的原则是依据信息素随机选择，即信息素多的路径被选择的可能性较大，若有一只蚂蚁随机地选择了最短或较短的路径，那么，它能较早地回来并在该路径上留下信息素。在一定时间内，这条路径上就有较多的信息素，从而吸引其它蚂蚁也选择这条路径。由于它们会较早地留下信息素，最短13路径上的信息素量就会越来越多，这种正反馈使得该路径的吸引力会越来越强，另一方面，信息素随时间挥发，较长的路径由于信息素难以得到加强，信息素的量会越来越少，最终被完全废弃。蚂蚁在选择路径的过程中，留下信息素来表示自己的“试错一结果；利用环境实现非直接通信，使得群体能区分不同解的优劣；利用随机选择特性，使得整个蚁群能够跳出局部最优；利用信息素的挥发特性来淘汰劣质解。(8) 神经元算法人工神经元网络的早期研究始于二十世纪四十年代，以 1943年美国生理学家 W.SMcCullocn 和数学家 W.APitts 提出的二值神经元模型为代表。人工神经网络的用人工神经元相互连接组成一个计算网络，并行高效地求解问题。它的主要特点是能够学习，通过给网络提供一定的训练样本，然后根据网络的实际输出与希望输出之间的偏差，利用某种方法逐步修改各人工神经元之间的连接权，形成求解某些问题的能力。从二十世纪八十年代末期开始，人工神经网络被用来求解调度问题。它的主要缺点是效率受训练影响很大，并且在问题规模较大时，计算速度慢，结构参数难以确定。2.6 两机无等待流水车间调度无等待流水车间（no-wait flow shop，NWFS）调度问题是一类十分重要的调度问题，它广泛存在于炼钢、食品加工、化工和制药等领域。已经证明机床数量大于 2的 NWFS是强 NP难题。NWFS 可描述为：给定 m台机床和 n个工件，所有工件在各机床上的加工顺序均相同。同时约定，一个工件在某一时刻只能够在一台机床上加工，一台机床在某一时刻只能够加工一个工件。由于技术条件的限制，同一工件的加工必须连续完成，即同一工件的相邻工序之间没有等待时间。各工序的加工时间已知。问题是如何安排生产，在满足上述要求的条件下得到最小生产周期。2.6.1 生产周期的计算由于同一工件的工序必须连续生产的限制，计算 NWFS的生产周期不同于一般流水车间调度问题。文献3给出了 NWFS生产周期的计算公式：令 为工件kip,i在机床 k上的加工时间， 为一个调度， 为相邻两工件 i-1,.1,.niid,1和 i的开工时间之差（如图 1-1)所示） ；则 为id,114iidi - 1 , i12机床时间 ti - 1i - 1 ii12机床时间 ti - 1i - 1生产周期生产周期a ) N W F S 调度 b ) 流水车间 调度图 1-1 两工件的 NWFS调度和流水车间调度 ,max111,2,1 ikqikqii ppd的生产周期为nimknipdf21,)(上述 和 的算法复杂度分别为 O(m2)、 O(nm2)。id,1)(f2.6.2 生产周期的快速算法结合问题特征，可简化 的计算。如图 1所示，两个工件的 NWFS和流水id,1车间调度问题有相同的生产周期。因此，可先按照流水车间调度问题求得生产周期，再根据连续生产的要求从后向前依次求得 NWFS的各工序开工时间，进而得到 。令 、 分别为工序 的开工、完工时间，求 的算法如下：id,1yxs,c, yxo, id,11. ， ；令 y从 2到 m，分别计算 ，0,i 1,iip ,1yiicsyiiyisc,1,2. ， ；令 y从 2到 m，分别计算 ，,ii 1,iiipsc ,max1, yiiyi cs。yjjyjsc,3. 令 y从 m-1到 1，分别调整 ， 。1,yiisciyiyipc,4. ,1iiisd上述算法的复杂度为 O(m)。若将得到的 代入式（2） ，容易求得生产周id,11-11-215mknp1,期，其复杂度为 O(nm)。因为 共有 个，为了提高算法效率，可预先求id,1)1(n出所有 。这样，在计算生产周期时， 就可视为常数。同id,1 id, 样，可看作常数。于是，式（2）的复杂度就可降低为 O(n)。16第三章 遗传算法3.1 遗传算法的形成与发展遗传算法起源于对生物系统所进行的计算机模拟研究。早在