【作者】 宋存利；

【导师】 刘晓冰； 王伟；

【作者基本信息】 大连理工大学 ， 控制理论与控制工程， 2011， 博士

【摘要】 随着经济全球化的深入和科学技术的发展,制造企业面临的外部环境越来越复杂多变,如市场变化迅速、竞争加剧、客户多样化等等。生产调度问题作为制造系统的一个核心问题,优良的调度结果可以帮助企业缩短生产周期、提高生产效率、增强竞争力,因此对调度问题的研究具有重要意义。生产调度问题类型很多,这些问题中大多数都属于NP问题。为此,研究者们多年来不断寻求求解这类问题的最优化方法。近年来,一些群体智能优化方法(如遗传算法、进化规划、差分算法、微粒群算法、蚂蚁算法等)以及一些邻域搜索算法(如模拟退火算法、禁忌搜索算法)的发展,为人们研究生产调度问题提供了新的思路和手段,同时各种智能算法的有效混合也成为人们研究的热点。基于此,本文对生产调度问题及其优化算法展开了如下几个方面的研究：针对以最小化最大完工时间为目标的Job-shop调度问题,提出了一种混合微粒群算法(Hybrid Particle Swarm Optimization Algorithm, HPSO)。该算法采用基于工序的随机键编码方式对微粒编码,同时提出了一种改进的活动调度解码算法对微粒解码。鉴于微粒群算法具有较强的全局寻优能力和差的局部搜索能力,将3种不同邻域结构的模拟退火算法随机与微粒群算法相结合,针对每个微粒找到的当前最好解利用模拟退火算进行局部寻优,提高算法的局部搜索能力。最后实验表明了该算法对大多数经典调度问题的有效性。在总结无等待流水调度问题一般规律的基础上,提出了基于邻域迭代的搜索算法。该算法利用相邻工件间的开工时间距离求解最小化最大完工时间,同时利用两确定工件相邻加工时其开工时间距离是常量这一特点,对邻域解采用增量计算,将算法的时间复杂度降了一阶。同时将变邻域搜索思想应用在算法设计中,避免算法陷入局部最优。实验表明该算法对大规模无等待流水调度问题有较高的求解效率和求解质量,比较适应生产实际。研究了柔性Job-shop调度问题,提出解决该问题的混合微粒群优化算法HPSO,该算法对设备分配和工序排序调度采用不同的编码方法和更新公式,为了提高算法效率,用基于设备的初始化方法和基于工件序列的初始化方法来提高HPSO初始种群的质量。同时提出了4种采用不同邻域搜索策略的模拟退火算法,并将它与PSO算法进行随机混合,提高了算法的局部搜索能力,最后实验表明了HPSO的有效性。考虑到设备分配与工件排序之间的强耦合性,传统的微粒群求解模式有可能在微粒运动过程中破坏gbest的优化模式,提出了协同进化的微粒群优化算法,该算法将设备选择和工件调度分别作为两个寻优变量,分别利用PSO算法寻优,并根据两个变量的内容进行互相评价,最终获得一个将设备选择和工件调度相结合的最好调度结果。最后实验表明该算法较HPSO算法对柔性Job-shop问题的寻优质量具有明显的优势。在对一些混合算法研究的基础上,通过对迭代搜索算法组成元素、寻优机理、静态算法混合模式、算法混合知识的描述及数据库存储模式等研究,提出了迭代搜索的算法框架及混合算法框架,并采用多代理技术予以实现,最后实验证明本策略的有效性。更多还原

【Abstract】 With the globalization of economy and the development of science and technology, the external environment of manufacturing enterprises becomes more and more complex and volatile, such as rapid market changes, increased competitions and more personalized and diverse customer needs. Production scheduling problem is a core issue of manufacturing system. A good scheduling can shorten the production cycle; improve enterprises’production efficiency and raise enterprises’competitiveness. Therefore, the research on the scheduling problem is important.There are many types of production scheduling, most of which are NP problems. Researchers have been working hard over the years to try to work out an optimal method to solve these problems. In recent years, with the development of some swarm optimization algorithms (such as genetic algorithm, evolutionary programming, differential algorithm, particle swarm optimization and ant colony algorithm, etc) and some neighborhood search algorithms (such as simulated annealing, taboo search etc.), new ideas and means were available for people to solve the production scheduling problems. At the same time many scholars begin to research these algorithms to solve scheduling problem. Based on the above mentioned, this dissertation aims to discuss the following aspects.A hybrid particle swarm optimization algorithm(PSO) is proposed to minimize the completion time of the job shop problem. In this algorithm, the particle is encoded with random key and an improved decoding algorithm is proposed to produce active scheduling. Since particle swarm optimization has a strong global search ability and a poor local search ability, in order to improve the local search ability of PSO, three simulated annealing algorithms which are based on different neighborhood structures are proposed and hybrid with PSO. At last, the computational results show the effectiveness of the algorithm.A hybrid particle swarm optimization algorithm (HPSO) is proposed to solve the flexible job shop scheduling problem(FJSP). In the algorithm, different encoding methods were proposed for assignment and sequence. In order to ensure the legitimacy of code for assignment, the updating formula of particles is changed. In order to improve the efficiency of algorithm, the initialization algorithm based on device and sequence is proposed to improve the quality of the initial population of HPSO. In order to improve the local search ability of algorithm, four SA algorithms based on different neighborhood search strategy are proposed and mixed with PSO. At last, the computational results show the effectiveness of the algorithm. Taking into account the strong coupling between assignment and sequence, co-evolution particle swarm optimization algorithm is proposed to solve FJSP. In the algorithm, assignment and sequence are treated as two variables. PSO algorithm will optimize them respectively and estimate them according each other. The computation results show that CPSO is better but slower than HPSO in the optimal.A new method using the distance of adjacent jobs for calculating makespan is proposed to large-scale no-wait flow shop scheduling. At the same time, an iterative neighborhood search algorithm is put forward. Since it reduces the time complexity, the efficiency is greatly improved. In order to avoid falling into local optimum, variable neighborhood search algorithm is used. As a result, the probability of finding the global optimal solution is enhanced. The computation results show that the algorithm for large-scale no-wait flow-shop scheduling is very practical and the solution is better.Based on the research of some hybrid computations, optimization mechanism, model of static hybrid algorithm, description and storage mode of algorithm knowledge for iterative search algorithm, the framework of iterative search algorithm and hybrid algorithm based on iterative algorithm is proposed. At last, the multi-agent technology is used to achieve it and the simulation experiment suggests the effectiveness and adaptability of the system.更多还原