蚁群算法在资源受限项目调度问题中的应用

资源受限的项目调度问题(RCPSP,Resource-ConstrainedProjectSchedulingProblems)已经被证明是一种NP-hard的组合优化问题,随着问题规模的增大,使用经典的数学方法如数学规划等方法,已经很难解决问题。论文提出了一种用于求解资源受限的项目调度问题的蚁群算法。针对资源受限的项目调度问题的具体特点,提出了蚂蚁巡游网络图的动态生成方式,信息素的表示及更新方式,以及启发信息的计算方法。针对PSPLIB中的测试集对算法中的主要参数进行了优化,最后,使用PSPLIB中的四种测试集对算法进行了测试,计算结果表明了算法的有效性。

Applications of ACO Algorithm in Resource-Constrained Project Scheduling Problems

RCPSP(Resource-Constrained Project Scheduling Problems) that has been proved to be a NP-hard problem is a kind of combination optimization problem.With the problem scale becoming larger and larger,the classical mathematics methods such as mathematics programming have great difficulty to solve this kind of problems.An Ant Colony Optimization(ACO) approach for the RCPSP is presented.According to the characteristics of the RCPSP,we develop the method of dynamic generation of the tour network of ants,the method to represent and update the pheromone,and the method to compute the heuristic information.We optimize the main parameters in the algorithm with the benchmark problems from PSPLIB.We test ACO algorithm on four sets of problems from PSPLIB.Computational results show soundness of these algorithms.