Computer Engineering and Applications ›› 2017, Vol. 53 ›› Issue (5): 249-254.DOI: 10.3778/j.issn.1002-8331.1605-0308

Previous Articles     Next Articles

Application of ACO algorithm and different scheduling rules in multi-objective resource-constrained project scheduling problem—modification and comparison with different scheduling rules

CHEN Qinglan1, LIN Kunting2, WEI Chiu-Chi2   

  1. 1.School of Economic and Management, Xiamen University of Technology, Xiamen, Fujian 361024, China
    2.School of Management, Chung Hua University of Technology, Taiwan 30012, China
  • Online:2017-03-01 Published:2017-03-03

蚁群算法求解多目标资源受限项目排程问题#br# ——结合不同排程法则的修正与比较


  1. 1.厦门理工学院 经济与管理学院,福建 厦门 361024
    2.中华大学 管理学院,台湾 30012

Abstract: Previous research focuses more on single target project scheduling problem to minimize the project duration, while multi-objective Resource-Constrained Project Scheduling Problem(RCPSP), considering the total duration, total delay time and total delay cost of the project simultaneously, is less investigated.A multi-objective RCPSP model is built, and an improved Ant Colony Optimization algorithm(ACO)combined with AM scheduling rule, which is proposed by this paper and named AM_ACO algorithm is designed, in order to deal with the multi-objective RCPSP mentioned above.New pheromones(Pheromone)update mode is discussed.Taguchi method is adopted to check ACO parameters values.Finally, the test examples in PSPLIB are used to compare and verify the quality and efficiency of proposed AM_ACO algorithm.The results of comparison confirm the higher quality and efficiency of proposed AM_ACO algorithm in this study.

Key words: resource-constrained project scheduling problem, ant colony optimization, scheduling rules, Taguchi method

摘要: 现有文献较多研究工期最小化的单目标项目排程问题,对于综合考虑项目总工期、总延迟时间、总延迟成本的多目标资源受限项目排程问题(RCPSP)还较少探讨。建构了一个多目标RCPSP模型,以蚁群算法(ACO)配合综合现有排程法则提出的局部启发式函数AM排程法则,修正得到AM_ACO演算法,设计出新的费洛蒙(Pheromone)更新方式,运用田口方法,测试分析ACO各项参数值。最后利用PSPLIB中的测试例题,比较验证AM_ACO演算法的求解品质与效率。比较结果证实AM_ACO演算法有较高的求解品质与效率。

关键词: 资源受限项目排程问题(RCPSP), 蚁群理论, 排程法则, 田口方法