基于蚁群系统的工件排序问题的一种新算法

Ant system based algorithm for scheduling problem

工件排序问题中如何使加工效率最高 ,一直是一个非常重要而且又非常困难的问题 .特别是问题的规模很大时 ,目前各种算法计算就非常困难 ,有的甚至无法得到合理的方案 .蚁群系统是近年来发展起来的解决组合优化问题的一种有效方法 .根据工件排序问题的特点 ,建立了在不同种类的并行机上加工一批不同种类工件的优化数学模型 .在蚁群算法的基础上对其进行了改进 ,成功地把改进的蚁群算法用于工件排序问题的优化中 .通过与其他算法的仿真比较 ,表明基于蚁群系统的算法是有效的 。

Different parallel machine scheduling problem for minimizing the makespan is a very important production scheduling problem, when its scale is large, there have been many difficulties in the course of solving different parallel machine scheduling problem. Ant system based optimization algorithms have shown great advantages in solving the combinatorial optimization problem in view of its characteristic that has high efficiency and that is fit for practical application. In this article, a kind of ant system based algorithm (ASBA) for minimizing the makespan in different machine scheduling problem is presented. Two different scale numerical examples demonstrate the ant system based algorithm proposed is efficient and fit for larger scale different 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.