【作者】 卫鑫；

【导师】 武波； 藤村茂；

【作者基本信息】 西安电子科技大学 ， 软件工程， 2009， 硕士

【摘要】 作业加工调度问题是NP难的,被认为是最难的组合优化问题之一。在解决工业生产、经济管理和网络通讯等诸多问题时,都要涉及求解这个问题。优质、快速地求解作业加工调度问题,既有重要的理论意义,又能带来巨大的经济效益。转换瓶颈算法是解决作业加工调度问题的最有效的算法之一,本论文中用转换瓶颈算法来产生问题的初始值,进而提高搜索效率。动态邻域算法的基本思想是利用两个主要工具"shake(振动)”和"local search(局部搜索)”,局部搜索用于探索一个更为优的结果,振动使局部最小跳入它的下一个邻域,从而继续进行局部搜索。本论文是依据这个基本思想研究和分析并进行改进,提出一个新的算法。为了提高振动的效率,本文根据卡里尔定理和格拉博夫斯基定理提出了六个推论,以避免无用的局部邻域结构的切换,并且提出了新的邻域结构,即：“向前插入”,“向后插入”,“直接交换”。同时把振动分为“正常振动”和“贪婪振动”。实验表明基于六个推论,振动更加有驱动力。基于新的邻域结构,可以找到更好的某个点的邻域最小值。更多还原

【Abstract】 The job shop scheduling problem is not only NP hard problem, but also regarded as one of the most difficult combinatorial optimization problems as well. It is well known that the problems in those fields of industrial production, economic management, network communication and cryptography etc. make direct appeal to this problem. Therefore, solving the job shop scheduling problem efficiently and effectively will make a great of economic benefits. Job shop scheduling problem is well known to be a difficult, strongly NP—complete problem, the objective of this is minimizing the completion time of all the jobs, called the make span, subject to the constraints of this kind of problem.The Shifting Bottleneck Procedure (SBP) proposed by Adams, Balas& Zawack is an effective heuristic method for solving the job shop scheduling problem. In my research, the SBP will be using to generate the initial solution. Our purpose is to cut down the executing time. Variable Neighborhood Search is a recent meta-heuristic for solving combinatorial and global optimization problems. Its basic idea is the systematic change of neighborhood within the local search. In an ordinary VNS algorithm two main functions’shake’and’local search’play an important role. Local search explores for an improved solution within the local neighborhood, while shake diversifies the solution by switching to another local neighborhood. In the related study, resultant effectiveness and computational efficiency still remain challenging task.In this thesis, in order to improve the efficiency of shake function we proposed 6 propositions to avoid useless neighborhood structures in Exchange, Forward-Insert, Backward-Insert, moreover divide the shake function to normal shake and intensified shake. In the experiments, it is showed that based on the above 6 propositions, the shake function is more driving when trapped in the local optimum. In our experiment, if the random solution was adopted, it is always taking more time while obtain a same final result.更多还原