绪论自然界中存在类问题，被人们称之为难问题。由于精确求解这类问题所花费的时间与问题实例的规模成指数型函数关系，因此为计算出规模不大如不超过的问题实例的精确解，即使用当今最快的电子计算机往往要用去宇宙的剩余年限。因此，用近似的方法求解具有难度的问题是有现实价值和理论意义的。本论文针对个具体的难问题即作业加工调度问题提出近似的求解方法动态邻域算法。我们所研究的作业加工调度问题是组合最优化问题之。在介绍动态邻域算法的研究结果之前，本章将综合扼要介绍组合最优化问题计算复杂性理论启发式方法和作业加工调度问题，并说明本课题的来源及其研究意义。研究的背景与意义生产调度，即对生产过程进行作业计划，作为个关键模块，是整个先进生产制造系统实现管理技术运筹技术优化技术自动化与计算机技术发展的核心。有效的生产调度方法和优化技术的研究和应用，是实现先进制造和提高生产效益的基础和关键。从上个世纪年代起，调度问题的研究就受到应用数学运筹学工程技术等领域科学家的重视，科学家们利用运筹学中的线性规划整数规划目标规划动态规划及决策分析方法，研究并解决了系列有代表意义的调度和优化问题。但是，人们普遍把，和三人有关调度的研究工作作为调度理论研究的正式开始，他们人也被人们称为调度理论的奠基人。此后多年的调度理论和应用研究都受到他们的影响。调度问题涉及面非常广泛，所以有很多种调度问题。根据加工系统的复杂度，生产调度可以分为单机调度调度调度调度多机器并行加工调度等几个基本类型。单机调度是指所有的操作任务都在台机器上完成，需要对任务进行优化排队调度是最般的调度类型，它是指由台次序不变。再次转化瓶颈排成否否是是用算法来解决单机排成问题，同时保持其他机器的拍成结果不变。根据产生的最大来判定瓶颈机器，同时保持的排成结果不变。是否超出次循环是是否图摘要作业加工调度问题是难的，被认为是最难的组合优化问题之。在解决工业生产经济管理和网络通讯等诸多问题时，都要涉及求解这个问题。优质快速地求解作业加工调度问题，既有重要的理论意义，又能带来巨大的经济效益。转换瓶颈算法是解决作业加工调度问题的最有效的算法之，本论文中用转换瓶颈算法来产生问题的初始值，进而提高搜索效率。动态邻域算法的基本思想是利用两个主要工具振动和局部搜索，局部搜索用于探索个更为优的结果，振动使局部最小跳入它的下个邻域，从而继续进行局部搜索。本论文是依据这个基本思想研究和分析并进行改进，提出个新的算法。为了提高振动的效率，我们根据卡里尔定理和格拉博夫斯基定理提出了六个推论，以避免无用的局部邻域结构的切换，并且提出了新的邻域结构，即向前插入，向后插入，直接交换。同时把振动分为正常振动和贪婪振动。实验表明基于六个推论，振动更加有驱动力。基于新的邻域结构，可以找到更好的个点的邻域最小值。关键词作业加工调度难问题启发式动态邻域算法目录目录第章绪论研究的背景与意义组合最优化问题实际难解性和完全问题启发式方法启发式方法的性能评价常用的启发式算法本文的主要内容和结构第二章作业加工调度问题及相关算法作业加工调度问题的描述的模型的甘特图表示的分离图表示的复杂性动态邻域算法转换瓶颈算法转换瓶颈算法的原理转换瓶颈算法流程图第三章动态邻域算法的改进及其设计作业车间调度模型的建立符号说明数学模型作业车间调度的编码问题中生成初始解的方法中振动操作的邻域结构振动操作的邻域结构关于振动邻域结构的推论中局部搜索操作的邻域结构中局部搜索操作的邻域结构局部搜索部分前项插入基于新的动态邻域算法的车间调度问题的研究局部搜索部分后项插入，‗‗如果用代替简单的局部搜索，而且初始解用进行加强，就得到般动态邻域搜索算法见图，邻域结构，被用于振动的邻域结构，同时邻域结构，则被用于局部搜索的邻域结构。找到个初始解选择个停止条件重复下序列直到到达停止条件设定重复以下步骤直到振动。从阶邻域的中随机生成个点局部搜索。应用些局部搜索方法，以作为初始解，以表示得到的局部最优解是否移动。如果解优于现任，移动同时继续搜索否则，设定基于新的动态邻域算法的车间调度问题的研究算法图转换瓶颈算法转换瓶颈算法的原理转换瓶颈算法是种很有效的启发式算法。等人对作业加工调度问题具有了深入的洞察，在总结以往的启发式算法的基础上提出的种新的构造问题可行解的方法，这种方法还有赖于对实践经验的总结。事实上，将所有的机器台台地排序后是可能得到个可行的调度的，这里所说的给台机器排序指的是为由该机器加工的全部工件确定个加工次序。这个方法采用的经验思想是为工业应用与管理设计个系统时，该系统性能的高低常常依赖于系统是否合理利用了稀有资源。具体地说转换瓶颈算法也就是由连续用算法来台台地解决单机排序调度问题的组成。令为所有机器的集合，是排好序的机器的集合。在算法的每步中，从未排好的机器中通过用解决单机排序问题来选择台机器做瓶颈机，并将其加入。每次新机器被加入的，对所有已经排好序的机器做局部再优化，局部再优化的方法是对它们中的每台机器用算法解单初始化找到个初始解同时用加强迭代重复下序列直到到达停止条件设定重复以下步骤直到振动。从阶邻域的中随机生成个点调度不是最优的调度，则存在关键工件和关键集，使得因此从调度到最优解的差距小于而且在最优调度中，工件要么是在中所有工件之后加工，要么是在中所有工件之前加工。基于新的动态邻域算法的车间调度问题的研究定理若该调度是最优的，则存在使得。若存在，则它是关键路径中满足﹤的最大的数，这里。算法是个分支限界的方法。树中每个结点对应于个单机调度问题及其下界。上界是目前已知的最好的调度的。分支考虑树中的结点，先用算法来解决单机问题。若不存在，则调度最优否则若考虑两个问题个是通过令，使得在中所有工件之前加工个是通过设置，使得在中所有工件之后的加工。若，则两个问题都作为结点加入树中。上界每次用算法的时候都比较该调度的与，若，则。如下图所示算法的流程图开始运行算法，把得到的作为，并记录排成的顺序确定关键排成路径是否每关键工件在关键路径上把归结到关键集合中，并计算新的是否小于，同时把排列在集合的最后面输出，和新的排成结果否否是是是否图第二章作业加工调度问题及相关算法转换瓶颈算法流程图转换瓶颈算法是由上节所述的算法和利用尽可能地优先使用稀缺资源的基本理念来形成的。下图是转换瓶颈算法的流程图。开始结束是否还有机器没有被安排排成把归结到已经被安排排成的机器集合中是否在机器集合中还有元素在的机器中，根据判定的瓶颈机的次序，逐个进行单机排成，并保持其他机器的排成用局部搜索。设定并重复以下步骤直到在中找到的最佳邻域如果设定和否则设定应用些局部搜索方法，以作为初始解，以表示得到的局部最优解是否移动。如果解局部最优优于现任，移动同时继续搜索否则，设定第二章作业加工调度问题及相关算法机调度问题，同时保持其它机器中的次序不变。机器在分离图中相应的选择为，。单机排序问题，是将中每台机器用替代，并将∈中的每条边删去而得到的问题。，可以描述为式而实际中解决的单机调度问题是而不是，。，的描述如下式其中是在机器上加工的工件的集合，是从节点到节点的最短路径的长度。问题，的约束条件可以从问题，的约束条件中导出，但只用了