求解资源受限项目调度问题的人工鱼群算法

运筹与管理 ›› 2014, Vol. 23 ›› Issue (5): 86-92.

求解资源受限项目调度问题的人工鱼群算法

郭云涛, 陈志, 白思俊

西北工业大学管理学院,陕西西安 710072

收稿日期:2012-11-28 出版日期:2021-05-25
作者简介:郭云涛(1975-),男,河北赵县人,西北工业大学管理学院副教授,博士,研究方向:项目管理,管理系统工程;陈志(1988-),男,陕西汉中人,西北工业大学管理学院硕士研究生,研究方向:项目管理;白思俊(1964-),男,陕西澄城人,西北工业大学管理学院教授、博士生导师,研究方向:项目管理,管理系统工程。
基金资助:
国家自然科学基金项目(71172123);陕西省软科学项目(2012KRM85);西北工业大学人文社科与管理振兴基金项目(RW201105)

An Artificial Fish Swarm Algorithm for the Resource-constrained Project Scheduling Problem

GUO Yun-tao, CHEN Zhi, BAI Si-jun

School of Management, North-western Polytechnical University, Xi'an 710072, China

Received:2012-11-28 Online:2021-05-25

摘要/Abstract

摘要： 提出了将人工鱼群算法应用于求解资源受限项目调度问题中的构想,建立了求解资源受限项目调度问题的人工鱼群算法模型,设计了一种标准随机键编码方式,构建了人工鱼的觅食行为、聚群行为、追尾行为和随机行为四种基本算子,采用了正向逆向局部改进技术和精英保留策略,并给出了算法流程。应用PSPLIB标准问题库对该算法进行了大量的测试,并与其他算法进行了比较,验证了该算法的有效性。

关键词: 运筹学, 项目调度, 资源受限, 人工鱼群算法

Abstract: This paper puts forward an assumption that applying the artificial fish swarm algorithm(AFSA)to the resource-constrained project scheduling problem(RCPSP). An algorithm model of AFSA for the RCPSP is presented, a unique standard random key(SRK)is proposed as the coding representation of the problem, the artificial fish's preying, swarming, following and randomly moving behaviors are redesigned according to the characteristics of the problem, both the forward-backward scheduling technique and elitist strategy are used in the algorithm to improve the schedule quality, finally the algorithm procedures are described in detail. The computational experiments have been performed on the standard test set j30 for the RCPSP generated using ProGen, and the performance of the algorithm given in this paper is compared with several other intelligent optimization algorithms from the literature, results validate the effectiveness of the proposed algorithm for solving the RCPSP.

Key words: operations research, project scheduling, resource-constrained, artificial fish swarm algorithm

中图分类号:

F224.3

郭云涛, 陈志, 白思俊. 求解资源受限项目调度问题的人工鱼群算法[J]. 运筹与管理, 2014, 23(5): 86-92.

GUO Yun-tao, CHEN Zhi, BAI Si-jun. An Artificial Fish Swarm Algorithm for the Resource-constrained Project Scheduling Problem[J]. Operations Research and Management Science, 2014, 23(5): 86-92.

参考文献

[1] Blazewicz J, Lenstra J K, Rinnooy Kan A H G. Scheduling subject to resource constraints: classification and complexity[J]. Discrete Applied Mathematics, 1983, 5(1): 11-24.
[2] 李晓磊,邵之江,钱积新.一种基于动物自治体的寻优模式:鱼群算法[J].系统工程理论与实践,2002,22(11):32-38.
[3] Brucker P, Drexl A, Mohring R, Neumann K, Pesch E. Resource-constrained project scheduling: Notation, classification, models, and methods[J]. European Journal of Operational Research, 1999, 112(1): 3- 41.
[4] 江铭炎,袁东风.人工鱼群算法及其应用[M].北京:科学出版社,2012:45- 47.
[5] 彭武良,郝永平.求解资源受限项目调度问题的改进粒子群算法[J].系统工程,2010,28(4): 84- 88.
[6] Valls V, Quintanilla S, Ballestin F. Resource-constrained project scheduling: a critical activity reordering heuristic[J]. European Journal of Operational Research, 2003, 149(2): 282-301.
[7] Debels D, De Reyck B, Leus R, Vanhoucke M. A hybrid scatter search/electromagnetism meta-heuristic for project scheduling[J]. European Journal of Operational Research, 2006, 169(2): 638- 653.
[8] Kolisch R. Serial and parallel resource-constrained project scheduling methods revisited: theory and computation[J]. European Journal of Operational Research, 1996, 90(2): 320-333.
[9] Li K Y, Willis R J. An iterative scheduling technique for resource-constrained project scheduling[J]. European Journal of Operational Research, 1992, 56(3): 370-379.
[10] Valls V, Ballestin F, Quintanilla S. Justification and RCPSP: a technique that pays[J]. European Journal of Operational Research, 2005, 165(2): 375-386.
[11] Kolisch R, Sprecher A, Drexl A. Characterization and generation of a general class of resource-constrained project scheduling problems[J]. Management Science, 1995, 41(10): 1693-1703.
[12] Hartmann S, Kolisch R. Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem[J]. European Journal of Operational Research, 2000, 127(2): 394- 407.
[13] Kolisch R, Hartmann S. Experimental investigation of heuristics for resource-constrained project scheduling: an update[J]. European Journal of Operational Research, 2006, 174(1): 23-37.
[14] Mobini M , Mobini Z, Rabbani M. An Artificial immune algorithm for the project scheduling problem under resource constraints[J]. Applied Soft Computing, 2011, 11(2): 1975-1982.
[15] Debels D, Vanhoucke M. A decomposition-based genetic algorithm for the resource-constrained project-scheduling problem[J]. Operations Research, 2007, 55(3): 457- 469.
[16] Chen W, Shi Y, Teng H, Lan X, Hu L. An efficient hybrid algorithm for resource-constrained project scheduling[J].Information Sciences, 2010, 180(6): 1031-1039.
[17] Valls V, Ballestin F, Quintanilla S. A hybrid genetic algorithm for the resource-constrained project scheduling problem[J]. European Journal of Operation Research, 2008, 185(2): 495-508.
[18] Tseng L Y, Chen S C. A hybrid metaheuristic for the resource-constrained project scheduling problem[J]. European Journal of Operation Research, 2006, 175(2): 707-721.
[19] Tormos P, Lova A. An efficient multi-pass heuristic for project scheduling with constrained resources[J]. International Journal of Production Research, 2003, 41(5): 1071-1086.
[20] 彭武良,王成恩.一种求解资源受限项目调度问题的蚁群算法[J].系统仿真学报,2009,21(7):1974-1978.
[21] Bouleimen K, Lecocq H. A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version[J]. European Journal of Operation Research, 2003, 149(2): 268-281.