
基于随机活动工期的资源约束项目鲁棒性调度优化
Robust scheduling optimization for resource-constrained project based on random duration of activities
项目进度计划的鲁棒性对于不确定条件下项目的顺利实施具有重要影响. 作者研究具有随机活动工期的资源约束项目鲁棒性调度问题, 目标是在可更新资源和项目工期约束下安排活动的开始时间, 以实现项目进度计划鲁棒性的最大化. 首先对所研究问题进行界定并用一个示例对其进行说明. 随后构建问题的优化模型, 设计禁忌搜索、多重迭代和随机生成三种启发式算法. 最后在随机生成的标准算例集合上对算法进行测试, 分析项目活动数、 项目工期和资源强度等参数对算法绩效的影响, 并用一个算例对研究进行说明, 得到如下结论: 禁忌搜索的满意解质量明显高于其他两种算法; 当资源强度或项目工期增大时, 平均目标函数值上升, 禁忌搜索的求解优势增强. 研究结果可为不确定条件下项目进度计划的制定提供决策支持.
The robustness of project schedule plays an important role for the smooth execution of project under uncertain conditions. The authors studied the resource-constrained project robust scheduling problem with random duration of activities. The objective was to arrange the start time of activities so as to maximize the robustness of project schedule under the constraints of renewable resources and project duration. The studied problem was identified and illustrated by using an example at first. Then the optimization model was constructed and three heuristic algorithms, including tabu search, multiple iteration, and random generation, were developed. Ultimately, the algorithms were tested on a standard instance set generated randomly. The influences of activity number, project duration, and resource strength on the algorithms' performance were analyzed. An instance was utilized to illustrate the research in the paper and the following conclusions were drawn: The solution quality of the tabu search is remarkably higher than that of the other two algorithms; as the resource strength or the project duration increase, the average value of objective function climbs and the quality advantage of the desirable solution of the tabu search augments. The research in this paper can provide decision supports for the preparation of project schedule under uncertain conditions.
资源约束项目调度 / 优化模型 / 启发式算法 / 随机活动工期 / 鲁棒性 {{custom_keyword}} /
resource-constrained project scheduling / optimization model / heuristic algorithm / random duration of activities / robustness {{custom_keyword}} /
[1] Kolisch R, Padman R. An integrated survey of deterministic project scheduling[J]. Omega, 2001, 29(3): 249-272.
[2] 刘士新, 王梦光, 唐加福. 资源受限工程调度问题的优化方法综述[J]. 控制与决策, 2001, 16(S1): 647-651.Liu S X, Wang M G, Tang J F. The optimization algorithms for solving resource-constrained project scheduling problem: A review[J]. Control and Decision, 2001, 16(S1): 647-651.
[3] 汪嘉#
[29] , 孙永广, 吴宗鑫. 时间和费用具有不确定性的优化进度计划[J]. 系统工程理论与实践, 2002, 22(1): 93-98.Wang J M, Sun Y G, Wu Z X. Optimal scheduling under probabilistic time and cost[J]. Systems Engineering — Theory & Practice, 2002, 22(1): 93-98.
[4] 寿涌毅, 王伟. 基于鲁棒优化模型的项目调度策略遗传算法[J]. 管理工程学报, 2009, 23(4): 148-152.Shou Y Y, Wang W. A robust optimization model based genetic algorithm for project scheduling policies[J]. Journal of Industrial Engineering and Engineering Management, 2009, 23(4): 148-152.
[5] Herroelen W, Leus R. The construction of stable project baseline schedules[J]. European Journal of Operational Research, 2004, 156: 550-565.
[6] Van de Vonder S, Demeulemeester E, Herroelen W, et al. The use of buffers in project management: The trade-off between stability and makespan[J]. International Journal of Production Economics, 2005, 97: 227-240.
[7] Van de Vonder S, Demeulemeester E, Herroelen W, et al. The trade-off between stability and makespan in resource-constrained project scheduling[J]. International Journal of Production Research, 2006, 44(2): 215-236.
[8] Al-Fawzan M A, Haouari M. A bi-objective model for robust resource-constrained project scheduling[J]. International Journal of Production Economics, 2005, 96: 175-187.
[9] Lambrechts O, Demeulemeester E, Herroelen W. A tabu search procedure for developing robust predictive project schedules[J]. International Journal of Production Economics, 2008, 111: 493-508.
[10] Van de Vonder S, Demeulemeester E, Herroelen W. Proactive heuristic procedures for robust project scheduling: An experimental analysis[J]. European Journal of Operational Research, 2008, 189: 723-733.
[11] Herroelen W, Leus R. Project scheduling under uncertainty: Survey and research potentials[J]. European Journal of Operational Research, 2005, 165: 289-306.
[12] Elmaghraby S. Activity nets: A guided tour through some recent developments[J]. European Journal of Operational Research, 1995, 82(3): 383-408.
[13] Blazewicz J, Lenstra J K, Rinnooy Kan A H G. Scheduling subject to resource constraints: Classification and complexity[J]. Discrete Applied Mathematics, 1983, 5: 11-24.
[14] Mika M, Waligóra G, Weglarz J. Tabu search for multi-mode resource-constrained project scheduling with schedule-dependent setup times[J]. European Journal of Operational Research, 2008, 187(3): 1238-1250.
[15] Waligóra G. Discrete-continuous project scheduling with discounted cash flows — A tabu search approach[J]. Computers and Operations Research, 2008, 35: 2141-2153.
[16] He Z W, Wang N M, Jia T, et al. Simulated annealing and tabu search for multi-mode project payment scheduling[J]. European Journal of Operational Research, 2009, 198(3): 688-696.
[17] Kolisch R, Sprecher A. PSPLIB — A project scheduling problem library[J]. European Journal of Operational Research, 1997, 96: 205-216.
[18] Kolisch R, Sprecher A, Drexl A. Characterization and generation of a general class of resource-constrained project scheduling problems[J]. Management Science, 1995, 41: 1693-1703.
[19] Kolisch R. Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation[J]. European Journal of Operational Research, 1996, 90: 320-333.
国家自然科学基金(70971105); 陕西省自然科学基金(2009JM9001); 中央高校基本科研业务费专项资金
/
〈 |
|
〉 |