Heuristic algorithms are one of the most classical methods to solve resource-constrained project scheduling problems and usually used to generate initial solutions to meta-heuristic algorithms. The traditional serial (SSGS) and parallel (PSGS) are classical mechanisms for generating project scheduling schemes. In this paper, a breadth-based progress generation mechanism (BSSGS) that takes into account the location of task nodes based on graph-based breadth-first search algorithm is proposed and the effectiveness of the algorithm is verified. Firstly, the breadth search algorithm is used to define the current task set C, the candidate task set D and the stage variable g in the progress generation mechanism, and hierarchically defined each task node and the task scheduling order. Secondly, combining with the priority rules, the candidate tasks are selected and the resources are updated to generate a complete scheduling scheme. In addition, the new mechanism takes into account the position factor of the task node in the network while meeting priority rules and resource constraint, which haves significant advantages of processing to local complex network and timely scheduling key node and so on. Finally, the examples in PSPLIB are seleeted and tested the new mechanism is tested under different priority rules. The test results show that the shortest duration, the average resource utilization and the optimal scheduling scheme rate is superior to the serial and parallel progress generation mechanism under the priority rules of LPT, SPT, MTS and MIS, and the algorithm time complexity does not increase compared with the traditional mechanism, still O (J2, K).
LI Xiao-peng, LI Cun-bin, PAN Nan-sheng
. A Schedule Generation Scheme Based on Breadth Search of Graph[J]. Chinese Journal of Management Science, 2018
, 26(9)
: 119
-128
.
DOI: 10.16381/j.cnki.issn1003-207x.2018.09.012
[1] 靳新涛,聂兰顺,战德臣,等. 基于人工蜂群的空间资源受限项目调度算法[J].计算机集成制造系统,2014,20(5):1088-1098.
[2] 张汉鹏,邱菀华.资源约束下多项目调度的改进遗传算法[J].中国管理科学,2007,15(5):78-82.
[3] Kolisch R,Hartmann S. Experimental investigation of heuristics for resource-constrained project scheduling:An update[J]. European Journal of Operational Reasearch,2006,174(1):23-27.
[4] Herroelen W. Project scheduling-Theory and practice[J].Production and Operations Management, 2015,14(4):413-432.
[5] 寿涌毅,彭晓峰,李菲.抢占式资源受限项目调度问题的遗传算法[J].浙江大学学报(工学版),2014,48(8):1473-1480.
[6] 郭云涛,陈志,白思俊.求解资源受限项目调度问题的人工鱼群算法[J].运筹与管理,2014,23(5):86-92.
[7] 樊敏,李远富.基于免疫原理的大型复杂项目运营资源受限问题研究[J].统计与决策,2014,(4):67-70.
[8] 张静文,单绘芳.可更新资源受限的工期费用权衡问题及粒子群算法[J].系统管理学报,2012,21(2):186-200.
[9] 李强,张静.多资源受限条件下工程集成管理优化问题研究[J].中国管理科学,2008,16(6):123-129.
[10] 陆志强,刘欣仪.考虑资源转移时间的资源受限项目调度问题的算法[J].自动化学报,2017,43(12):1-9.
[11] 丁雪枫,尤建新.多模式资源受限项目调度问题的混合优化算法研究[J].中国管理科学,2012,20(S1):154-159.
[12] 何立华.资源不确定条件下项目调度多目标优化研究[D].天津:天津大学,2013.
[13] Cooper D F. Heuristic for scheduling resource-constrained projects:An experimental investigation[J]. Management Science,2006,22(11):1186-1194.
[14] Schirmer A. Resource-constrained project scheduling:An evaluation of adaptive control schemes for parameterized sampling heuristics[J]. International Journal of Production Research,2011,39(7):1343-1365.
[15] Klein R. Bidirectional planning:Improving priority rule-based heuristic for scheduling resource-constrained projects[J].European Journal of Operation Research, 2010,127(3):619-638.
[16] Kolisch R.Efficient prority rules for the resource-constrained project scheduling problem[J].Journal of Operations Management,2006,14(3):179-192.
[17] 齐东海,宋向群.工程项目进度管理[M].大连:大连理工大学出版社,2009.
[18] 张松.资源受限项目调度若干问题研究[D].合肥:中国科技大学,2016.
[19] 李菲.基于依赖结构矩阵的资源受限项目[D].杭州:浙江大学,2015.
[20] Li K Y, Wills R J. An iterative scheduling technique for resource-constrained project scheduling.[J] Theory and methodology,2002,56,370-379.
[21] 邵浩,陈华平,孙广中.带有缓冲区的资源受限调度问题的滚动时域求解算法[J].系统工程理论与实践,2010,30(1):119-125.
[22] 初梓豪,徐哲,于静. 带有活动重叠的多模式资源受限项目调度问题[J].计算机集成制造系统,2017,2(3):557-566.
[23] 于静,徐哲,李洪波.带有活动重叠的资源受限项目调度问题建模与求解[J].系统工程理论与实践,2015,35(5):1237-1245.
[24] 杨子兰,李睿,张瑜. 基于资源受限广义指派问题的分解启发式算法[J].数学的实践与认识,2017,47(2):149-154.
[25] Kolish R, Sprecher A. PSPLIB-A project scheduling problem library[J]. European Journal of Operational Research,1996, 96:205-216.
