树状网络中最短接通时间的快速算法

Fast algorithm for calculating the minimum makespan in tree-type networks

针对文件分配问题 ,提出了一种求解树状网络中最短接通时间的快速算法 .基于边着色和标号的思想 ,结合网络拓扑 ,将原来的网络分解为一系列更小规模的子网络进行处理 .子网络对应的最优解逼近原始网络的最优解 .理论分析和实验结果表明 ,在最短接通时间的计算精度略微降低的情况下 ,本文算法的计算复杂度为O(n) .

Focusing on the file allocation problem, a computationally efficient algorithm for calculating the minimum makespan in tree type networks is proposed. In our approach, the original network is decomposed into a set of smaller subnetworks to be processed, based on the concept of edge coloring and numbering combined with network topology. It is shown that the optimal solution for subnetworks is close to the optimal solution of the original network. Theoretical analysis shows the computational complexity of the proposed algorithm is O(n) while the precision of the minimum makespan declined is insignificant. Numerical experiments corroborate the obtained theoretical results.