【作者】 梁燕；

【导师】 王书锋；

【作者基本信息】 郑州大学 ， 控制理论与控制工程， 2009， 硕士

【摘要】 作业车间调度问题作为著名的机器调度问题之一,也是最困难的组合优化问题,在生产系统和工程应用中有着非常重要的意义,开发精确而有效的调度算法是近年来研究的热点。本文首先对确定性的作业车间调度问题进行了详细的描述,并在当前研究的基础上,结合生产实际情况,对生产中因各种随机因素的影响而产生的不确定性调度问题进行了研究。把不确定的加工时间和交货期分别用三角模糊数和梯形模糊数表示,同时考虑模糊加工时间和模糊交货期,以最大化平均满意度作为优化目标,建立了模糊作业车间调度模型。近年来,邻域搜索算法在作业车间调度问题中得到了广泛的应用,本文重点对其中的遗传算法进行了深入的研究。针对传统遗传算法在求解时存在早熟收敛和局部搜索能力差的缺点,本文采用两种改进方法来改善遗传算法的局部搜索能力,提高优化质量和搜索效率。算法一首先采用双种群相互指导进化的思想,既增加了种群的多样性又提高了算法的抗早熟能力,同时采用一种优差染色体相互的交叉方式来避免局部最优,并且对基于工序的编码方式设计了一种新的交叉算子,避免因交叉操作产生不可行解。将改进的遗传算法应用于确定性的作业车间调度问题中,通过对经典算例的仿真,验证了该算法的可行性和有效性。算法二采用遗传算法和模拟退火算法相结合的方法,利用模拟退火算法能概率性的跳出局部最优解的特性,让其承担遗传算法选择的压力,同时发挥遗传算法良好的全局最优特性,设计了一种性能优良的全局最优的混合优化算法。通过对模糊作业车间调度问题仿真,验证了该混合算法的有效性和实用性。更多还原

【Abstract】 Job-shop scheduling problem is one of the well-known machine scheduling, and also the most difficult combinatorial optimization problems. It plays a significant role in production systems and engineering applications. The development of accurate and effective scheduling algorithm has come into the focus of research in recent years.This dissertation firstly presents a detailed description of deterministic job-shop scheduling problem and then studies some uncertain scheduling problems arising in production due to a variety of random factors, with consideration of actual production processes. In this study, uncertain processing time and due date are denoted by a triangular fuzzy number and a trapezoid fuzzy number respectively, and at the same time factors like fuzzy processing time and fuzzy due date are considered. As a result, the model of the fuzzy job-shop scheduling problem is proposed, and the maximum average satisfaction is taken as the optimization objective.In recent years, local search method has been widely applied to job-shop scheduling problem. This dissertation is intended to make deep investigation into genetic algorithm. It employs two kinds of methods to promote the local search function of traditional genetic algorithm, to tackle such problems as premature convergence and poor local search function and in turn to better optimization quality and search efficiency.The first algorithm proposed, based upon the principle of mutually-guided evolution of two populations, not only increases the diversity of the population, but also improves the ability of resisting pre-maturity; at the same time, it uses the best and worst chromosome to crossover each other to avoid local optimum. And then for the operation-based representation, a new crossover operator is designed for avoiding unfeasible solution resulting from cross-operation. Application of the improved genetic algorithm in deterministic job-shop scheduling problems, and the simulation results of the classic example have proved the feasibility and effectiveness of the algorithm.The second algorithm proposed combines genetic algorithm with simulated annealing algorithm. Simulated annealing algorithm can probably circumvent the local optimal solution. The algorithm uses simulated annealing to bear the selection pressure of genetic algorithm, and uses the good global optimum characteristics of the genetic algorithm. The paper proposes a global optimal of the hybrid optimization algorithm. The simulations of fuzzy job-shop scheduling show the effectiveness and practicality of the hybrid algorithm.更多还原