[1]喻瑛.多模式资源受限项目调度问题的混合遗传算法[J].东南大学学报(自然科学版),2008,38(4):736-740.[doi:10.3969/j.issn.1001-0505.2008.04.038]
 Yu Ying.Hybrid genetic algorithm for multi-mode resource-constrained project scheduling problems[J].Journal of Southeast University (Natural Science Edition),2008,38(4):736-740.[doi:10.3969/j.issn.1001-0505.2008.04.038]
点击复制

多模式资源受限项目调度问题的混合遗传算法()
分享到:

《东南大学学报(自然科学版)》[ISSN:1001-0505/CN:32-1178/N]

卷:
38
期数:
2008年第4期
页码:
736-740
栏目:
经济与管理
出版日期:
2008-07-20

文章信息/Info

Title:
Hybrid genetic algorithm for multi-mode resource-constrained project scheduling problems
作者:
喻瑛
东南大学经济管理学院, 南京 210096
Author(s):
Yu Ying
School of Economics and Management, Southeast University, Nanjing 210096, China
关键词:
多模式 资源受限项目调度 二层混合遗传算法 关键链
Keywords:
multi-mode resource-constrained project scheduling bi-level hybrid genetic algorithm critical chain
分类号:
C934
DOI:
10.3969/j.issn.1001-0505.2008.04.038
摘要:
多模式资源受限项目调度问题是一种NP难的组合优化问题.提出了与基于关键链的启发式算法相结合的二层混合遗传算法对该问题进行求解.在由上层算法确定的调度顺序下,下层遗传算法结合基于关键链的启发式算法,对系统资源重新优化配置,使算法加速向最优解区域收敛,并在下层设计了随迭代代数增加的可变变异概率,以避免早熟收敛.利用标准问题库对算法进行测试,分析问题参数与算法参数对算法结果的影响,发现实验结果的绩效随迭代数的增加而提高,算法耗时随任务数和迭代数的增加而增加.数值测试结果验证了算法的可行性和可靠性.
Abstract:
The multi-mode resource-constrained project scheduling problem is a kind of NP-hard combination optimization problem. To solve it a bi-level hybrid genetic algorithm combined with a critical chain-based heuristic is proposed. Under the given project scheduling specified by the upper-level algorithm, combined with a critical chain-based heuristic, the lower-level genetic algorithm reallocates the resources to shorten the project duration so that the rate of converging to the global optimum district is improved, and a variable mutation probability is developed to avoid premature convergence. Finally, a computational study for a standard set of project instances is carried out to test the validity of the algorithm, and the effects of the problem parameters and algorithm parameters on the results are analyzed. It can be found that the performance of the experimental results improves with the increment of the generations, and the algorithm takes more CPU time when the task numbers or the generations increase. Numerical examples testify the feasibility and reliability of the algorithm.

参考文献/References:

[1] Sprecher A,Hartmann S,Drexl A.An exact algorithm for project scheduling with multiple modes[J].OR Spectrum,1997,19(3):195-203.
[2] Hartmann S,Drexl A.Project scheduling with multiple modes:a comparison of exact algorithms[J].Networks,1998,32(4):283-297.
[3] Heilmann Roland.A branch-and-bound procedure for the multi-mode resource-constrained project scheduling problem with minimum and maximum time lags[J].European Journal of Operational Research,2003,144(2):348-365.
[4] Boctor F F.Heuristics for scheduling projects with resource restrictions and several resource duration modes[J]. International Journal of Production Research,1993,31(11):2547-2558.
[5] Boctor F F.A new and efficient heuristic for scheduling projects with resource restrictions and multiple execution modes[J].European Journal of Operational Research,1996,90(3):349-361.
[6] Mori M,Tseng C.A genetic algorithm for multi-mode resource constrained project scheduling problem[J].European Journal of Operational Research,1997,100(1):134-141.
[7] 刘士新,王梦光,聂义勇.多执行模式资源受限工程调度问题的优化算法[J].系统工程学报,2001,16(1):55-60.
  Liu Shixin,Wang Mengguang,Nie Yiyong.Optimization algorithm for solving multi-mode resource constrained project scheduling problem[J].Journal of Systems Engineering,2001,16(1):55-60.(in Chinese)
[8] Zhang H,Li X,Li H,et al.Particle swarm optimization-based schemes for resource-constrained project scheduling[J]. Automation in Construction,2005,14(3):393-404.
[9] 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 Operational Research,2003,149(2):268-281.
[10] 王为新,李原,张开富.基于遗传算法的多模式资源约束项目调度问题研究[J].计算机应用研究,2007,24(1):72-74.
  Wang Weixin,Li Yuan,Zhang Kaifu.Research of multi-mode resource-constrained project scheduling problem based on genetic algorithm[J].Application Research of Computers,2007,24(1):72-74.(in Chinese)
[11] Kolish R,Sprecher A.PSPLIB—a project scheduling problem library[J]. European Journal of Operational Research,1996,96(1):205-216.
[12] 刘士新,宋健海,唐加福.基于关键链的资源受限项目调度新方法[J].自动化学报,2006,32(1):60-66.
  Liu Shixin,Song Jianhai,Tang Jiafu.Critical chain based approach for resource-constrained project scheduling[J].Acta Automatica Sinica,2006,32(1):60-66.(in Chinese)
[13] 王宏,林丹,李敏强.求解模糊资源受限项目调度问题的遗传算法[J].系统工程学报,2006,21(3):323-327.
  Wang Hong,Lin Dan,Li Minqiang.Application of genetic algorithm in solving fuzzy resource-constrained project scheduling problem[J]. Journal of Systems Engineering,2006,21(3):323-327.(in Chinese)

备注/Memo

备注/Memo:
作者简介: 喻瑛(1975—),女,博士生,squarey@seu.edu.cn.
引文格式: 喻瑛.多模式资源受限项目调度问题的混合遗传算法[J].东南大学学报:自然科学版,2008,38(4):736-740.
更新日期/Last Update: 2008-07-20