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

西北工业大学明德学院本科毕业设计论文 本科毕业设计论文 题 目 ： 两机无等待流水车间调度问题与仿真 专业名称 机械设计制造及其自动化 学生姓名 指导教师 毕业时间 2014 年 6 月 西北工业大学明德学院本科毕业设计论文 I 摘 要 流水车间 (Flow Shop)调度问题无论是在工厂经营管理还是在产品制造中都具有广泛的应用，因此对流水车间调度问题进行研究具有重 大的理论意义和实际意义。 本文首先对车间调度问题国内外研究现状和发展趋势进行了系统的阐述。其次，对遗传算法的基本理论进行了详细的论述。然后对 Flow Shop 调度问题建立数学模型。再次，在掌握了遗传算法的基础之上给出了基于遗传算法求解 Flow Shop 调度问题的编码方案，遗传算子的设计。然后基于遗传算法对调度问题进行了实例分析。最后对上述两种调度的结果进行了分析，结果表明本文提出的方法是有效可行的。 关键词： 生产调度 ， 流水车间调度 ， 遗传算法 。 II ABSTRACT Flow 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 目 录 摘 要 . I ABSTRACT . II 目 录 . III 第一章 绪 论 . 1 1.1 引 言 . 1 1.2 国内外车间调度问题的研究现状和存在的问题 . 1 1.2.1 国内外车间调度问题的研究现状 . 1 1.2.2 研究中存在的问题 . 2 1.3 研究意义与目的 . 3 1.4 本文的工作 . 4 第二章 车间调度问题 . 5 2.1. 车间调度问题的描述 . 5 2.2 车间调度问题的特点 . 6 2.3 车间调度问题的分类 . 6 2.4 Job Shop 与 Flow shop 比较 . 7 2.5 调度问题的研究方法 . 8 2.6 两机无等待流水车间调度 . 13 2.6.1 生产周期的计算 . 13 2.6.2 生产周期的快速算法 . 14 第三章 遗传算法 . 16 3.1 遗传算法的形成与发展 . 16 3.2 遗传算法的基本思想 . 17 3.3 遗传算法的特点 . 17 3.4 遗传算法的过程和流程 . 19 3.5 求解调度问题的遗传算法 . 22 IV 3.5.1 遗传算法的设计步骤 . 22 3.5.2 编码方式 . 22 3.5.3 适配值函数 . 24 3.5.4 遗传算子的设计 . 24 3.5.5 编码参数 . 26 3.5.6 遗传算子 . 26 3.5.7 算法的 终止条件 . 26 第四章 两机无等待流水车间调度问题仿真 . 27 4.1 流水车间调度问题的描述与数学模型 . 27 4.2 基于 Johnson 法则的两机无等待流水车间调度问题仿真 . 28 4.3 遗传算法的设计 . 31 4.3.1 编码方案 . 31 4.3.2 群体的 确定 . 31 4.3.3 适应度函数 . 31 4.3.4 遗传算子的设计 . 31 4.4 基于遗传算法的两机无等待流水车间调度问题仿真 . 32 4.5 结果分析 . 32 第五章 全文总结 . 33 参考文献 . 34 致 谢 . 36 毕业设计小结 . 37 西北工业大学明德学院本科毕业设计论文 1 第一章 绪 论 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 国家重点实验室，但离形成系统的理论和开发出成熟的软件系统还有很长一段距离，因此还在投入大量的人力和物力进行该方面的研究，特别是在开展对车间作业作业调度算法的研究方面，目前尚处在实验研究阶段。 车间调度问题的高度复杂性和现有计算机条件的局限性决定了不可能一开始就考虑到实际调度问题中的所有因素，因此，实际研究通常是对车间系统进行简化和抽象来解决实际问题。正是在这些现有的理论成 果上不断加上约束条件，使得研究问题近似于实际问题。总而言之，随着各种特殊调度问题的攻克和新方法、新设备的出现，车间调度研究正向动态、敏捷、多资源、智能化的方向发展。 1.2.2 研究中存在的问题 由于在实际生产过程中会出现诸多不确定因素，而且调度问题己经被证明 3 NP 难题，因此寻找具有多项式复杂性的最优算法几乎是不可能的。从目前文献的研究来看，对于资源分配也没有提出一个切实可行的解决方案，往往都是从某一方面入手，在若干假设的基础上，得出一种理论上的可行解。各种启发式方法、诸如基于规则的算法等，由于能在合理的时间 内产生比较满意的调度，因此广泛应用于实际调度中，但其往往对所得到的调度解的次优性不能进行评估。因此，有必要探索更好的近似最优调度算法，可以考虑通过增加合理的计算时间来提高解的次优性。各种基于统计优化的方法，诸如模拟退火法、遗传算法等，提供了一种解决调度优化问题的新途径，但与别的优化算法类似，也存在着一定程度的枚举、一般来说收敛到最优解较慢，对于判断解的最优性也很困难，在这方面也需要做进一步的研究。 1.3 研究意义与目的 有史以来，有限资源的合理配置和优化利用问题始终是人类社会所面临的最基本经济问题，这个问 题贯穿于社会生活的各个方面。从一个国家、社会的宏观经济运行到具体企业的微观经济活动，都要受资源条件的限制。对企业来说，能否对现有资源进行合理配置和充分利用将直接影响到产品的制造成本，进而成为影响企业效益的重要因素。企业资源的合理配置和优化利用很大程度上体现在车间一层的生产活动中，所以加强车间层的生产计划与控制一直在企业生产经营活动中占有十分重要的地位。 车间生产调度是制造系统生产管理的核心，是生产管理和控制系统实现管理技术、运筹技术、优化技术和自动化技术发展的核心。及时准确的生产调度对生产系统的高效运行有着 重要的影响。生产管理任务能否顺利的实施与完成，最终要靠合理的生产调度来保证有效。 实用的调度方法和优化技术的研究与应用己成为先进制造技术实践的基础。因此，研究生产调度问题，不仅具有较大的理论意义，而且具有相当大的实用价值。一方面，生产调度问题的研究不仅可以推动相关算法的研究，如遗传算法、神经网络、人工智能等，而且还能在此基础上提出新的算法，这为其他领域类似问题的解决提供了条件和手段；另一方面，一个好的生产调度方案不仅可以降低生产成本，而且可以提高企业产品的准时交货能力，从而增强企业的竞争力。 随着科学技术的 发展，制造行业的生产规模变得越来越大，产品越来越多样 4 化，车间生产情况的复杂性也越来越高。同时，由于加工系统的复杂性和多样性，目前还没有一种通用的、全面的方法解决各种生产方式的优化调度问题。制造企业迫切希望能有一个结合其自身特点的实用而有效的调度支持系统，这就需要根据企业的实际状况和生产变化，从以获得工程满意解的实际需求出发，选取调度目标，应用能满足要求的快速有效的优化算法，满足企业的实际需求，实现优化调度。 1.4 本文的工作 第一章 绪论，从课题的研究背景到车间调度的国内外的研究现状再到车间调度存在的问 题及解决途径来引出遗传算法对车间调度问题研究的重要性。描述了车间调度问题。进而描述了关于车间调度的较常见的几种研究方法及它们的应用领域。 第二章 车间调度问题综述，先介绍车间调度问题其中包括车间调度问题的描述、特点、分类、 job shop 与 flow shop 比较然后追寻调度问题研究方法 (数学规划法、近似算法、智能搜索算法、模拟退火方法、 Multi-agent 方法、模糊逻辑、蚂蚁调度算法、神经元算法 )，从而找到一些解决这些问题的办法。 第三章 遗传算法，先介绍遗传算法的形成与发展，然后再介绍遗传算法的基 本思想和特点，阐述一下遗传算法的过程和流程，最后求解调度问题的遗传算法其中包括遗传算法的设计步骤、编码方式适配值函数、遗传算子的设计、编码参数、遗传算子和算法的终止条件。 第四章 基于遗传算法的流水车间调度问题，首先介绍流水车间的背景，然后对流水车间调度问题进行描述与建立数学模型，进行遗传算法的设计其中包括编码方案、群体确定、适应度函数、遗传算子的设计 ， 并且进行了仿真。 5 第二章 车间调度问题 2.1. 车间调度问题的描述 生产调度通常是生产过程的作业计划， 例如某机器上工件的加工顺序，以及要加工点的工件如何划分批次。从本质上分，调度问题可以为开环调度和闭环调度。所谓开环调度是指研究工件加工的顺序，所有的客户订购的产品，在机器上排序生产，不考虑其他的因素，闭环调度是指，除了考虑工件的加工顺序之外，还要考虑产品批次的大小等。显然闭环调度的复杂性远远大于开环调度的复杂性，目前对闭环调度的处理通常使用近似方法，首先确定批量大小，然后再确定加工顺序。 生产调度的问题基本上可以概述为：对于某一项可分解生产任务，在特定的约束条件下，分派生产所需要的资源，安排子任务的生产时间，并对子任务进行排序，目标是产 品的最短的制造时间，或者最低产品成本。其中生产所需要的资源主要包括：人力资源、资金、生产原料、生产设备等，评价目标好的的指标一般有：产品的生产周期短，总成本低和生产设备利用率低等。 生产调度的形式可以描述为： n 个工件， m 台机器加工，每一个工件需要在m台中的一台或者多台加工，假设第 i个工件 ni1 ，在第 j台机上加工 mj 1加工时间为 Pij，加工操作位 Oij 没一个工件的准备时间为 Rij，工件的交货期为 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 的共性 Job Shop 与 Flow shop 调度问题是目前调度问题的两大类型，其目标均是通过科学的调度，使车间调度问题最优化。基本约束条件均为： 8 (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 多条，如先进先出、最短加工时间、交付期最早等经常使用的规则，其它规则基本上是简单规则的组合或加权组合；另外，调度规则经过适当的组合和变形后，往往可以得到很好的调度效果。调度规则的缺点在于其精确度不够高。随着计算机运算速度的飞速提高，人们希望寻找新的近似调度 方法，以合理的额外计算时间代价，换得比单纯启发式规则所得到的调度更好的调度。 (2) 启发式图搜索法 启发式图搜索法主要有宽度优先、深度优先、 Beam 搜索及 A 或者 A算法等。 10 启发式图搜索法的缺点在于计算复杂度较高，如 A*算法的计算复杂度为D(2n-1)(n 为搜索图中结点数 )，在调度问题的离散图中结点数为 nxm。对于此类方法如何提高搜索效率、减少内存使用，以能解决比较大的规模的问题，还需要进一步探索。 (3) 拉格朗日松弛算法 LR 算法由于其在可行的时间里能对复杂的规划问题提供较好的最优解，并能对解的最优性进 行定量评估，近年来已成为解决复杂生产调度问题的重要方法。但不可避免的是， LR 算法存在搜索效率低，可行调度的构造有待于进一步研究等问题。 3智能搜索算法 计算智能是通过神经网络、模糊系统、进化计算的有机融合而形成的新的科学方法，也是智能理论和技术发展的崭新阶段。 (1) 遗传算法 遗传算法 (genetic algorithm 简称 GA)是一种崭新的并行优化搜索方法。它是模仿物群体进化过程的一种优化算法，给定一组初始解作为一个群体，通过选择、交叉和变异等遗传操作来搜索最优解。遗传算法对求解问题本身一无所知，它所 需要的仅是对算法所产生的每个染色体进行评价，并根据适应性进行选择，使适应性好的染色体比适应性差的染色体有更多的繁殖机会，经过反复迭代，直到达到某种形式的收敛。遗传算法尤其适用于处理传统搜索方法难以解决的复杂的非线性问题，可广泛用于组合优化、机器学习和规划设计等领域。 遗传算法已经成为一种比较通用的优化算法，主要原因是编码技术和遗传操作比较简单，优化不受限制性条件的约束。但遗传算法也有明显的不足之处：对于大规模的组合优化问题，由于搜索空间大，搜索时间较长，往往会出现早熟收敛的情况；对初始种群很敏感，初始种群选 择不好会影响解的质量和算法效率。为了进一步改进遗传算法，人们主要从两方面入手：一是对遗传算法本身进行改进；二是与其它算法结合，取长补短。 (2) 禁忌搜索算法 对于复杂的组合优化问题，禁忌搜索也是一种通过邻域搜索以获取最优解的方法。算法的基本过程如下：它从一个可行解 S 出发，产生的领域，如果 F 为目 11 标函数，选取所有领域中使 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.S McCullocn 和数学家 W.A Pitts 提出的二值神经元模型为代表。人工神经网络的用人工神经元相互连接组成一个计算网络，并行高效地求解问题。它的主要特点是能够学习，通过给网络提供一定的训练样本，然后根据网络的实际输出与希望输出之间的偏差，利用某种方法逐步修改各人工神经元之间的连接权，形成求解某些问题的能力。从二十世纪八十年代末期开始，人工神经网络被用来求解调度问题。它的主要缺点是效 率受训练影响很大，并且在问题规模较大时，计算速度慢，结构参数难以确定。 2.6 两机无等待流水车间调度 无等待流水车间（ no-wait flow shop， NWFS）调度问题是一类十分重要的调度问题，它广泛存在于炼钢、食品加工、化工和制药等领域。已经证明机床数量大于 2 的 NWFS 是强 NP 难题。 NWFS 可描述为：给定 m 台机床和 n 个工件，所有工件在各机床上的加工顺序均相同。同时约定，一个工件在某一时刻只能够在一台机床上加工，一台机床在某一时刻只能够加工一个工件。由于技术条件的限制，同一工件的加工必须连续完成，即同 一工件 的 相邻工序之间没有等待时间。各 工序的加工时间已知。问题是如何安排生产， 在 满足上述要求的 条件下 得到最小生产周期。 2.6.1 生产周期的计算 由于同一工件的工序必须连续生产的限制，计算 NWFS 的生产周期不同于一般流水车间调度问题。文献 3给出了 NWFS 生产周期的计算公式：令随 机 产 生 初 始 种 群并 计 算 个 体 适 配 值算 法 收 敛 准 则是 否 满 足执 行 复 制 操 作random0,10。在复杂问题的优化时，往往需要构造合适的评价函数，使其适应 GA 进行优化。 )()f JMTMJM （ （ 3-1） 3.5.4 遗传算子的设计 遗传算子优胜劣汰是设计 GA 的基本思想，它应在选择、交叉、变异等遗传算子中得以体现，并考虑到对算法效率与性能的影响。 1.选择复制 复制操作是为了避免有效基因的损失，使高性能的个体得以更大的概率生存，从而提高全 局收敛性和计算效率。最常用的方法是比例复制和基于排名的复制，前者以正比于个体适配值的概率来选择相应的个体，后者则基于个体在种群中的排名来选择相应的个体。至于种群的替换，采纳的方案可以是部分个体的替换，也可以是整个群体的替换。 2.交叉算子 (1).交叉方法 1： 首先选取父代染色体 1 和 2，随机产生一个与染色体长度相同的向量，该向 25 量由数字 1、 2 组成。向量定义了从父代 1 和父代 2 中选取基因的顺序。从一个父代上选取 1 个基因并从另一个父代上消除对应的基因，并且将该基因加到子代上去；重复该步骤直到两父代染色体为空并且子代 染色体包含所有的基因。 父代 1 ： 3 2 4 2 2 3 1 1 1 4 3； 父代 2： 1 4 1 3 2 2 1 2 4 3 3 索 引： 1 1 1 2 3 2 1 2 3 2 3； 索引： 1 1 2 1 1 2 3 3 2 2 3 随机产生的数字： 1 1 2 2 2 2 2 1 1 1 1 交叉方法 1 结果： 子代 1： 3 2 1 4 1 2 1 2 3 4 3； 子代 2： 1 4 3 2 2 2 3 1 1 4 3 (2).交叉方法 2： 从父代染色体中任意选取一个子串，然后把该子串插入到 父代 2 中子串中第一个基因出现的位置，然后从得到的染色体中删掉子串索引所对应的所有基因。 父代 1： 3 2 4 2 2 3 1 1 1 4 3； 父代 2： 1 4 1 3 2 2 1 2 4 3 3 索 引： 1 1 1 2 3 2 1 2 3 2 3； 索 引： 1 1 2 1 1 2 3 3 2 2 3 随机产生的数字： 1 1 2 2 2 2 2 1 1 1 1 交叉方法 2 结果： 子代 1： 4 3 2 2 1 2 3 1 1 4 3； 子代 2： 3 2 2 1 2 4 3 1 1 4 3 (3).交叉方法 3： 从父代染色体 1 中任意选取一个子串，先从染色体 2 中删掉子串索引所对应的所有基因，然后把该子串插入到父代 2 中子串在父代 1 中出现的位置。 父代 1： 3 2 4 2 2 3 1 1 1 4 3； 父代 2： 1 4 1 3 2 2 1 2 4 3 3 索 引： 1 1 1 2 3 2 1 2 3 2 3； 索 引： 1 1 2 1 1 2 3 3 2 2 3 随机产生的数字： 1 1 2 2 2 2 2 1 1 1 1 交叉方法 3 结果： 子代 1： 4 3 2 2 2 3 1 1 1 4 3 ； 子代 2： 3 4 3 1 2 2 1 2 1 4 3 (4).交叉方法 4： 从父代染色体 1 中任意选取一个子串，然后把该子串插入到父代 2 中子串在父代 1 中出现的位置，从染色体 2 中删掉子串索引所对应的所有基因 父代 1： 3 2 4 2 2 3 1 1 1 4 3； 父代 2： 1 4 1 3 2 2 1 2 4 3 3 索 引： 1 1 1 2 3 2 1 2 3 2 3； 索 引： 1 1 2 1 1 2 3 3 2 2 3 随机产生的数字： 1 1 2 2 2 2 1 1 1 26 交叉方法 4 结果： 子代 1： 4 3 2 3 1 1 2 2 1 4 3 ； 子代 2： 3 4 2 2 1 2 3 1 1 4 3 3.5.5 编码参数 种群数目是影响算法优化性能和效率的因素之一。 通常，种群太小则不能提供足够的采样点，以至算法性能很差，甚至得不到问题的可行解 ; 种群太大时尽管可增加优化信息以阻止早熟收敛的发生，但无疑会增加计算量，从而使收敛时间太长。当然，在优化过程中种群数目是允许变化的。 交叉概率用于控制交叉操作的频率表。概率太大时，种群中串的更新很快，进而会使高适配值的个体很快被破坏掉；概率太小时，交叉操作很少进行，从而会使搜索停滞不前。 当交叉 操作产生 的后代适配值不在进化且没有达到最优时，就意味着算法的早 熟 收敛。这种现象的根源在于有效基因的缺损。 变异操作一定程度上 克 服了这种情况，有利于增加种群的多样性。 变异概率是加大种群多样性的重要因素。基于二进制编码的 GA 中，通常一个较低的变异率足以防止整个群体中任意位置的基因一直保持不变。但是，概率太小则不会产生新个体，概率太大则是 GA 成为随 机 搜索。 3.5.6 遗传算子 优胜劣汰是设计 GA 的基本思想，它应在的选择、交叉、变异等遗传算子中得以体现，并考虑到算法效率与性能影响。 复制操作是为了避免有效基因的损失，使 高性能的个体得以更大的概率生存，从而提高全局收敛性和计算效率最常用的方法是比例复制和基于排名的复制，前者以正比于个体是配置的概率来选择相应的个