相同并行机上工件排序问题的一种新算法

A new Algorithm for Minimizing the Makespan in the Case of Scheduling Identical Parallel Machines

根据工件排序问题的特点,建立了在相同种类的并行机上加工一批相同种类工件的优化数学模型。在蚂蚁系统的基础上对其进行了改进,并把改进的蚂蚁系统用于工件排序问题的优化中。通过与其他算法的仿真比较表明,该基于蚂蚁系统的算法是有效的,特别是问题规模很大时更显示其较快的收敛速度和较高的精度。

In this paper, a kind of ant system based algorithm (ASBA) for minimizing the makespan in identical machine scheduling problem is presented. Two different scale numerical examples demonstrate the ant system based algorithm proposed is efficient and can be used for larger scale identical parallel machine scheduling problem for minimizing the makespan, the quality of its solution has advantage over heuristic procedure and simulated annealing method, as well as genetic algorithm.