涉及面非常广泛，所以有很多种调度问题。

根据加工系统的复杂度，生产调度可以分为单机调度调度调度调度多机器并行加工调度等几个基本类型。

单机调度是指所有的操作任务都在台机器上完成，需要对任务进行优化排队调度是最般的调度类型，它是指由台不同的机器加工个有特定加工路线顺序的工件，不同工件的工序间没有顺序约束，工序加工不能中断。

调度假设所有工件都在同样的设备因此，用近似的方法求解具有难度局部搜索部分后项插入局部搜索部分的交换中和的组成结构新动态邻域算法的结束条件的流程图第四章改进的动态邻域算法的分析模拟环境各种启发式算法的的比较第五章全文总结及展望主要工作总结及创新未来的研究方向致谢语附录第章绪论第章绪论自然界中存在类问题，被人们称之为难问题。

由于精确求解这类问题所花费的时间与问题实例的规模成指数型函数关系，因此为计算出规模不大如不超过的问题实例的解这类问题所花费的时间与问题实例的规模成指数型函数关系，因此为计算出规模不大如不超过的问题实例的精确解，即使用当今最快的电子计算机往往要用去宇宙的剩余年限。

绪论自然界中存在类问题，被人们称之为难问题。

附录第章绪论第章部分内容简介邻域结构关于振动邻域结构的推论中局部搜索操作的邻域结构中局部搜索操作的邻域结构局部搜索部分前项插入基于新的动态邻域算法的车间调度问题的研究局部搜索部分后项插入局部搜索部分的交换中和的组成结构新动态邻域算法的结束条件的流程图第四章改进的动态邻域算法的分析模拟环境各种启发式算法的的比较第五章全文总结及展望主要工作总结及创新未来的研究方向致谢语附录第章绪论第章绪论自然界中存在类问题，被人们称之为难问题。

由于精确求解这类问题所花费的时间与问题实例的规模成指数型函数关系，因此为计算出规模不大如不超过的问题实例的精确解，即使用当今最快的电子计算机往往要用去宇宙的剩余年限。

因此，用近似的方法求解具有难度的问题是有现实价值和理论意义的。

本论文针对个具体的难问题即作业加工调度问题提出近似的求解方法动态邻域算法。

我们所研究的作业加工调度问题是组合最优化问题之。

在介绍动态邻域算法的研究结果之前，本章将综合扼要介绍组合最优化问题计算复杂性理论启发式方法和作业加工调度问题，并说明本课题的来源及其研究意义。

研究的背景与意义生产调度，即对生产过程进行作业计划，作为个关键模块，是整个先进生产制造系统实现管理技术运筹技术优化技术自动化与计算机技术发展的核心。

有效的生产调度方法和优化技术的研究和应用，是实现先进制造和提高生产效益的基础和关键。

从上个世纪年代起，调度问题的研究就受到应用数学运筹学工程技术等领域科学家的重视，科学家们利用运筹学中的线性规划整数规划目标规划动态规划及决策分析方法，研究并解决了系列有代表意义的调度和优化问题。

但是，人们普遍把，和三人有关调度的研究工作作为调度理论研究的正式开始，他们人也被人们称为调度理论的奠基人。

此后多年的调度理论和应用研究都受到他们的影响。

调度问题涉及面非常广泛，所以有很多种调度问题。

根据加工系统的复杂度，生产调度可以分为单机调度调度调度调度多机器并行加工调度等几个基本类型。

单机调度是指所有的操作任务都在台机器上完成，需要对任务进行优化排队调度是最般的调度类型，它是指由台不同的机器加工个有特定加工路线顺序的工件，不同工件的工序间没有顺序约束，工序加工不能中断。

调度假设所有工件都在同样的设备上加工，并有致的加工操作和加工顺序。

多机器并行加工调度是指多台机器并行加工工件，而且并行加工的机器和工件都是类似的。

实际的调度问题通常是上述几种调度类型的组合。

基于新的动态邻域算法的车间调度问题的研究本文主要研究求解调度问题。

主要对工场内的作业进行组织调度和管理。

而工场以完成大量的作业为其基本特征，以组织生产过程，合理利用设备生产出产品或配件为其主要目的，这些产品通常有种或多种不同的处理方式或过程。

每种过程又是由系列工序所组成。

这些工序将占用定的资源并需要在机器上持续定的时间。

对每种产品的生产，其相关的工序又要按照定的次序进行。

求解调度问题即是要确定系列工序的前后顺序起始时间及占用的资源等并满足定的要求。

这些要求主要包括机器闲置与劳动力的费用调度过程中库存中的费用交货日期等等。

调度问题不仅是，还被认为是最难的组合最优化问题之。

解决工业生产经济管理交通运输和网络通讯等诸方面的些问题，都要借助于求解这个问题。

因此，优质快速地求解调度问题，既有重要的理论意义，又能带来巨大的经济效益。

组合最优化问题随着计算科学理论的发展和科学技术的不断提高，人类对组合最优化问题的认识与研究不断加深，而且解决这种问题的技术也在不断改进。

目前的研究认为，组合最优化问题是研究些具有约束条件的问题的最优解它的存在性和当它存在时求解它的方法，通常的表现为对于给定的具体问题，研究如何从众多的可行的解决方案中选出种意义下的最优的解决方案。

我们知道，组合最优化问题研究的对象是离散的事件，下面是被人们广泛接受的它的形式化的定义。

定义组合最优化问题。

在给定的约束条件下，求目标函数最优值最大值或最小值的问题称为组合最优化问题。

组合最优化问题的个实例可以表示为个偶对其中解空间是可行解的集合，目标函数是个映射，定义为式求目标函数的最小值的问题称为最小化问题，记为∈式求目标函数的最大值的问题称为最大化问题，记为∈式很明显，在形式上只要改变目标，，将被用到给出的振动中。

算法图之前的两个算法中，我们说明了如何利用寻找局部最优值和为了搜索接近进优化解而找到有其他的有潜力去寻找全局最优解的区域。

为了两个任务合并找到个初始解。

重复下面的序列直到不再获得提高设定重复下步骤直到对于找到最好的邻域值如果所得到的解较更优，设定以及否则设定找到个初始解选择个停止条件重复下序列直到到达停止条件设定重复以下步骤直到振动。

从中取出随机解如果解优于现任，移动同时继续搜索否则，设定第二章作业加工调度问题及相关算法我们引出了般动态邻域搜索算法我们先讨论找到的局部最优值如何结合局部搜索和系统邻域的变换。

于是图我们得到了基本的算法。

在这里，假设被用于所给振动的邻域结构，。

方法图的伪代码如果用代替简单的局部搜索，而且初始解用进行加强，就得到般动态邻域搜索算法见图，邻域结构，被用于振动的邻域结构，同时邻域结构，则被用于局部搜索的邻域结构。

找到个初始解选择个停止条件重复下序列直到到达停止条件设定重复以下步骤直到振动。

从阶邻域的中随机生成个点局部搜索。

应用些局部搜索方法，以作为初始解，以表示得到的局部最优解是否移动。

如果解优于现任，移动同时继续搜索否则，设定基于新的动态邻域算法的车间调度问题的研究算法图转换瓶颈算法转换瓶颈算法的原理转换瓶颈算法是种很有效的启发式算法。

等人对作业加工调度问题具有了深入的洞察，在总结以往的启发式算法的基础上提出的种新的构造问题可行解的方法，这种方法还有赖于对实践经验的总结。

事实上，将所有的机器台台地排序后是可能得到个可行的调度的，这里所说的给台机器排序指的是为由该机器加工的全部工件确定个加工次序。

这个方法采用的经验思想是为工业应用与管理设计个系统时，该系统性能的高低常常依赖于系统是否合理利用了稀有资源。

具体地说转换瓶颈算法也就是由连续用算法来台台地解决单机排序调度问题的组成。

令为所有机器的集合，是排好序的机器的集合。

在算法的每步中，从未排好的机器中通过用解决单机排序问题来选择台机器做瓶颈机，并将其加入。

每次新机器被加入的，对所有已经排好序的机器做局部再优化，局部再优化的方法是对它们中的每台机器用算法解单初始化找到个初始解同时用加强迭代重复下序列直到到达停止条件设定重复以下步骤直到振动。

从阶邻域的中随机生成个点用局部搜索。

设定并重复以下步骤直到在中找到的最佳邻域如果设定和否则设定应用些局部搜索方法，以作为初始解，以表示得到的局部最优解是否移动。

如果解局部最优优于现任，移动同时继续搜索否则，设定第二章作业加工调度问题及相关算法机调度问题，同时保持其它机器中的次序不变。

机器在分离图中相应的选择为，。

单机排序问题，是将中每台机器用替代，并将∈中的每条边删去而得到的问题。

，可以描述为式而实际中解决的单机调度问题是而不是，。

，的描述如下式其中是在机器上加工的工件的集合，是从节点到节点的最短路径的长度。

问题，的约束条件可以从问题，的约束条件中导出，但只用了的部分约束条件，工件之间可能存在的约束条件被忽略了。

在转换瓶颈算法中是用算法来解决的。

算法中用到了算法，算法的描述如下令为已经调度的工件的集合，为所有的其它工件的集合。

。

在时刻，从就绪工件中∈且中选择值最大的工件加工。

。

，。

若则算法结束否则跳到。

算法是基于算法和下面的定理。

令为算法得到的。

定理若该调度不是最优的调度，则存在关键工件和关键集，使得因此从调度到最优解的差距小于而且在最优调度中，工件要么是在中所有工件之后加工，要么是在中所有工件之前加工。

基于新的动态邻域算法的车间调度问题的研究定理若该调度是最优的，则存在使得。

若存在，则