基于适应度地形理论的作业车间调度方法研究

发布时间：2018-07-07 16:12

本文选题：适应度地形 + Logistic模型　；参考：《华中科技大学》2012年硕士论文

【摘要】：作业车间调度是车间调度中一类典型的问题，其研究方法与成果已被运用于众多其它类型调度问题以及实际的生产运作中，针对作业车间调度问题的特性研究和算法设计具有重要的意义。本文从适应度地形理论出发，从搜索空间地形的分布和结构两方面来探讨作业车间调度问题的本质特性和影响因素，并据此设计出高效的调度优化算法。本文首先提出了基于Logistic模型的适应度地形研究方法，，该模型能有效地区分不同的问题实例。在使用该方法来研究问题基本属性对适应度地形分布特性的影响中发现：问题的形状约束会对地形分布产生巨大影响，随着工件数对机器数比例的提升，问题的求解难度会呈现“易—难—易”的变化规律，问题加工路径约束的增多会使地形崎岖而难求解，而加工时间的影响比较微弱。实例测试表明，该方法相比以往研究方法能更好地反映问题的适应度地形特性。接着使用局部搜索算法来研究问题适应度地形的结构特征，发现个体的搜索过程也会出现Logistic式的分布规律。分别使用2点交换邻域和关键路径插入邻域的局部搜索算法来研究问题基本属性对适应度地形结构特性的影响，结果表明：加工路径约束会对地形结构中盆地与峡谷的比例和性质产生较大影响，而形状和规模并未改变地形的结构性质。两种邻域策略所表现出来的不同地形结构特征，则为算法的设计提供了思路。基于前述研究结论，本文在广义粒子群优化模型框架下提出了粒子群优化与变邻域搜索的混合算法。使用本文提出的Logistic模型来挑选高效的邻域组合策略，结果表明，基于交换的随机全邻域和基于插入的N5邻域具有较好的组合效果。实例测试表明，该混合算法效果要优于单一的邻域搜索，LA系列的40个实例中，有38个可以求得最优解，验证了所提出的算法的优越性。文章最后对全文进行总结，并对作业车间调度和适应度地形的研究进行了展望。
[Abstract]:Job shop scheduling is a typical problem in job shop scheduling. Its research methods and achievements have been applied to many other scheduling problems and practical production operations. It is of great significance to study the characteristics and algorithm design of job shop scheduling problem. Based on the fitness terrain theory, this paper discusses the essential characteristics and influencing factors of job shop scheduling problem from the distribution and structure of search space terrain, and designs an efficient scheduling optimization algorithm. In this paper, we first propose a method for the study of fitness terrain based on Logistic model, which can effectively distinguish different problem cases. It is found that the shape constraint of the problem has a great influence on the topographic distribution with the increase of the number of jobs to the number of machines, and the effect of the basic properties of the problem on the distribution of the terrain is studied by using this method. The difficulty of solving the problem will present the law of "easy-difficult-easy". The increase of the constraint of processing path will make the terrain difficult and difficult to solve, but the influence of processing time is weak. The experimental results show that the proposed method can better reflect the fitness of the problem than the previous methods. Then the local search algorithm is used to study the structural characteristics of the fitness terrain and it is found that the logistic distribution is also found in the individual search process. The local search algorithms of 2-point exchange neighborhood and critical path insertion neighborhood are used to study the effect of the basic properties of the problem on the fitness of terrain structure. The results show that the processing path constraint has a great influence on the ratio and nature of the basin to the canyon in the topographic structure, but the shape and size have not changed the structural properties of the terrain. The different topographic structure features of the two neighborhood strategies provide ideas for the design of the algorithm. Based on the above conclusions, a hybrid algorithm of particle swarm optimization and variable neighborhood search is proposed under the framework of generalized particle swarm optimization (GPSO) model. The Logistic model proposed in this paper is used to select an efficient neighborhood combination strategy. The results show that the commutation-based random whole neighborhood and the inserted N5 neighborhood have better combination effect. The test results show that the hybrid algorithm is better than the 40 examples of single neighborhood search la series, and 38 of the 40 examples can obtain the optimal solution, which verifies the superiority of the proposed algorithm. In the end, the thesis summarizes the whole paper and looks forward to the study of job shop scheduling and fitness terrain.
【学位授予单位】：华中科技大学
【学位级别】：硕士
【学位授予年份】：2012
【分类号】：TH186

【参考文献】