基于新的动态邻域算法的车间调度问题的研究

《基于新的动态邻域算法的车间调度问题的研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、基于新的动态邻域算法的车间调度问题的研究摘要作业加工调度问题是NP难的，被认为是最难的组合优化问题乞一。在解决工业生产、经济管理和网络通讯等诸多问题时，都要涉及求解这个问题。优质、快速地求解作业加工调度问题，既有重要的理论意义，又能带来巨大的经济效益。转换瓶颈算法是解决作业加工调度问题的最有效的算法Z-,本论文屮用转换瓶颈算法来产生问题的初始值，进而提高搜索效率。动态邻域算法的基本思想是利用两个主要工具“shake（振动）”和“localsearch（局部搜索）”,局部搜索用于探索一个更为优的结果，振动使局部最小

2、跳入它的下一个邻域，从而继续进行局部搜索。本论文是依据这个基本思想研究和分析并进行改进，提出一个新的算法。为了提高振动的效率，我们根据卡里尔定理［⑴和格拉博夫斯基定理⑺提出了六个推论，以避免无用的局部邻域结构的切换，并且提出了新的邻域结构，即：“向前插入”，“向后插入”，“直接交换”。同时把振动分为“正常振动”和“贪婪振动”。实验表明基于六个推论，振动更加有驱动力。基于新的邻域结构，可以找到更好的某个点的邻域最小值。关键词：作业加工调度NP难问题启发式动态邻域算法目录上d-^^3"V匕1」研究的背景与意义1.2组

3、合最优化问题1.3实际难解性和NP完全问题1.4丿J1.4.1启发式方法的性能评价……1.4.2常用的启发式算法1.5木文的主要内容和结构第二章作业加工调度问题及相关算法・・2」作业加工调度问题的描述2.2JSSP的模型2.2.12.2.2JSSP的甘特图表示JSSP的分离图表示JSSP的复杂性…•…2.2.32.3动态邻域算法2.4转换瓶颈算2.4.1转换瓶颈算法的原理2.4.2转换瓶颈算法流程图第三章动态邻域算法的改进及其设计3」作业车间调度模型的建立3」」符号说明3.1.2"j**作业车间调度的编码问题IV

4、NS中生成初始解的方法IVNS中振动操作的邻域结构3.4.1振动操作的邻域结构3.4.2关于振动邻域结构的推论3.5IVNS中局部搜索操作的邻域结构••…351IVNS中局部搜索操作的邻域结构3.3.2VNS局部搜索部分前项插入3.23.33.4•••••••1•••••••1••••••••3••••••••■••••••••••••••••••••••••••••••••10111212•••••••••1•••••••••119••••••••1••••••••121••••••••••••••••22.2

5、4••••••••■25.29.293.3.3VNS局部搜索部分后项插入303.3.4VNS局部搜索部分的交换313.6IVNS中shake和localsearch的组成结构333.7新动态邻域算法的结束条件343.8IVNS的流程图35第四章改进的动态邻域算法的分析374.1模拟环境374.2各种启发式算法的MakeSpan的比较37第五章全文总结及展望415」主要工作总结及创新415.2未来的研究方向42References43附录47第一章绪论自然界中存在一类问题，被人们称之为NP难问题。由于精确求解这类问

6、题所花费的时间与问题实例的规模成指数型函数关系，因此为计算击规模不大（如不超过1000）的问题实例的精确解，即使用当今最快的电子计算机往往要用去宇宙的剩余年限。因此，用近似的方法求解具有NP难度的问题是有现实价值和理论意义的。木论文针对一个具体的NP难问题即作业加工调度问题提出近似的求解方法—动态邻域算法。我们所研究的作业加工调度问题是组合最优化问题之一。在介绍动态邻域算法的研究结果之前，木章将综合、扼要介绍组合最优化问题、计算复杂性理论、启发式方法和作业加工调度问题，并说明木课题的来源及其研究意义。1.1研究的

7、背景与意义生产调度，即对牛产过程进行作业计划，作为一个关键模块，是整个先进生产制造系统实现管理技术、运筹技术、优化技术、自动化与计算机技术发展的核心。有效的牛产调度方法和优化技术的研究和应用，是实现先进制造和提高牛产效益的基础和关键。从上个世纪50年代起，调度问题的研究就受到应用数学、运筹学、工程技术等领域科学家的重视，科学家们利用运筹学中的线性规划、整数规划、目标规划、动态规划及决策分析方法，研究并解决了一系列有代表意义的调度和优化问题。但是，人们普遍把Conway,Maxwell和Miller三人有关调度的研

8、究工作〔⑺作为调度理论研究的正式开始，他们3人也被人们称为调度理论的奠基人。此后30多年的调度理论和应用研究都受到他们的影响。调度问题涉及面非常广泛，所以有很多种调度问题。根据加工系统的复杂度，生产调度可以分为单机调度、Jobshop调度、Flowshop调度、Openshop调度、多机器并行加工调度等几个基木类型。单机调度是指所有的操作任务都在一台机器上完成，需要对任务