通信网调度——B题  

作　　者：林晓沧 刘晓军[1] 丁刚[2] 

机构地区：[1]清华大学无线电子学系,学生北京100084 [2]清华大学自动化系,学生北京100084

出　　处：《数学的实践与认识》1994年第4期83-92,共10页Mathematics in Practice and Theory

摘　　要：本文讨论了通信网络的文件传送最优化问题。文中设计了三类模型对不同类型的网络进行了分析;模型Ⅰ针对网络图为连通树且文件传送为单位时间的情况,给出两个定理,得到最短完成时间及最优调度方案;模型Ⅱ采用启发式解法给出了两种算法以得到一般网络的 近似最优调度方案。前两个模型都认为文件在传送中不可分,而模型Ⅲ在文件可分块传送假设下,基于图论中的匹配概念,给出了另一种有效的算法。 以上算法在个人微机上实现,并分别用来解决问题[1]中的情况A,B和C,根据文件是否可分,分别给出了网络的最短完成时间及调度方案,并证明了方案的最优性。 结果为:文件可分时,情况A,B和以C分别用3.0,23.0和29.6单位时间;文件不可分时,则分别用3.0,21.0和29.6单位时间。

关 键 词：通信网 调度 最优调度方案 

分 类 号：TN913.21[电子电信—通信与信息系统]