基于结构矩阵求解双代号网络计划的改进算法  

Improved algorithm for solving activity-on-arc network planning based on structure matrix

作　　者：李昊翔[1] 侯公羽[1] 陈钦煌 刘冬桥[2] LI Haoxiang;HOU Gongyu;CHEN Qinhuang;LIU Dongqiao(School of Mechanics and Civil Engineering,China University of Mining and Technology-Beijing,Beijing100083,China;State Key Laboratory for Geomechanics and Deep Underground Engineering,Beijing 100083,China)

机构地区：[1]中国矿业大学(北京)力学与土木工程学院,北京100083 [2]深部岩土力学与地下工程国家重点实验室,北京100083

出　　处：《华中科技大学学报（自然科学版）》2024年第11期147-152,160,共7页Journal of Huazhong University of Science and Technology(Natural Science Edition)

基　　金：国家自然科学基金资助项目(52074299)。

摘　　要：为了提高求解双代号网络计划的算法通用性和计算效率,首先研究了两种计算机求解算法的原理,即基于边集数组的算法(EA-A)和基于结构矩阵的算法(SM-A);然后,提出改进型算法(SM-A1)和相应的Python编程规则;最后,结合算例编写Python程序,验证SM-A1的通用性,并对三种算法的程序性能进行对比分析.经过验证,SM-A1可以准确计算搭接关系转化后的双代号网络计划.算法的性能分析结果表明:SM-A的程序计算效率比EA-A低,主要是因为其在矩阵运算过程中调用了更多的第三方函数.通过优化算法的搜索范围和改进编程规则,可以降低SM-A1程序的时间复杂度和第三方函数的调用,显著提高其求解双代号网络计划的时间参数和关键路径的效率.To enhance the versatility and computational efficiency of algorithms for solving the activity-on-arc network planning,the principles of two computer algorithms,which were the algorithm based on edge set array(EA-A)and the algorithm based on structure matrix(SM-A),were initially studied.Then,an improved algorithm(SM-A1)and corresponding Python programming guidelines were proposed.Finally,combined with examples,Python programs were developed to validate the versatility of SM-A1,and performance comparisons of the three algorithms′programs were conducted.It is confirmed that SM-A1 could accurately compute the activity-on-arc network planning after the conversion of overlapping relationships.Performance analysis results show that the computational efficiency of SM-A′s Python program is lower than that of EA-A′s,primarily due to its increased invocation of third-party functions during matrix operations.The time complexity and third-party function calls of SM-A1′s Python program could be reduced by optimizing the algorithm′s search ranges and improving the programming guidelines,which could significantly enhance the efficiency in solving time parameters and critical paths of the activity-on-arc network planning.

关 键 词：双代号网络计划 结构矩阵 Python编程规则 时间参数 关键路径 

分 类 号：TP399[自动化与计算机技术—计算机应用技术]