【毕业学位论文】（Word原稿）基于新的动态邻域算法的车间调度问题的研究

摘要 作业加工调度问题 是 的， 被认为是最难的组合 优化问题之一。 在 解决工业生产、经济管理和网络通讯等诸多问题 时 ，都要 涉及 求解这个问题。优质、快速地求解作业加工调度问题，既有重要的理论意义，又能带来巨大的经济效益。 转换瓶颈算法是解决 作业加工调度问题 的最有效的 算法之一 ，本 论文中用 转换瓶颈算法来产生 问题 的初始值，进而提高 搜索 效率。动态邻域算法的 基本思想是 利用 两个主要 工具“ 动） ” 和 “ 部搜索） ” ， 局部搜索 用于 探索 一个更为 优的结果， 振动 使局部最小跳入 它 的下一个邻域 ， 从而继续 进行局部搜索。 本 论文是 依 据这个基本思想 研究和分析并进行改进 ， 提出一个新的算法。 为了 提高 振动 的 效率 ， 我们 根 据 卡里尔 定理 11和 格拉博夫斯基 定理 7提 出了六个 推论 ，以 避免无用的 局部邻域 结构的 切 换， 并且提出了新的邻域结构， 即： “向前 插入 ” ， “ 向后插入 ” ， “直接交换”。同时把 振动 分为 “ 正常 振动” 和 “ 贪婪 振动” 。 实验 表 明基于六个 推论 ， 振动更加有驱动力 。 基于新的邻域结构 ， 可以找到更好的某个点的邻域最小值。 关键词 ： 作业加工调度 启发式 动态邻域算法 he is P as of as It is in of to a of is to be a Pof is of to of of is an In my BP be to is to is a is of In an NS an an by to In In in to of we to to In it is on is in In if it is a NP 目录 I 目录 第一章 绪论 . 1 究的背景与意义 . 1 合最优化问题 . 2 际难解性和 全问题 . 3 发式方法 . 4 发式方法的性能评价 . 5 用的启发式算法 . 6 文的主要内容和结构 . 7 第二章 作业加工调度问题及相关算法 . 9 业加工调度问题的描述 . 9 模型 . 9 甘特图表示 . 10 分离图表示 . 11 复杂性 . 12 态邻域算法 . 12 转换瓶颈算法 . 16 换瓶颈算法的原理 . 16 换瓶颈算法流程图 . 19 第三章 动态邻域算法的改进及其设计 . 21 作业车间调度模型的建立 . 21 号说明 . 21 学模型 . 22 作业车间调度的编码问题 . 22 生成初始解的方法 . 22 振动操作的邻域结构 . 24 动操作的邻域结构 . 24 于振动邻域结构的推论 . 25 局部搜索操作的邻域结构 . 29 局部搜索操作的邻域结构 . 29 部搜索部分前项插入 . 30 基于新的动态邻域算法的车间调度问题的研究 部搜索部分后项插入 . 30 部搜索部分的交换 . 31 组成结构 . 33 动态邻域算法的结束条件 . 34 流程图 . 35 第四章 改进的动态邻域算法的分析 . 37 拟环境 . 37 种启发式算法的 比较 . 37 第五章 全文总结及展望 . 41 要工作总结及创新 . 41 来的研究方向 . 42 致谢语 . 43 . 45 附录 . 49 第一章 绪论 1 第一章 绪论 自然界中存在一类问题，被人们称之为 于精确求解这类问题所花费的时间与问题实例的规模成指数型函数关系，因此为计算出规模不大 （ 如不超过 1000） 的问题实例的精确解，即使用当今最快的电子计算机往往要用去宇宙的剩余年限。因此，用近似的方法求解具有 论文针对一个具体的 态邻域算法。 我们所研究的 作业加工调度问题是组合最优化问题之一。在介绍 动态邻域算法 的研究结果之前，本章将综合、扼要介绍组合最优化问题、计算复杂性理论、启发式方法和作业加工调度问题，并说明本课题的来源及其研究意义。 究的背景与意义 生产调度，即对生产过程进行作业计划，作为一个关键模块，是整个先进生产制造系统实现管理技术、运筹技术、优化技术、自动化与计算机技术发展的核心。有效的生产调度方法和优化技术的研究和应用，是实现先进制造和提高生产效益的基础和关键。从上个世纪 50 年代起，调度问题的研究就受到应用数学、运筹学、工程技术等领域科 学家的重视，科学家们利用运筹学中的线性规划、整数规划、目标规划、动态规划及决策分析方法，研究并解决了一系列有代表意义的调度和优化问题。但是，人们普遍把 人有关调度的研究工作 17作为调度理论研究的正式开始，他们 3 人也被人们称为调度理论的奠基人。此后 30 多年的调度理论和应用研究都受到他们的影响。调度问题涉及面非常广泛，所以有很多种调度问题。根据加工系统的复杂度，生产调度可以分为单机调度、 度、 度、 度、多机器并 行加工调度等几个基本类型。单机调度是指所有的操作任务都在一台机器上完成，需要对任务进行优化排队 ； 度是最一般的调度类型，它是指由 m 台不同的机器加工 顺序 )的工件（ ， 不同工件的工序间没有顺序约束，工序加工不能中断 。 度假设所有工件都在同样的设备上加工，并有一致的加工操作和加工顺序 。 多机器并行加工调度是指多台机器并行加工工件，而且并行加工的机器和工件都是类似的。实际的调度问题通常是上述几种调度类型的组 合。 基于新的动态邻域算法的车间调度问题的研究 2 本文主要研究求解 度问题（ 。 要对工场内的作业进行组织、调度和管理。而工场以完成大量的作业为其基本特征，以组织生产过程，合理利用设备、生产出产品或配件为其主要目的 ， 这些产品通常有一种或多种不同的处理方式或过程。每种过程又是由一系列工序所组成。这些工序将占用一定的资源并需要在机器上持续一定的时间。对每一种产品的生产，其相关的工序又要按照一定的次序进行。求解 度问题即是要确定一系列工序的前后顺序、起始时间及占用的资源等并满足一定的要求。这些要求主要包括 ： 机器闲置与劳动力的费用、调度过程中库存 中的费用、交货日期等等 。 度问题不仅是 被认为是最难的组合最优化问题之一。解决工业生产、经济管理、交通运输和网络通讯等诸方面的一些问题，都要借助于求解这个问题。因此，优质、快速地求解 度问题，既有重要的理论意义，又能带来巨大的经济效益。 合最优化问题 随着计算科学理论的发展和科学技术的不断提高，人类对组合最优化问题的认识与研究不断加深，而且解决这种问题的技术也在不断改进。目前的研究认为，组合最优化问题是研究某些具有约束条件的问题的最优解 它的存在性和当 它存在时求解它的方法，通常的表现为 ： 对于给定的具体问题，研究如何从众多的可行的解决方案中选出某种意义下的最优的解决方案。我们知道，组合最优化问题研究的对象是离散的事件，下面是被人们广泛接受的它的形式化的定义。 定义 组合最优化问题。在给定的约束条件下，求目标函数最优值 (最大值或最小值 )的问题称为组合最优化问题。组合最优化问题的一个实例可以表示为一个偶对 (S,f ) ，其中解空间 S 是可行解的集合，目标函数 f 是一个映射，定义为 f： SR 式（ 1 求目标函数的最小值的问题称为最小化问题，记为 f(i) i S 式（ 1 求目标函数的最大值的问题称为最大化问题，记为 f(i) i S 式（ 1 很明显 ， 在形式上只要改变目标函数的正负号，问题 式（ 1和 式（ 1是可以等价地转换的。本文以 式（ 1为研究形式。 为了进一步说明 组合最优化问题的解，以下将依次给出几个重要的概念。 定义 邻域结构。令 (S, f )是组合最优化问题的一个实例，则邻域结构是一个映射 N： S 2s 式（ 1 第一章 绪论 3 它表示对于每个解 x S，有一个解的集合 N(x) S， N(x)就称为 x 的领域。N(x)中的元素在某种意义下是邻近于 x 的，并且 x N (x)称为 x 的邻近解。 映射 是在实际解 决问题的时候，人们总是将它定义 得“简单”、“优美”、“有效”。换句话说 ， 任何 x N (x)都只是对 x 做“很小的”、“自然的”修改所得到，同时这种邻域的定义有利于问题的求解。 有了邻域的概念以后，我们就可以给出组合最优化问题的两个核心的概念 局部最优解和全局最优解。 定义 局部最优解。设 (S, f )是组合最优化问题的一个实例，满足条件 *f ( x ) = m i n f ( x ) | x N x *（ ） 式（ 1 的可行解 x* 称 为 (S, f )的一个局部最优 (或局部极小 )解。 定义 全局最优解。设 (S, f )是组合最优化问题的一个实例，满足条件 *f ( x ) = m i n f ( x ) | x S 式（ 1 的可行解 x* 称为 (S, f )的全局最优 (或全局极小 )解。 从上述定义不难看出，对任何的 (S, f )，其全局最优解必定是它的一个局部最优解，反之则不必然。 际难解性和 全问题 在求解所遇到的组合最优化问题时，人 们甚至发现有些问题 是不能用算法求解的， 也就是这些问题是原则上是没有算法解的 1117， 本论文将不讨论这类问题。至于那些原则上有算法解的问题，有些易于求解，而有些问题难解。于是，在“原则上是可计算的”的前提下，问题复杂性的概念得以提出 21。我们知道， 一个问题实例的规模可以用一个自然数 n 来表示 ， 如果存在求解问题的算法其最大的计算步数可以用 n 的多项式来表示，那么说该算法具有多项式时间复杂度，该问题是多项式时间可解的。为了定义算法，人们设计了一个计算模型 19。 对一个问题，如果有解它的多项式 时间 定型图灵机 )程序，那么就称该问题是易解的，所有这一类问题的集合被称作 P。就是说， P (题是指具有多项式时间复杂度的确定型算法的问题类 19。 对一个问题，如果有解它的多项式时间 非确定型图灵机 )程序，那么就称该问题属于 (即所有具有多项式时间复杂度的非确定型算法的问题的集合被称为 。 P 之外的问题都被看成实际上难解的。一个问题是实际上难解的就意味着，即使用最好的确定型算法来计算它，计算所需消耗的资源也会随问题规模的 增长而急剧增长，这一增长速度快于任何一个多项式函数的增长速度。当问题规模增加到一定程度，计算它所需要的资源会很快增加到令人无法接受的程度，甚至即使基于新的动态邻域算法的车间调度问题的研究 4 耗尽世界上所有可利用的资源，为得出问题的答案，计算所需时间也将超过人们所能接受的范围。 研究表明，很多目前还没有多项式时间复杂度的确定型算法的问题，都具有多项式时间复杂度的非确定型算法。很明显 P ， 但是否有 P 还没有肯定或否定的答案，即是否 P=至今的一个未解之迷。 换句话说， 的问题是否都是易解的仍然是一个未解之迷。这就是著名的 P?=题 对一个问题，如果 中的任何一个问题都可以多项式时间归约到它，那么就称这个问题是 的 (如果一个问题既属于 是 的，那么称该问题是 全的 19。 1971 年， 人成功地证明了合取范式可满足性问题，即通常所说的 题，是 全的 19。 从 二十世纪六十年代以来，许多组合优化问题被证明是 全的，其中有代表性的问题有旅行 商问题、图着色问题、背包问题、调度问题、 题和题等。由于 全问题的难解性，如今人们不再苛求能够在自己可接受的时间内找出问题的最优解，而倾向于针对具体的组合优化问题设计算法，以求在尽可能短的时间内找出尽可能好的解 通常所说的次优解。换句话说，当人们知道所关注的问题是 全问题时，大家更愿意降低标准去采用非最优解，去采用不总是多项式的或者不在所有可能实例上工作的算法 12。这是一个突破性的思想，粗看上去我们倒退了，但事实上，我们在求解组合最优化问题这个领域向前迈进了一大步 ，它是人类同自然作斗争的一种迂回的策略。 在这个思想的指引下，大量的近似求解具有 度的组合最优化问题的算法随即涌现出来，代表性的算法有近似算法、回溯和分支界限算法、局部改进算法等 9。这些算法减弱了严格、规整的逻辑推理，大胆运用来自于自然界、人类社会的启发，使得快速、有效、近似地求解这些组合最优化问题成为可能 19。 发式方法 启发式搜索是启发式方法得以实现的手段 10，它就是从由问题的所有的解组成的解空间中找出一个尽可能好的解。因此就有一个搜索过程，在此过程中，启发式搜索充分利用与问题有 关的某些信息，以使自己尽快地找到更好的解。 启发式算法是通过执行具体的启发式搜索而得到的算法，它是相对于求解具有 度问题的最优算法 (或称完整算法 )而提出的。启发式方法是指引搜索方向以快速高效地求解问题的原则或规则。 启发式是一个学术研究领域中的术语，其本意是研究发现和发明的方法，它与哲学、逻辑学和心理学都有关联。这个名字来自希腊语文字 一章 绪论 5 今天，这一术语被用来描述一种方法 ： 这个方法建立在经验或者判断的基础上，它似乎能产生有关问题的一个好的解，但是不能确保产生这个问题的最好的解 (最优解 )。 下面我们再给出几个重要的定义。 定义 启发式 概念 。一个基于直观或经验构造的算法，对待解决的组合最优化问题的每一个实例，能够在可接受的花费 (计算时间、占用空间 )下给出一个可行解，该可行解相对于最优解的偏离程度不一定事先可以预计。在很多情况下人们还接受了启发式算法这一概念的另一个定义。 定义 启发式算法。启发式算法是一种技术。它在可接受的计算费用内寻找出最好的解，但是不一定能够保证所得到的解的可行性和最优性，并且在多数情况下，无法阐述所得解同最优解的近似程度。 定义 启发式方法。启发 式方法，或更一般地，经验规则，是对启发式算法的综合，它是指引搜索方向以求到达目标节点路径的原则或规则。启发式算法和启发式方法这两个概念的联系十分紧密，在某些情况下含义相同。在许多文献中，它们没有被严格区分。 发式方法的性能评价 启发式方法之所以能够迅速发展，是因为它具有以下优点 ： 模型本身是实际问题的简化，它往往会忽略一些次要因素 ： 数据采集具有非精确性 ;参数估计具有非准确性 ;以上这些因素可能使最优算法所得到的解比启发式法所得到的解产生更大的误差。 有些难的组合最优化问题还没有找到最优算法，或 者即使找到了，根据算法复杂性理论，其计算时间是无法接受的或不切实际的。 某些启发式方法可以用在最优算法之中，例如，在分支定界算法中，对上下界的估算就是用启发式方法。 简单易行，直观，容易被使用者接受。 速度快，应用于适时管理系统中十分有效。 多数情况下，其程序简洁，易于修改。 启发式方法当然有其缺点，这些常常既是人们在研究过程中争论的焦点，又是这个方法得以发展之所在。 不能保证算法一定得到最优解。 性能不稳定。启发式算法对同一个问题的不同实例的计算会产生不同的效果。所得有些实例的解的优度很高，而 另一些则相反。在工程应用中，启发式算法的这种不稳定性使得计算结果不可信。 基于新的动态邻域算法的车间调度问题的研究 6 启发式算法的优劣依赖于具体问题以及设计者的经验、技术等，这一点很难总结成规律，同时使不同算法之间难于比较。 一个好的启发式算法可以使其解尽可能地接近最优解，同时保持很好的稳定性。评价启发式算法的性能有很多不同的方法，主要是对算法的复杂性和它的计算效能进行分析。 用的启发式算法 启发式算法包括 禁忌 搜索法、模拟退火法、遗传算法、 人工神经网络和蚂蚁算法等等。 禁忌 算法是局部搜索算法的推广，是人工智能在求解组合最优化问题中 的一个成功的应用。局部搜索算法实质上就是在可行解空间中搜索，这里的禁止 就是禁止这种搜索回到原先搜索过的解，即禁止走回头路。为了克服局部搜索容 易落入局部最优的陷阱的严重不足，禁止搜索算法采用一种特殊的数据结构来记录曾经搜索过的解，在以后的搜索过程中利用这些信息来防止搜索回到过去。这 个思想的最大优点是可以组织搜索在某个局部最优解附近徘徊进而逃出这样的陷 阱。本论文稍后还将详细介绍这个算法。 人工神经网络是人类长期对大脑结构的理解、受大脑传递信息机制的启发，从 而设计出的能够实现某些大脑的功能的一种计算模型，或者说是基于 模仿大脑这个神经中枢的网络结构和功能而设计出来的一种信息处理系统。人工神经网络是由大量简单的神经单元按照一定的规则连接而成的复杂网络系统，它具有高度的 非线性性，能够进行十分复杂的逻辑操作和给线性性关系实现的系统。每一个神 经单元的简单的行为通过神经单元之间的连接来完成复杂的或具有 智能 的操作。人工神经网络就是通过对大脑神经系统的结构、功能及其信息处理机制的探索，构造出与大脑智能相近的人工的神经网络。虽然这种思想和技术产生时间不长，它正被广泛应用于自动控制等许多工程领域 11。 蚂蚁算法是观察自然界中蚂蚁的 行为，受它们总是沿最短路径寻找和搬运食物的特征行为的启发而设计出的算法。通过模拟蚂蚁在寻找和搬运食物的路径上处 理信息的行为，蚂蚁算法利用某些有效的优化策略快速高效地求解了寻找最短路 径的组合最优化问题，例如旅行商问题 ( 模拟退火算法也是局部搜索算法的一种扩展。它对于局部搜索算法的最大的改 进是它以一定的概率选择接受邻域中费用较大的解。理论上说，它是一个全局最 优算法。模拟退火算法的基本思想是立足于晶体的结晶 (退火 )过程与寻求组合最优化问题的最优解的过程的相似 性。事实上，在退火过程中，各个粒子都要经历由较高的热能状态变化到较低的热能状态，以及由于晶体的热能分布不均匀而造第一章 绪论 7 成的某些粒子偶尔由较低的热能态回迁到较高的热能态的复杂过程。人们由此得到启发 ： 将组合最优化的可行解目标函数分别对应于晶体的热运动状态和能量，则对所得解的优化过程就类似于晶体的结晶过程。晶体 吸热时，其热能增加 ， 于是其温度升高，对应的目标函数值就变大 ;当晶体放热时，其热能减少，于是其温度降低，对应的目标函数值就变小。当温度降低到某个值的时候，晶体与外界形成等量热交换，晶体处于热能稳定态，对应的目标函数 就收敛到一个局部极小 值 。 遗传算法是借鉴生物进化的自然选择和遗传机制而设计出的一类随机搜索算法。这个算法的主要特点时是群体搜索策略和群体中个体之间的信息交换，搜索不依赖于梯度信息。遗传算法的本质是一种求解问题的并行高效全局搜索方法，它模拟由个体组成的群体的整体学习过程，其中每个个体表示给定问题搜索空间中的一个解。遗传算法从任一初始化的群体出发，通过随机的选择 (使得群体中优秀的个体的特征有更多的机会传给下一代 )、交叉 (体现自然界中群体内个体之间的信息交换 )和变异 (在群体中引入新的变种以确保群体中信息的多样性 )等遗传操作，使群体一代接一代地进化，以此将搜索引到解空间中越来越好的区域， 直至抵达最优解。 二十世纪八十年代初被设计出的 启发式算法，如 禁忌 搜索法、模拟退火法、遗传算法、人工神经网络、蚂蚁算法等，到现在都得到了很大的发展。 文的主要内容和结构 本文共分五章，具体章节安排如下 ： 第一章 介绍选题的意义、 度问题及求解 度问题的基本算法和研究现状，描述了我们研究的主要内容。 第二章 介绍动态邻域算法的基本理论，包括该算法的基本概念、基本定理、基本流程、基本实现技术等。同 时介绍著名的转化瓶颈算法。 第三章 设计一种求解 度问题的改进动态邻域算法，基于已有的数学模型对调度模型进行仿真研究。 (这也是本文的核心工作 )。 第四章 对实验结果进行总结，以及概括出我们算法的优缺点。 第五章对本文进行了总结和展望。基于新的动态邻域算法的车间调度问题的研究 8 第二章 作业加工调度问题及相关算法 9 第二章 作业加工调度问题及相关算法 业加工调度问题的描述 作业加工调度问题 (以下简称 题 )一般可以描述为 ： 给定一个 工件 （ 集合和一个机器的集合，每个工件包括多道 工序（ ，每道工序需要在一台给定的机器上非间断地加工某 一段时间 。 模型 许多实际生产调度问题的简化模型 。 究 n 个工件在 m 台机器上的加工。已知每个工件在各个机器上的加工次序和每个工件的各个工序的加工时间。要求确定与工艺约束条件相容的各机器上所有工件的加工开始时刻、完成时刻、加工次序，使加工性能指标达到最优。各个工件和机器应满足以下约束 ： (1)在整个加工过程中，每个工件只能被所有的机器都加工并且只加工一次 ； (2)各个工件必须按工艺路线以指定的次序在机器上加工 ； (3)加工过程不能间断 ； (4)每一时刻每一台机器只能加工一个工 件。 求解就是要找到一个合理的安排使每个工件都能在满足工艺约束的条件下在各台机器上加工，使得总的加工时间最短。对于工件 i， 第 i 工件在机器 k 上的完成时刻， 第 i 工件在机器 k 上的加工时间，如果机器 h 先于机器 i，则应满足如下约束 ： 式（ 2 如果机器 k 先于机器 h 加工工件 i，则应满足如下约束 ： 式（ 2 定义变量 ： 0， 否则； 1， 机器 i ； 则上述约束可表示为 ： L(1 式（ 2 i,j=1,2, n, h,k=1,2, m. 基于新的动态邻域算法的车间调度问题的研究 10 其中 L 为一足够大的正数。对于在机 器 k 上加工的工件 i 和 j，如果工件 i 先于工件 j 在机器 k 上加工，则应满足如下约束 ： 式（ 2 如果工件 j 先于工件 i 在机器 k 上加工，则应满足如下约束 ： 式（ 2 定义变量 ： 0， 否 则； 1， 工件 则上述约束可表示为 ： L(1 式（ 2 i,j =1,2, n, h,k=1,2, m. 因此一个 n/m/G/ (n 表示工件数， m 表示机器数， G 表示是 度问题， 示性能指标为最大完成时间 )的 度问题的数学模型可描述如下 ： 11m i n m a x m a x m i L(1 式（ 2 i,j =1,2, n, h,k=1,2, m. L(1 式（ 2 i,j =1,2, n, h,k=1,2, m. 0,0, 式（ 2 i,j =1,2, n, h,k=1,2, m. 0 , 式（ 2 i =1,2, n, h,k=1,2, m. , 式（ 2 i,j =1,2, n, h,k=1,2, m. 甘特图表示 对于 m 台机器 （ n 个工件 （ 加工过程，所谓的调度就是分配各工件在各机器上的加工时间，调度通常用甘特图表示。甘特图 （ 是在 20 世纪初由亨利甘特开发的。他基本上是一种线条图，横轴表示时间，纵轴表示机器。甘特图直观地表明任务计划在什么时候进行，以及时机进展与计划要求的对比。图 3 个工件 3个机器面向机器的甘特图 ，每个方框代表特定的工序 。 第二章 作业加工调度问题及相关算法 11 图 分离图表示 分离图是描述 常用工 具，对于 n 个工 序 ， m 台机器（共 N 个工 件 ）的应的分离图为 G=(V,A,E)。其中， V 为所有 工件 构成的定点集，包括 j 两个虚拟 工件 （分别表示加工开始和结束）； A 为 n 条子边构成的边集，子边（实线）表示某工件按时约束条件在所有机器上从开始到结束的加工路径； E 为 弧（虚线）表示同一机器上加工各 工件 的连接。图 4机器 3 个工件表示的 离图表示。 图 最大完成时间为指标，则对 求解就归结为到各弧上作为优先决策的13 2 1 间 机器 基于新的动态邻域算法的车间调度问题的研究 12 各 工件 的一组顺序，当同一机器上有很多个 工件 出现冲突时，上述顺序用于决定各 工件 的先后，最终得到各 工件 间没有冲突的一个有向非循环图，其关键路径长度既为最大完成时间。 但是如果在分离图中产生一个回路，则这个解是无效解。那么必定有个有一个 前一个操作在它的后一操作之后做，则这样的解是不可用的，并且在我们的算法中尽量的避免这种情况的出现，如图 是一个实例在这个分离图中我们可以明显的看到一个回路（如加黑实线所示），也就是不可行解。 图 复杂性 算法的时间和空间复杂性对计算机的求解能力有重大影响。算法对时间和空间的需要量成为算法的时间复杂性和空间复杂性。 经典的 题， m 机器的 度问题共有 （ n!） m 个可能解，即 6 工件 6 机器的 6！） 6 =1017 个可能解。 态邻域算法 态邻域 搜索 ） 的基本思想是在搜索中改 动态邻域 从而找出更优解。 收益是通过一个下降方法向局部最小值系统地或随机的搜索，从而增加解的邻域。每次局部 优化时 ，在目前邻域范围内的一个或几个点被用来 作为初始解。当且仅当找到一个新的更优解时，这个方法从现第二章 作业加工调度问题及相关算法 13 有解跳到一个新解。因此， 是一个跟随轨迹的方法（如模拟退火或禁忌搜索） ， 并没有具体规定禁止动作。在这一章节中，我们将介绍该算法。 一个优化问题，包括寻找对于一个任意给定的 X 的实数方程 f 的最小值或最大值。如果这是一个最小化的问题，它可以如下定义：