【作者】 贾兆红；

【导师】 陈华平；

【作者基本信息】 中国科学技术大学 ， 管理科学与工程， 2008， 博士

【摘要】 传统的作业车间调度问题是求解每个工件具有特定加工机器的一类调度问题,而在实际生产中,可以加工某个工序的机器往往不止一个,这就产生了柔性作业车间调度问题。柔性作业车间调度问题(Flexible job shop scheduling problem,FJSP)由于具有路径柔性的特点,从而可以避免传统作业车间在正常运行过程中容易出现的阻塞和拥挤等现象,并且当加工过程中出现机器故障等一些异常情况的时候,作业车间系统仍然能够维持生产的继续进行,这样可以提高作业车间调度系统的灵活性。然而,柔性路径的特点也使得这类问题的可行解范围的增大,从而给问题的求解带来新的挑战。在实际生产中,柔性作业车间调度问题往往需要同时面向多个目标进行决策分析。因此,寻找有效的方法对多目标柔性作业车间调度问题进行求解具有重要的理论价值和应用意义。本文主要探讨了如何使用粒子群优化(Particle Swarm Optimization,PSO)算法求解柔性作业车间调度问题,特别是多目标柔性作业车间调度问题。本论文的主要工作与创新点如下:(1)研究了基于混沌的PSO算法在柔性作业车间调度问题中的应用。利用混沌优化技术的随机性、遍历性特点和易跳出局部极值的能力,在PSO算法中引入混沌技术以提高PSO算法的性能,提出了一种混合PSO算法。首先,利用混沌对PSO算法的参数进行自适应优化,实现全局搜索与局部搜索间的有效平衡;然后,在PSO算法的搜索过程中引入混沌局部搜索策略,以提高求解的精度和收敛速度。并且将该算法分别应用于若干个单目标和多目标柔性作业车间调度问题的求解,实验结果表明算法具有良好的全局搜索性能。(2)探讨了基于多目标权重聚合优化策略的PSO算法。在PSO和混沌的混合优化算法的基础上,针对多目标存在的量纲问题,采用一种基于模糊逻辑的适应度函数形式。同时,为了进一步保持种群的多样性,最大可能的搜索到所有的非劣解,利用随机思想生成适应度函数的权系数。实验表明这种方法使得算法获得的非劣解具有很好的分布行和稳定性。(3)研究了Fully-informed粒子群(FIPS)算法在多目标柔性作业车间调度问题中的应用。首先,基于Pareto最优概念对种群进行排序,同时将属于相同Pareto等级的个体定义为邻居,并将这种基于Pareto等级的近邻拓扑结构用于FIPS算法中。其次,通过计算同Pareto等级中个体的拥挤距离进行第二级排序,给出了一种基于排序的FIPS算法。最后,针对算法的早熟收敛问题,引入基于编码机制的两种变异算子。(4)研究了基于动态概率搜索机制的PSO算法在多目标作业车间调度问题中的应用。算法在搜索初期利用粒子近邻的平均最优代替传统的单个最优引导搜索,后期用Gaussian动态概率搜索来提高算法的局部开挖能力。然后,引入Pareto优的概念,采用精英集来存放非劣解,提出一种新的适应度值分配方法。此外,在算法中还引入了一种自适应的变异算子来增强解的多样性。实验结果表明本文提出的算法具有较好的搜索性能,是求解多目标柔性作业车间调度问题的一种可行方法。更多还原

【Abstract】 The traditional job shop scheduling problem is a kind of scheduling problems where each job is processed by a specified machine. But in practice, the job generally can be processed by more than one machine, which brings the flexible job shop scheduling problem.Since flexible job shop scheduling possesses the advantage of route flexibility, it can avoid the problem of jam-up and congestion in the traditional job shop. Meanwhile, the flexible routes can make the system proceed with the exception encountered in the manufacturing procedure such as machine failure. Therefore, the flexible routes are capable of enhancing the agility of the job shop scheduling system. However, this new feature enlarges the range of the available solutions for the flexible job shop scheduling problems and brings new challenges to the given problems. Moreover, making decisions on multiple objectives is often needed when solving and analyzing the flexible job shop scheduling problems in practice. Thus, seeking the effective methods to solve multi-objective flexible job shop scheduling problems is of important theoretical value and practical significance.This dissertation mainly discusses the application of the particle swarm optimization algorithm on flexible job shop scheduling problems, especially the multi-objective flexible job shop scheduling problems. The main and pioneering works of this dissertation are as follows:(1) Research on the particle swarm optimization algorithm based on chaos and its application in flexible job shop scheduling problems. As a new optimization technique, chaos bears randomicity, ergodicity and the superiority of escaping from a local optimum. By integrating the advantage of Chaos optimization and . particle swarm optimization algorithm, a hybrid particle swarm optimization algorithm is proposed. Firstly, parameters of particle swarm optimization algorithm are adaptively chaotic optimized to efficiently balance the exploration and exploitation abilities. Then, during the search process of particle swarm optimization algorithm, the chaotic local optimizer is introduced to raise its resulting precision and convergence rate. The algorithm is applied to solving the single objective and multi-objective flexible job-shop scheduling problems and the global search performance of the new algorithm is validated by the results of the comparative experiments.(2) Discussion of the multi-objective weighting composite optimization with particle swarm optimization algorithm, resulting in a multi-objective hybrid particle swarm optimization algorithm. Based on the combination of particle swarm optimization and chaos, a fitness function with fuzzy logic is proposed to evaluate the particles for the dimension problems of multiple objectives. Meanwhile, the weighting coefficients are randomly generated to further maintain the diversity of the population and find all the non-dominated solutions as more as possible. Experiments on four typical flexible job shop scheduling instances are presented to show the good distribution and stability of the non-dominated solutions found by the proposed approach.(3) Research on the application of the fully-informed particle swarm algorithm in the multi-objective flexible job shop scheduling problems. Firstly, the population is ranked based on Pareto optimal concept. And the neighborhood topology used in the fully-informed particle swarm algorithm is based on the Pareto rank. Secondly, the crowding distance of individuals is computed in the same Pareto level for the secondary rank. Thirdly, addressing the problem of trapping into the local optimal, two mutation operators based on the coding mechanism are introduced into our algorithm.(4) Research on the application of particle swarm optimization algorithm based on the dynamic probabilistic search in the multi-objective flexible job shop scheduling problems. At the earlier stage, the average of the neighboring best individuals instead of the general single one is employed in the algorithm to guide the search. In the latter stage, the next generation individuals’ positions are sampled from a Gaussian dynamic probabilistic distribution around the expected position of the particle at the next generation with the purpose of improving the local exploiting ability of our method. Then, borrowing ideas from Pareto optimization, the non-dominated solutions are stored by using an elitism repository, and a new fitness allocation approach is proposed. Meanwhile, the self-adaptive mutation operators are introduced to enhance the diversity of solutions. Finally, comparative experiments are conducted with several groups of flexible job shop scheduling instances. The experimental results show the better search ability of the algorithm, which indicates that the proposed algorithm is feasible in solving multi-objective flexible job shop scheduling problems.更多还原