网络调度问题.pdf

《网络调度问题.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、网络调度问题摘要本文叙述了公司在用计算机传输文件时如何实现传输时间最短效率最高的调度方案。公司传输文件的计算机网络如一张树形图，解决此问题的办法便是由图论中的最大匹配引出。将文件分批次传输。每次将未被传输的文件合理搭配，利用LINGO软件计算出被选中的文件，使其可以同时传输的文件量达到最大。找出传输每批次文件所需要的时间，其和即为传输完所有文件总用时的最优值。对于问题一，每台计算机能够同时传输的文件数为1，传输每个文件需要的时间为1。所以只在不使计算机同时传输文件的数量超过1的情况下，尽可能多的选取未被传输的文件，就会使文件的传输量达到最大。选取文件的次数即为所求的最优解。对于问题二，

2、每台计算机能够同时传输的文件数不在相同，传输每个文件需要的时间也不唯一。在不超过每台计算机规定的能够同时传输文件的数量的最大值的情况下，使选中的文件在单独传输时所需时间之和最大，即可使该批次的文件传输量达到最大。找出每批次的传输时间，将这些时间相加即为所求结果的最优值。此解决问题的模型具有一般性。当公司布局有所改变，计算机传输量有所改变，以及传输每个文件所需时间有所改变时都可以很快的求得最佳调度方案。考虑到分批次传输文件具有一定的离散性，实际传输文件时，在分析结果的基础上使其连续传输文件便可得到最优结果。关键词：LINGO网络通信调度问题最大匹配1一、问题重述在一些大型公司中，多个部门

3、之间往往需要共享信息，协同工作。假设该公司用若干台计算机组建一个通信网络，由一台计算机向另一台计算机传输文件（数据）。如果该公司有28个部门，每个部门有一台计算机，每天必须传输27个文件。其布局可以用下图表示：其中，顶点V表示计算机，边e表示要传输的文件。用CV()表示计算机Vijii能够同时传输文件的容量（比如CV()1表示计算机V一次能传输一个文ii件），Te()表示传输文件e所需要的时间（文件的传输必须占用两台计算jj机为传输该文件所需的全部时间）。求一下问题：（1）假设对所有的i，j都有CV()1，Te()1。请安排一个最优的方ij式来安排传输，使得所用总时间最少。（2）

4、若公司计算机每次能够传输的文件个数不止一个，如表-1所示。表-1计算机容量i12345678910C(Vi2211111123)i11121314151617181920C(Vi1122121111)i2122232425262728C(Vi12111211)2同时，传输文件所需时间也发生了变化，如表-2所示。表-2文件传输时间j12345678910T(ej)3.04.14.07.01.08.03.22.45.08.0j11121314151617181920T(ej)1.04.49.03.22.18.03.64.57.07.0j21222324252627T(ej)9.04.24.

5、45.07.09.01.2在此情况下，安排一个最优的方式来传输，使得所用总时间最短。并就问题（2）说明：你的方法是否具有一般性（即对CV()和Te()的任意取值，网络结构ij任意）？（3）请向公司主管写一个报告，叙述你解决问题的思路和方法，并证明方法的最优性。二、模型假设（1）假设在传输该批次文件时，将所有文件传输完才进行下一批次传输。（2）每次传输文件的整个过程中每台计算机的性能稳定，即计算机的最大传输量不变、传输文件的速度不变。（3）与文件传输时间相比，用于传输切换的时间（即一台计算机从一文件传输转向另一文件传输的时间）很小，可以忽略。（4）所有文件都是独立的，不存在某个文件必须在

6、另一个文件之前或之后传输的情况。（5）每一个文件都是以一个连续的整体被传输。（6）每次传输可以发生的充分条件是：参与该次传输的两台计算机都有足够的能力进行这次文件传输，即在该时刻计算机正在传输的文件数小于或等于其可以传输的最大文件数。（7）通讯网络是可靠的，无需为了验证或纠正错误而重复传输某个文件，因此，实际传输时间就是。3三、符号说明n:公司部门数量，即传输文件的计算机数量vi（i=1,2,3…n）：表示第i个部门的计算机。h:公司每天必须传输文件的总量（与公司布局有关）ej：表示要传输的文件。T(ej):表示传输文件ej所需要的时间（文件的传输必须要占用两台计算机为传输该文件所需的

7、全部时间）。Xj=0表示文件ej未被选中，xj=1表示文件ej被选中。f,k,g均属于0到h。tmaxp:表示第p批被选中的文件单独传输时所用的时间之和。tminp:表示第p批文件被全部传输完所用的时间。c(vi):表示第i台计算机能够同时传输的文件数量。l:表示传输完所有文件所需的批次。四、问题分析与模型的建立4.1问题分析公司各部门在用计算机传输文件时，所用总时间越少越好。这就需要合理调度各部门的计算机。这一调度方案的设计是建立在已确定的公