蚂蚁算法在工件排序问题中的应用

The Application of Ant Algorithm to the Job Scheduling Problem

蚂蚁算法是近年来新出现的一类随机型仿生算法。它已被成功的应用于组合优化问题中,如旅行商(TravelSalesmanProblem,TSP)问题等。运用蚂蚁算法研究m台机器目标函数为最小时间表长的同顺序车间作业排序问题(Fm|prmu|Cmax),设计出解决该问题的算法步骤与流程;并将蚂蚁算法与解决该问题的其它启发式算法进行了比较。比较的结果说明,蚂蚁算法能有效地解决此类问题,其最优结果优于或者与其他算法的最优结果相当。

Ant Algorithm is a newly developed stochastic searching and bionic algorithm.It has been successfully used to solve several combination optimization problems,such as TSP (Travel Salesman Problem).In this paper,Ant Algorithm is adopted to solve the permutation schedule problem,namely Flow Shop JSP (Job Scheduling Problem).The program flow for solving this problem is presented.For two specific numerical examples of Flowshop,the optimal results by Ant Algorithm are obtained and compared with the results by some other heuristic algorithms.The comparison proves that Ant Algorithm is more satisfying.