资源受限项目调度问题的时间窗分解算法研究

发布时间：2019-06-05 12:43

【摘要】：资源受限项目调度问题是项目管理领域的一类长期受人关注的研究课题,此类问题是各类新的高性能优化方法的实验床。在此类问题的求解中,人们一般会直接利用活动的整体时间窗属性,通过可行解空间的搜索来获取最优调度方案,而在搜索中却忽略了活动的时间窗的可分解特性。通过活动时间窗的分解,可以有效缩小可行解空间,减少搜索过程中的计算量和时间花费,这对求解大规模的资源受限项目调度问题具有重大意义,因此本文对时间窗分解算法进行了创新性的尝试。本研究结合活动时间窗分解的基本思想,首先设计并分析了合适的时间窗分解活动的选择策略与可行解空间分解策略,将原问题可行解空间分解成多个子可行解空间,然后根据重定义方法更新子可行解空间的时间窗,随后基于不同采样策略设置每个子可行解空间的采样规模,最后分别在不同的子可行解空间中进行调度方案的搜索。经过实验对不同策略的检验,本文选取了五种时间窗分解活动的选择策略、三种可行解空间分解策略和两种采样策略进行详细介绍,并对上述策略进行有效组合,通过基于标准案例库PSPLIB的计算实验,分别在J30、J60与J120三组测试集上做了实验分析和对比,广泛地验证了本算法的有效性。实验结果表明,RCPSP的时间窗分解算法在具体案例上能将可行解空间有效降低,并在不同可行解空间分解策略和采样策略下,均相对于未分解的算法在求解时间效率上有显著提高,充分表明了算法的合理性和有效性。此外,本算法具有良好的可拓展性,可嵌套多种启发式算法进一步提高求解效率,这对于未来的研究方向也指出了可行的道路。
[Abstract]:Resource constrained project scheduling problem is a kind of research topic which has been paid close attention to for a long time in the field of project management. This kind of problem is the experimental bed of all kinds of new high performance optimization methods. In solving this kind of problem, people usually use the whole time window attribute of the activity directly to obtain the optimal scheduling scheme through the search of the feasible solution space, but ignore the decomposability of the active time window in the search. Through the decomposition of the active time window, the feasible solution space can be effectively reduced and the amount of computation and time spent in the search process can be reduced, which is of great significance to solve the large-scale resource-constrained project scheduling problem. Therefore, this paper makes an innovative attempt on the time window decomposition algorithm. In this study, combined with the basic idea of active time window decomposition, the suitable selection strategy and feasible solution space decomposition strategy of time window decomposition activity are designed and analyzed, and the feasible solution space of the original problem is decomposed into several sub-feasible solution spaces. Then the time window of the subfeasible solution space is updated according to the redefinition method, and then the sampling scale of each subfeasible solution space is set based on different sampling strategies. Finally, the scheduling scheme is searched in different subfeasible solution spaces. Through the experimental test of different strategies, this paper selects five selection strategies of time window decomposition activities, three feasible solution space decomposition strategies and two sampling strategies in detail, and effectively combines the above strategies. Through the calculation experiments based on the standard case base PSPLIB, the experimental analysis and comparison are carried out on J30, J60 and J120 test sets, and the effectiveness of the algorithm is widely verified. The experimental results show that the time window decomposition algorithm of RCPSP can effectively reduce the feasible solution space in specific cases, and under different feasible solution space decomposition strategies and sampling strategies, Compared with the undecomposed algorithm, the time efficiency of the algorithm is significantly improved, which fully shows the rationality and effectiveness of the algorithm. In addition, the algorithm has good extensibility and can be nesting a variety of heuristic algorithms to further improve the efficiency of the solution, which also points out a feasible way for the future research direction.
【学位授予单位】：华中科技大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP301.6

【参考文献】