【作者】 李莉；

【导师】 王克奇；

【作者基本信息】 东北林业大学 ， 机械设计及理论， 2011， 博士

【摘要】 随着日益加剧的全球市场竞争,为满足客户多样化及个性化的需求,提高客户满意度,缩短生产加工周期以及按时交货,进而提高自身竞争力,企业需要制定合理的车间生产调度方案。增加了路径柔性特点的作业车间调度系统变得更加灵活,这也使柔性作业车间调度问题成为最困难的组合优化问题之一。根据实际生产需要,柔性作业车间调度问题常常需要针对多个目标制定优化决策。因此,对多目标柔性作业车间调度问题的求解方法进行深入研究具有重要的理论意义与实际应用价值。本文主要研究对群智能优化算法进行改进、融合,并将其应用于解决柔性作业车间调度问题,主要完成了以下方面的研究：对基本蚁群优化算法进行了改进,将其应用于解决单目标柔性作业车间调度问题。在改进的蚁群优化算法中,完成了对路径构造中的邻域搜索方法的设计。算法中,子集的数量由所调度问题包含的工件数量决定。为了避免过早停滞现象的发生,算法对启发式信息采用了轨迹强度蒸发规则。本文分析了改进型蚁群优化算法中的相关参数,并以平衡全局搜索能力、算法收敛性为目标,在充分考虑了所解决问题规模的前提下进行了算法参数的设置。通过对算法进行仿真实验获取了较为满意的调度结果。通过对多目标FJSP数学模型和优化方法的研究,在改进的蚁群优化算法基础上通过对算法中局部启发式信息的重新设计,以均衡加工周期最小化、机器总负载最小化和关键机器负载最小化为问题优化目标,进一步完成了蚁群优化算法的改进,并将其应用于解决多目标FJSP,通过实验证明了该算法的有效性。对传统PSO算法进行了改进,并将其应用于解决单目标和多目标柔性作业车间调度问题。在改进的PSO算法中,利用种群进化原理并引入基于混沌的自适应参数策略来提高算法的全局搜索能力,采用基于混沌策略的局部搜索来提高算法的局部搜索能力。改进后的算法在一定程度上对传统PSO算法所存在的容易陷入局部极值的问题进行了改善,从而使算法的解质量、搜索效率和收敛速度都得到了提高。最后利用具有27道工序的8×8部分FJSP和具有30道工序的10×10完全FJSP这两个标准测试实例对该算法的求解性能进行了实验测试。为克服单一优化算法在解决复杂调度问题中固有的弊端,本文将蚁群优化和粒子群优化两种算法加以有效融合,从而增强整体搜索能力。针对多目标FJSP特点,在分别完成了对蚁群优化算法及粒子群优化算法改进工作的基础上,进一步提出二阶式蚁群粒子群混合优化算法(TSAPO)。在TSAPO中,采用分解方式通过两个阶段实现多目标优化。通过工序可选加工机器析取模型的建立,第一阶利用改进的蚁群算法,在对蚁群转移概率重新设计的基础上实现在多目标FJSP中机器总负载最小化与关键机器负载最小化的两个优化目标；第二阶通过对粒子群解码的设计,利用所改进的粒子群优化算法实现加工时间最小化的优化目标。通过仿真实验证明TSAPO算法在求解多目标FJSP中具有较好的求解性能。更多还原

【Abstract】 With global market competition intensified, in order to enhance the competitiveness, enterprises need to design reasonable scheduling schemes to satisfy demands of customer for diversification and personalization, improve customer satisfaction, shorten production cycle and deliver just-in-time. Job-shop scheduling system becomes more flexible with the enhancing of route flexibility, and it also makes flexible job-shop scheduling as one of the most difficult problems in combinatorial optimization problems. For the need of production, flexible job-shop scheduling problems usually make optimization decision according several objectives. So, it is of important theoretical value and practical significance to carry out deep research on effective methods for solving multi-objective flexible job-shop scheduling problem.In this dissertation, the improvement and fusion of swarm intelligent optimization algorithms are studied and these algorithms are applied to solve flexible job-shop scheduling problems. The main researches are as follows.The classical ant colony algorithm is improved and applied to solve single-objective flexible job-shop scheduling problem. In the improved ant colony optimization algorithm, the number of subsets is defined according to the number of jobs and the local search method in the period of path construction is designed. To avoid early stagnation state, rule of trail intensity update is adopt. The problem of parameters’setting is discussed. According to the scale of problem, reasonable parameters setting is given to balance capacity of global search and fast convergence. Satisfactory results are obtained through algorithm experiments.According to research on mathematical model and optimization method of multi-objective FJSP, further improvement for ant colony optimization algorithm is made based on the redesign of local heuristic information. The optimization objective of the improved algorithm is to obtain the balanced minimum of make span, total machine load and bottle-neck machine load. The algorithm is applied to solve multi-objective FJSP and validated by experiments.The traditional PSO algorithm is improved and applied to solve single objective FJSP and multi-objective FJSP. In he improved PSO algorithm, global research capacity of algorithm is enhanced by theory of population evolution and the strategy of self-adaptive parameters based on chaos. Local research capacity of algorithm is enhanced by importing local search based on chaos. The improved algorithm can reduce the possibility of falling into the local extremum for traditional PSO. Therefore the solution quality, search efficiency and convergence rate are all enhanced. Finally, capacity of the algorithm is validated by standard instances of8X8partial FJSP with27operations and10X10total FJSP with30operations.In order to overcome the shortcomings exist in simple optimization algorithm, a hybrid of ACO and PSO is designed to provide more powerful search capability. According to character of multi-objective FJSP, two stage ant particle optimization algorithm (TSAPO) is put forward on the basic of the previous improved ant colony optimization algorithm and the improved particle swarm optimization algorithm. In TSAPO, the multi-objective optimization is realized by decomposition method through two stages. In the ant colony optimization algorithm, through the processing machines’extract graph model, the minimum of workload for total machine and bottle-neck machine can be realized in the first stage on the basic of improved ant colony algorithm and the redesign of ants transfer probability. In the second stage, the minimum of make span is realized on the basic of improved particle swarm optimization algorithm and the design of decoding of particle swarm. Simulation experiments show TSAPO algorithm has a good solution performance in solving multi-objective FJSP.更多还原