柔性作业车间调度优化的改进模拟退火算法

Modified simulated annealing algorithm for flexible job-shop scheduling problem

针对柔性作业车间调度问题,提出一种改进模拟退火算法来进行求解。该算法引入粒子群算法中的基于位置取整和基于轮盘赌两种个体编码方法,并采用3种不同的局部搜索方法来构造个体的邻域结构。算例计算表明,改进模拟退火算法在求解柔性作业车间调度问题时,比粒子群算法、混合粒子群算法以及模拟退火算法具有更好的求解性能,其中采用轮盘赌编码时,算法的求解性能要优于采用位置取整时的求解性能,且基于互换的局部搜索方法要优于其他两种局部搜索方法,能更有效地改善算法的求解性能。

A modified simulated annealing algorithm was put forward to resolve the flexible job-shop scheduling problem,which used two kinds of individual encoding method respectively based on particle position rounding and roulette probability assignment in particle swarm algorithm.Three different local search methods were employed to constitute the neighborhood structure.The computational results show that the modified simulated annealing algorithm is more effective than particle swarm algorithm,hybrid particle swarm algorithm and simulated annealing algorithm in resolving the flexible job-shop scheduling problem.Compared with the position rounding encoding method,the rouletteprobability-assignment-based encoding method can render the algorithm more effective,and the local search method based on crossing-over operation is better than the other two search methods in improving the solving performance of the algorithm.