求解Job Shop调度问题的粒子群算法研究

为解决单一粒子群算法求解Job shop调度问题存在的不足,提出一种基于交换序的混合粒子群算法,提高了这类问题的求解质量.在混合粒子群算法中,采用粒子群算法进行大范围全局搜索.根据Job Shop调度问题解的特征,提出基于关键工序的邻域选择方法,并将基于这种方法的禁忌搜索算法作为局部搜索算法,增强了粒子群算法的搜索能力.采用混合粒子群算法对13个难解的benchmark问题进行求解,在较短的时间内,得到的最优解和10次求解的平均值优于并行遗传算法和粒子群算法.由此说明本文所提出的混合粒子群算法是有效的.

Study on particle swarm algorithm for Job Shop scheduling problems

A hybrid particle swarm algorithm is proposed,which is used to make up for the deficiencies of resolving Job Shop scheduling problem and improve the quality of searching solutions.In the hybrid particle swarm algorithm,the particle swarm algorithm is applied to search in the global solution space.According to the characteristics of job shop solutions,a sort of selection method is proposed based on critical operation,and the taboo search algorithm based on the method is utilized as the local algorithm,thus strengthening the capability of the local search.The hybrid particle swarm algorithm is tested with 13 hard benchmark problems.The result shows that the obtained best solution and the average value of ten times result are better than the parallel genetic algorithm and particle swarm algorithm.So it can be concluded that the proposed hybrid particle swarm algorithm is effective.