Resource-confidence-considered Robust Project Scheduling Algorithm for Cross-enterprise Project
-
摘要: 资源不确定性高和调度鲁棒性要求高是跨企业项目调度问题的重要特征,本文采用资源置信度度量资源的不确定性,建立了考虑资源置信度约束的跨企业项目鲁棒性优化调度模型,设计了路径重连求解算法.算法以路径重连机制搜索解空间,以嵌入 的启发式时间缓冲插入算法快速生成鲁棒性调度,并可通过局部增强搜索算法进一步优化调度的鲁棒性.本文应用项目调度标准问题 库PSPLIB中大量问题实例进行了仿真实验,同两个当前具有代表性的鲁棒性项目调度算法进行了比较,实验结果表明了文中算法的有 效性与优势.Abstract: Higher resources uncertainty and requirement of schedule robustness are key characteristics of cross-enterprise project scheduling. For this problem, some conceptions of resource confidence are defined to measure the resource uncertainty, and a robustness optimization model for cross-enterprise project scheduling is developed which considers the special constraint of resource confidence. A path relinking based project scheduling approach is presented. Firstly, the approach searches the solution space employing path relinking technique. Then, it embeds a heuristic time buffer insertion algorithm to quickly generate robust project schedule. If needed, a local enhanced search algorithm can be used to further improve the schedule robustness. The proposed approach has been tested on the standard instances in PSPLIB, and compared with two well-known competitive algorithms. Experimental results have shown that the new proposed approach is highly effective and efficient for cross-enterprise project scheduling.
-
[1] Brucker P, Drexl A, Möhring A, Neumann K, Pesch E. Resource-constrained project scheduling: notation, classification, models, and methods. European Journal of Operational Research, 1999, 112(1): 3-41 [2] Al-Fawzan M A, Haouari M. A bi-objective model for robust resource-constrained project scheduling. International Journal of Production Economics, 2005, 96(2): 175-187 [3] Herroelen W, Leus R. Project scheduling under uncertainty: survey and research potentials. European Journal of Operational Research, 2005, 165(2): 289-306 [4] Kobylański P, Kuchta D. A note on the paper by M. A. Al-Fawzan and M. Haouari about a bi-objective problem for robust resource-constrained project scheduling. International Journal of Production Economics, 2007, 107(2): 496-501 [5] Lambrechts O, Demeulemeester E, Herroelen W. A tabu search procedure for developing robust predictive project schedules. International Journal of Production Economics, 2008, 111(2): 493-508 [6] Tavares L V, Ferreira J A A, Coelho J S. On the optimal management of project risk. European Journal of Operational Research, 1998, 107(2): 451-469 [7] Herroelen W, Leus R. The construction of stable project baseline schedules. European Journal of Operational Research, 2004, 156(3): 550-565 [8] Vonder S, Demeulemeester E, Herroelen W, Leus R. The use of buffers in project management: the trade-off between stability and makespan. International Journal of Production Economics, 2005, 97(2): 227-240 [9] Vonder S, Demeulemeester E, Hemeulemeester W, Leus R. The trade-off between stability and makespan in resource-constrained project scheduling. International Journal of Production Research, 2006, 44(2): 215-236 [10] Liu Shi-Xin, Song Jian-Hai, Tang Jia-Fu. Approach for setting time buffers in resources-constrained project scheduling. Journal of Systems Engineering, 2006, 21(4): 381-386(刘士新, 宋健海, 唐加福. 资源受限项目调度中缓冲区的设定方法. 系统工程学报, 2006, 21(4): 381-386) [11] Liu Shi-Xin, Song Jian-Hai, Tang Jia-Fu. Critical chain based approach for resource-constrained project scheduling. Acta Automatica Sinica, 2006, 32(1): 60-66(刘士新, 宋健海, 唐加福. 基于关键链的资源受限项目调度新方法. 自动化学报, 2006, 32(1): 60-66) [12] Vonder S, Demeulemeester E, Herroelen W. Proactive heuristic procedures for robust project scheduling: an experimental analysis. European Journal of Operational Research, 2008, 189(3): 723-733 [13] Lambrechts O, Demeulemeester E, Herroelen W. Proactive and reactive strategies for resource-constrained project scheduling with uncertain resource availabilities. Journal of Scheduling, 2008, 11(2): 121-136 [14] Leus R, Herroelen W. The complexity of machine scheduling for stability with a single disrupted Job. Operations Research Letters, 2005, 33(2): 151-156 [15] Wang Xiao-Qing, Tang Jia-Fu, Han Yi. Advances in SCAtter search. Journal of System Simulation, 2009, 21(11): 3155-3160(王晓晴, 唐加福, 韩毅. 分散搜索算法研究进展. 系统仿真学报, 21(11): 3155-3160) [16] Kolisch R, Sprecher A. PSPLIB ——a project scheduling problem library: OR software ——ORSEP operations research software exchange program. European Journal of Operational Research, 1997, 96(1): 205-216 [17] Herroelen W, Leus R. Robust and reactive project scheduling: a review and classification of procedures. International Journal of Production Research, 2004, 42(8): 1599-1620
点击查看大图
计量
- 文章访问数: 1560
- HTML全文浏览量: 73
- PDF下载量: 786
- 被引次数: 0