启发式算法是解决资源受限的项目调度问题的经典方法之一,通常用来生成元启发算法初始解,传统的串行(SSGS)和并行(PSGS)是生成项目调度方案的经典机制,本文基于图的广度优先搜索算法,提出了一种考虑任务节点位置因素的广度生成机制(BSSGS),并验证了算法的效果。借鉴广度搜索算法定义进度生成机制中的当前任务集合C、候选任务集合D以及阶段变量g等,对各任务节点进行层次划分并定义任务调度秩序;结合优先规则选择候选任务j*并进行资源Rk(t)调度更新,进而生成完整的调度方案;案例分析表明新机制在满足优先规则和资源约束的同时兼顾了任务节点在网络中位置因素,拥有对于局部复杂网络不回避,对关键节点及时调度等明显优势;选择PSPLIB中算例,在不同优先规则下对新机制进行了测试,测试结果表明新的进度生成机制在LPT、SPT、MTS和MIS等优先规则下,在平均最短工期、平均资源利用率及最优调度方案率等方面优于串行和并行进度生成机制,且算法时间复杂度与传统机制相比并未增加,仍为O(J2,K)。
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).
[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.