文件传输调度问题算法研究

M3M4。与现有的M1M2相比，通过不同的决策变量和约束的表示方式，本文提出了具有更少变M3M3中引入基本下界，进一步减M4。本文进行了大量的数值实验，验证了本文新模型M3和M4的优越性。与现有的最好的整数规划模型相比，求解相同的实例时本文新模型M4平均只需要其约14.3%的时间另外，本文新模型M4可以求解更大规模的实例（100个节点，600条边），150秒，而现有的模型在合理的时间内（600秒）无法求解这样的实例。Modified-VNS的高效性。和现有的基于局部搜索的启发式算法相比，本文算法Modified-VNS获得的解不仅具有更高的质量（和最优解之间的gap小于AlgorithmDesignforFileTransferSchedulingTransferringlargefilesbetweennodesinadistributednetworkisacommonscenarioinproductionandlife.Duetophysicalconstraints,itisimpossibleforanodetotransferallfilesatthesametime.Inthiscase,arrangingwhenthefiletransferstartstoizethebenefitsesaveryinterestingproblem.Itisagainstthebackgroundthatthefiletransferschedulingproblem(FTSP)TherearedifferentvariantsoftheFTSPbyaddingdifferentconstraints,suchasallowingfilestobeforwardedthroughintermediatenodes,etc.ThispaperfocusesonthebasicFTSPwithintegerfilelengthandportconstraints,whichistodesignascheduletotransferseriesoffileswithdifferentfilelengthwhileminimizinerallcompletiontime.Thispaperproposesanewtime-indexintegerprogrammingmodelfortheFTSP.Bydifferentformulationsofvariablesandconstraints,ournewmodelcontainsfewerconstraintsandvariables.Andanenhancedtechniqueisproposedtoreducethenumberofconstraintsfurtherbyutilizingtheelementarylowerbound.Experimentalresultsshowthatcomparedtoexistingbestmodel,thenewmodelwiththeenhancedtechniquecansolvethesameinstancewithonlyabout14.3%ofthetime.Moreover,thenewmodelcansolvelargerinstances(upto100verticesand600files)tooptimalitythatcannotbesolvedbyexistingmodels.Besides,thispaperproposesanewheuristicalgorithmbasedonvariableneighborhoodsearchforsolvingtheFTSP,namedModified-VNS.AccordingtothecharacteristicsoftheFTSP,thispaperdesignsamoresuitableneighbordefinition,andproposesanewsolutionrepresentationwhichreducesthetimecostofcalculatingtheobjectivefunctionvalueofthesolution.Accordingtotheexperimentalresults,thispaperverifiestheefficiencyofthealgorithmModified-VNS.Comparedwiththeexistingbestheuristicalgorithmsbasedonlocalsearch,thealgorithmModified-VNSnotonlyobtainssolutionwithhigherquality,butalsoonlytakesabout14.4%ofthetimeoage.：FileTransferSchedulingProblem;IntegerProgramming;LocalSearch;VariableNeighborhoodSearch;HeuristicAlgorithm........................................................................................................................ 绪 问题定 国内外研究现 本文主要贡 章节介 求解文件传输调度问题的现有方 FTSP相关定 𝑚𝑎𝑘𝑒𝑠𝑝𝑎𝑛的定 FTSP的公式化定 求解FTSP的整数规划模 现有的整数规划模型 现有的整数规划模型 求解FTSP的启发式算 局部搜索的相关概 通用的局部搜索算 通用的变邻域搜索算 现有的求解FTSP的启发式算 本章小 改进的新模型和新的启发式算 新的整数规划模型M3和 新的整数规划模型 进一步改进的整数规划模型 和现有整数规划模型的对 新的启发式算法Modified- 解的表示方 邻域的定 新的启发式算法Modified- 本章小 实验结果与分 本文主要研究求解文件传输调度问题（FileTransferSchedulingProblem，FTSP）的问题定文件传输调度问题可以用无向图𝐺=(𝑉,𝐸)来表示，即文件传输图（FileTransferGraph），1.1所示。其中，图中的节点𝑣∈𝑉表示分布式网络中的计算机，每两个1.1文件传输调度图Fig. Filetransfer𝑒4和𝑒5），满足端口约束意味着节点𝑣3最多只能同时传输这三个文件中的两个Coffmanetal.[1-2]提出，描述该问题的文件传输图也是由FTSP，并且不允许文件经Coffmanetal.研究了具有不同特征的文件传输调度问题的复杂度，其中涵盖了很多特殊的情况，比如文件传输图点的端口数均为1，每一对节点间最多只有一条边，NP-hard，而在一些特殊的FTSP（例如文件的长度相同，或者文件传输图是二分图等）是存在多项式时间复杂度的算法的。另外，Coffmanetal.FTSP的基本下NP-hardNakanoNishizeki考虑了带有端口约束和通道约束的除此之外，也有一些研究者更关注FTSP在更复杂的实际场景中的应用。例如，Veeraraghavanetal.研究了高速光电路中文件的调度和传输问题[7]。另外，MaoSimha调度和路由问题（FileTransferRoutingandScheduling）[8]。他们提出了三个贪心的列表调度算法（GreedyListScheduling），并证明了这些算法的高效性。之后，Havill，Mao和Simha首次考虑了的文件传输调度和路由问题（On-LineFileTransferRoutingandSchedulingMao也提出了一个简单的贪心算法，并给出了该算法的竞争比[10]。另外，Jiaetal.还分析[11]。Linetal.则研究了在云计算中大文件传输的调度问题，并提出了求解该问题的FTSP的法已经在不同的调度问题的求解中得到了很广泛的应用[13]，Higueroetal.首次将该方法外，DražićZetal.重新模型化了文件传输时间为整数的FTSP，并且首次提出了求解该问节点，200个文件），但是求解时间依旧很长，仍然存在可提升的空间。考虑到现有的整数规划模型的缺点，本文提出了两个新的更好的求解FTSP的整数规划模型。虽然包括整数规划在内的精确方法可以保证获得的解是最优的，但是由于问题FTSP本身固有的复杂性，随着实例规模的增大，求解时间将呈指数增长，很难在合理Akbarietal.HopfieldFTSP[17]。但Algorithm，GA）[25]和变邻域搜索算法（VariableNeighborhoodSearch，VNS）[26-27]等。模拟退火算法和搜索算法都是采用允许往比当前解更坏的邻居解移动的策略来避了广泛的关注[28-29]，DražićZFTSPFTSP的基FTSP的基于变邻域搜索的启发式算法，以及两个新的求解FTSP的局部搜索子程FTSP的基于局部搜索的启发式算法，但是这些算法求解大FTSP的启发式算法性能不够的求解FTSP的启发式算法。本文主要贡M3M4。通过更改决策变量和约束的定义方式，本文新模型M3和M4具有更小的规模——更少的约束数和变量数。本了大量的数值实验，验证了新模型M3和M4的优越性。和现有的整数规划模型相比，求解相同实例时新模型M3M4会花费更少的求解时间，因此可以在合理的时间内（600s）求解更大的实例，高达100个节点，600条边。本文的第二个工作是设计了更高效的基于局部搜索的启发式算法Modified-VNS。通过设计不同的解的表示方式，本文算法可以在更短的时间内解析出解对应的调发式算法相比，本文新算法Modified-VNS可以获得更高质量的解，并且花费更章节介本文在第2章介绍了文件传输调度问题的相关概念以及求解该类问题的方法——本章节首先将详细介绍本文研究的文件传输调度问题（FileTransferSchedulingProblem，FTSP）的更公式化的定义，然后介绍求解文件传输调度问题的两大类FTSP，考虑的约束包括节点的端口约束和文FTSP中，一个调度𝑠可以视为一个函数𝑠𝐸0，给每一个文件𝑒𝐸都分配一个开始时间𝑠(𝑒)。令𝑠(𝑒)表示在调度方案𝑠对应的每一个文件𝑒∈𝐸的开始传输时间，max𝑠(𝑒)+ 2.1给出了一个时序图表示的文件调度方案，图中表示文件𝑒1，𝑒4和𝑒5输的文件为𝑒3，在时刻5完成传输，那么该调度方案的𝑚𝑎𝑘𝑒𝑠𝑝𝑎𝑛为5。1：令调度方案𝑠𝐸0FTSP的可行解，那么一定存在调度方案𝑠𝐸𝑁使得𝑂𝑏𝑗(𝑠′′)≤𝑂𝑏𝑗(𝑠′)[15]定理1中的𝑂𝑏𝑗(𝑠′)表示调度方案𝑠的𝑚𝑎𝑘𝑒𝑠𝑝𝑎𝑛。由于文件的传输时间都是整数，定理1→个文件𝑒∈𝐸都分配一个整数的开始时间𝑠(𝑒)FTSPFTSP可以模型FTSP给定文件传输图𝐺=(𝑉𝐸)，其中每一个节点𝑣𝑉关联一个整数的端口数𝑝(𝑣)，每一条边𝑒∈𝐸关联一个整数的文件传输时间𝑙(𝑒)FTSP的调度方案可以描述为函数𝑠𝐸其中，端口约束指的是对于任意一个节点𝑣∈𝑉和任意一个时刻𝑡≥|{𝑒:𝑒是𝑣需要传输的文件并且𝑠(𝑒)≤𝑡<𝑠(𝑒)𝑙(𝑒)}|≤𝑝(𝑣)不允许中断。另外，本文研究的FTSP中认为任意两个节点之间均具有直接相连的通信2.1一个调度方案Fig. A求解FTSP的整数规划模关注的求解FTSP的精确方法也是这种。为了方便和本文新的整数规划模型进行本小节将介绍由DražićZetal.整数规划模型[15]，记为模型M1。模型M1中1,eτ𝑥𝑒𝜏=

0,

其中，文件𝑒τ对应的时间段[𝜏1𝜏]是活跃的，也即文件𝑒τ对应的时间段[𝜏1𝜏]𝑠𝑢𝑏𝑗𝑒𝑐𝑡∑𝑇𝑀𝐴𝑋𝑥𝑒𝜏=𝑙(𝑒),∀𝑒∈∑𝑒∈𝐸,𝑒∋𝑣𝑥𝑒𝜏≤𝑝(𝑣),∀𝑣𝑠𝑢𝑏𝑗𝑒𝑐𝑡∑𝑇𝑀𝐴𝑋𝑥𝑒𝜏=𝑙(𝑒),∀𝑒∈∑𝑒∈𝐸,𝑒∋𝑣𝑥𝑒𝜏≤𝑝(𝑣),∀𝑣∈𝑉,1≤𝑧≥𝜏𝑥𝑒𝜏,∀𝑒∈𝐸,1≤𝜏≤𝑥𝑒𝑗≥𝑥𝑒𝑖+𝑥𝑒𝑘−1,∀𝑒∈𝐸,1≤≤<𝑗<𝑘≤𝑥𝑒𝜏∈{0,1},∀𝑒∈𝐸,1≤𝜏≤𝑧∈其中，约束（2.4）确保每一个文件𝑒∈𝐸都在𝑇𝑀𝐴𝑋之前被完整地传输。约束（2.5）（2.6束（2.7）例如如果文件𝑒∈𝐸在时间段𝑖和时间段𝑘活跃，那么它一定在满足𝑖<𝑗<𝑘的任一时间段𝑗活跃。约束（2.8）保证了𝑥𝑒𝜏是个二进制变量，而约束（2.9）保证了变量𝑧，即调度的模型M1的变量数为|𝐸|𝑇𝑀𝐴𝑋+1，而约束数为|𝐸||𝑉|𝑇𝑀𝐴𝑋+|𝐸|∗𝑇𝑀𝐴𝑋|𝐸|∗∑𝑇𝑀𝐴𝑋−2𝑘∗(𝑘+1)。尽管 是预先求得的常量，但是 实际和文件数 以及节点数|𝑉|M1具有关于|𝐸|和|𝑉|伪多项式的约束数。显然，当实例有|𝐸|∗∑𝑇𝑀𝐴𝑋−2𝑘∗(𝑘+1)个约束。当文件的数目和𝑇非常大的时候，由公式（2.7）引入 本小节将介绍由DražićZ另一个整数规划模型[16]，记为模型M2。和模型1,eτ𝑦𝑒𝜏= 0,引入变量𝑦𝑒𝜏之后，文件传输的连续性约束可以表示为如下形式∑𝑇𝑀𝐴𝑋𝑦𝑒𝜏=1,∀𝑒∈ 𝑥𝑒𝜏−𝑥𝑒(𝜏−1)≥𝑦𝑒𝜏,∀𝑒∈𝐸,2≤𝜏≤ 𝑥𝑒1=𝑦𝑒1,∀𝑒∈ 𝑠𝑢𝑏𝑗𝑒𝑐𝑡𝑠𝑢𝑏𝑗𝑒𝑐𝑡∑𝑇𝑀𝐴𝑋𝑥𝑒𝜏=𝑙(𝑒),∀𝑒∈∑𝑒∈𝐸,𝑒∋𝑣𝑥𝑒𝜏≤𝑝(𝑣),∀𝑣∈𝑉,1≤≤𝑧≥𝜏𝑥𝑒𝜏,∀𝑒∈𝐸,1≤𝜏≤∑𝑇𝑀𝐴𝑋𝑦𝑒𝜏=1,∀𝑒∈𝑥𝑒𝜏−𝑥𝑒(𝜏−1)≥𝑦𝑒𝜏,∀𝑒∈𝐸,2≤≤𝑥𝑒1=𝑦𝑒1,∀𝑒∈𝑥𝑒𝜏∈{0,1},∀𝑒∈𝐸,1≤𝜏≤𝑧∈数目大大减少，即由原来的|𝐸|∑𝑇𝑀𝐴𝑋−2𝑘∗(𝑘+1)减小为|𝐸||𝐸|𝑇 M2的变量数却增多了，从原来的|𝐸|∗𝑇𝑀𝐴𝑋+1增加为2∗|𝐸|∗𝑇𝑀𝐴𝑋+1，几乎增加了一倍。不过后模M2的性能有了比较大的提M1相点，200个文件）。尽管和模型M1相比，模型M2的性能有了一定的提升，但是最根本的问题并没有M2求解FTSP的启发式算本文研究的问题FTSP已经被证明是NP-hard的最优化问题[1-2]。在研究求解某个问NP类问题则无法找到求解该问题的多项式时间复杂度的算法。其中，多项式时间复杂𝑂(𝑝(𝑛))求解最优化问题的方法一般可以分为两类——精确方法和启发式算法。对于像FTSPNP-hard最优化问题，精确方法虽然可以保证获得的解一定是最优解，但的整数规划模型的设计，还关注求解FTSP的启发式算法的设计。𝑓𝑓:𝑋→ℝ表示目标函数。目标函数𝑓给每一个解𝑥∈𝑋分配一个实数的目标函数值，可以min𝑠.𝑡.𝑥∈

前，本文将首先引入一个重要的概念——邻域（Neighborhood）和邻居解（Neighbor邻域和邻居解：邻居函数𝑁给每一个解𝑥∈𝑋都分配了一个邻居解的集合𝑁(𝑥)，𝑁(𝑥)即解𝑥的邻域。如果解𝑥′∈𝑁(𝑥)，那么称解𝑥′是解𝑥的邻居解。min𝑓(𝑥)=𝑥1+𝑥2+𝑠.𝑡.𝑥∈

令𝑁(𝑥)={𝑥′||𝑥′−𝑥|2≤1}。那么当𝑥=(1,1,1)时，其邻域𝑁(𝑥){(0,1,1),(1,0,1),(1,1,0),(2,1,1),(1,2,1),(1,1,2)}，如图2.2所示。2.2邻居解Fig. Neighbor前解的邻域中选择一个更好的邻居解来取代当前的解，如图2.3所示。当所有的邻居解2.4中，如果将𝑥∗作为初始解开始搜索，那么得到局部最优解𝑋′后算法2.3局部搜索的思想Fig. Theprincipleoflocal，搜索算法，遗传算法，变邻域搜索算法等。其中，模拟退火算法和搜索算法都是通过允许选择比当前解更差的邻居解来跳出局部最优因buit），通过向近的居解移2.4局部搜索Fig. Local2.5所示，在第一种邻域定义中，解𝑥∗已经是局解的表示方式，邻居的定的移动规则和搜索的停止规则。2.5包含两种邻居的变邻域搜索Fig. Variableneighborhoodsearchusino有解，因此需要花费更久的时间。表2.1中描述的是第一种邻居选择策略。2.1局部搜索Tab. Local′∈2.2描述了通用的变邻域搜变邻域搜索通常需要预先指定包含多种邻域定义的集合𝑁𝑘(𝑘=1,2𝑘𝑚𝑎𝑥)𝑘𝑚𝑎𝑥为预先定义的常数，可以通过这个参数来控制不同邻域的数目。如果𝑘𝑚𝑎𝑥比较大，变邻域搜索类似于多个局部搜索算法；如果𝑘𝑚𝑎𝑥比较小，例如𝑘𝑚𝑎𝑥=1时，那么变邻域个邻域𝑁𝑘(𝑥)通常包含前一个邻域𝑁𝑘−1(𝑥)：𝑁1𝑁2𝑁𝑘𝑚𝑎𝑥。变邻域搜索时首先会对当前的解𝑥进行一个抖动（shaking），随机生成当前解𝑥邻和当前解𝑥进行比较，如果𝑓(𝑥′′)<𝑓(𝑥)，那么令𝑥=𝑥′′，并进行下一次迭代。否则，继续探索当前邻域𝑁𝑘(𝑥)的下一个邻域𝑁𝑘+1(𝑥)，直至找到邻居解𝑥′′满足条件𝑓(𝑥′′)<𝑓(𝑥)或者探索完最后一个邻域𝑁𝑚𝑎𝑥(𝑥)，如图2.6所示。2.6变邻域搜索的思想Fig. Theprincipleofvariableneighborhood时间地花费在抖动阶段则可以将搜索到整个解空间潜在的包括更好的解的区域，即搜索整个解空间的区域。因此在设计基于变邻域搜索的启发式算法时，需要根据问本小节将简单介绍DražićZetal.求解FTSP的变邻域搜索算法[30]记为VNS。VNS2.2中描述的通用的变邻域搜索框架，嵌入的局部搜索子程序使2.1VNS中解的表示方式2.2Tab. 输入：给定邻域𝑁𝑘，𝑘=1,2𝑘𝑚𝑎𝑥。 令𝑘=1，重复以下步骤，直至𝑘>𝑘𝑚𝑎𝑥′∈𝑁(𝑥)′∈𝑁(𝑥)以𝑥′为初始解进行局部搜索，获得局部最优解𝑥′′如果𝑓(𝑥′′)<𝑓(𝑥)，那么令𝑥=𝑥′′，𝑓(𝑥)=𝑓(𝑥′′)1。否则，令𝑘=𝑘+1。VNS中，作者使用𝑛维向量𝑥=(𝑥1𝑥2𝑥𝑛)来表示=个节点在时刻𝑡均有可用的端口，那么令文件𝑒的开始传输时间𝑠(𝑒)=𝑡，并继续扫描接下来的文件。每完成一次文件列表的扫描，时刻𝑡𝑡1，直至所有的文件都被分配一VNS算法中解的表示方式转换成文件传输调度问题的具体调度然后是邻域的定义。算法VNS中外层搜索时的邻域集合为{𝑁𝑘(𝑥)𝑘𝑚𝑖𝑛≤𝑘≤𝑘𝑚𝑎𝑥}，𝑘𝑚𝑖𝑛和𝑘𝑚𝑎𝑥均为预先设置的参数。𝑁𝑘(𝑥)的含义为 {𝑥′|𝑥′和𝑥最多有个元素不同}。而变邻域搜索中内层局部搜索子程序的邻域定义为𝑁2(𝑥)本小节将简单介绍DražićZetal.求解FTSP的变邻域搜索算法[32]，记为Gauss-VNSGauss-VNSVNS相同的解的表示方式，不同之处Gauss-VNS中外层搜索时的邻域集合为{𝑁′(𝑥),

≤𝑘≤

为预先设置的参数。另外，预先给定参数{𝜎𝑘,𝑘𝑚𝑖𝑛≤𝑘≤𝑘𝑚𝑎𝑥}。对于𝑥，生成其邻居解∈𝑁(𝑥)①首先随机生成𝑛个满足分布𝑁(0,1)的数𝑧1,𝑧2,…,𝑧𝑛，构成𝑛维向量𝑧=(𝑧1,𝑧2,…,𝑧𝑛)。𝑥′=𝑥𝜎𝑘𝑧VNS，Gauss-GVNS和Gauss-VNS-LS1。由于Gauss-VNS和Gauss-GVNS本质上相差不大，因此本文主要关注算法Gauss-GVNS和Gauss-VNS-LS1。Gauss-VNSVNS2.1中描述的通用的局部搜索算法，局部搜索算法中使用的邻域定义也和VNS算法相同。定义𝐿𝑆-𝑁𝑙(𝑥)，𝐿𝑆-𝑁𝑙(𝑥)={𝑥′|交换𝑥中任意两个距离为𝑙的元素}，𝑙=1,…,𝑛−1。Gaussian-GVNS中使用的局部搜索算法如下所示①令𝑖=1𝑥𝑥′1；否则令𝑖𝑖1。如果令𝑖𝑛，那么结束搜索。否则，继续执行步骤2。Gaussian-GVNS中使用的局部搜索算法在所有的邻居解都没有当前解好时，会继续探索的邻居解，直至完成预先定义的所有邻域的探索；反之，则不会。这样一来，Gauss-VNS-LS12.1中描述的通用的局部搜索算本章小义。对于本文关注的FTSP，其𝑚𝑎𝑘𝑒𝑠𝑝𝑎𝑛的含义为最后一个文件完成传输的时间。FTSP方法的分类，主要分为精确方法和启发式算法两大FTSPM1M2；启发式解FTSP的基于局部搜索的启发式算法VNSGauss-VNS。本章将介绍本文求解文件传输调度问题（FileTransferSchedulingProblem，FTSP）FTSPM3M4FTSP的新的基于局部搜索的启发式算法Modified-VNS。DražićZetal.FTSPM1M2[15-16]，但是模型M1的变量数有|𝐸|∗𝑇𝑀𝐴𝑋+1，而约束数为|𝐸||𝑉|𝑇𝑀𝐴𝑋+|𝐸|∗𝑇𝑀𝐴𝑋+|𝐸|∑𝑇𝑀𝐴𝑋−2𝑘∗(𝑘+1)M2的变量数有2|𝐸|𝑇1，约束数为|𝐸||𝑉|𝑇2 |𝐸|𝑇𝑀𝐴𝑋。其中|𝐸|为文件的数目，|𝑉|为节点的数目，𝑇𝑀𝐴𝑋为问题FTSP的一个上界。M14050M2虽然可M1M2中引入了启发式算法获得的上界𝑇𝑀𝐴𝑋来减少模型的约束数和变量数，那接下来，本小节将详细介绍本文求解FTSP的两个新的整数规划模型，记为模型M3和模型M4。本文第一个整数规划模型M3是时间索引的整数规划模型，M3的改进版，通过利用基本下界进一步地减少了约束数。FTSPM3。数规划模型M3。𝑦𝑒𝜏=

1,如果文件𝑒在时间索引𝜏对应的时间开始传输0,

包含排序和调度的问题可以很自然地使用由(𝑖,𝑡)索引的变量𝑥𝑖𝑡模型化为整数规划其中，𝑒表示需要被传输的文件的索引，𝜏𝑍+表示时间段[𝜏1𝜏]的索引，例如对于时间索引1，表示时刻0到时刻1的时间段[0,1]。考虑到文件的数目是有限的，显然在有 𝑠𝑢𝑏𝑗𝑒𝑐𝑡∑𝑇𝑀𝐴𝑋−𝑙(𝑒)+1 =1,∀𝑒∈

( 𝑦𝑒𝑠≤𝑝(𝑣),∀𝑣∈𝑉,1≤𝜏≤𝑠=max{1,𝜏−𝑙𝑒𝑧≥(𝑙(𝑒)+𝜏−1)𝑦𝑒𝜏,∀𝑒∈𝐸,1≤𝜏≤ 𝑦𝑒𝜏∈{0,1},∀𝑒∈𝐸,1≤𝜏≤ 𝑧∈ 束（3.5）保证了所有文件𝑒𝐸的完成传输的最大时间小于等于𝑧，该约束实际上也是变本文新模型M3中的变量数为|𝐸|∗𝑇𝑀𝐴𝑋+1，约束数为|𝐸|+|𝑉|∗𝑇𝑀𝐴𝑋|𝐸|∗𝑇𝑀𝐴𝑋。和模型M1相比，模型M3的变量数保持不变，但是约束数降低了|𝐸|∑𝑇𝑀𝐴𝑋−2𝑘∗(𝑘+1)。而和模型M2相比，模型M3的变量数减小了|𝐸|∗ （1）上界𝑇𝑀𝐴𝑋3.1列表调度算法Tab. Listscheduling输入：文件传输图𝐺=(𝑉𝐸)初始化：将所有文件𝑒∈𝐸按照文件长度𝑙(𝑒从大到小的顺序排序，记为𝑎𝑙𝑙𝐹𝑖𝑙𝑒𝐿𝑖𝑠𝑡，并设置所有文件𝑒𝐸的开始传输时间𝑠(𝑒1，所有节点𝑣𝑉的可用端口数𝑎𝑣𝑎𝑖𝑙𝑎𝑏𝑙𝑒𝑃𝑜𝑟𝑡𝑁𝑢𝑚(𝑣)=𝑝(𝑣)。𝑐𝑜𝑢𝑛𝑡= /∗𝑡ℎ𝑒𝑛𝑢𝑚𝑏𝑒𝑟𝑜𝑓𝑓𝑖𝑙𝑒𝑠𝑡𝑟𝑎𝑛𝑠𝑓𝑒𝑟𝑟𝑒𝑑𝑡𝑚𝑎𝑘𝑒𝑠𝑝𝑎𝑛=𝑭𝒐𝒓𝑡=0;;𝑡=𝑡+𝑰𝒇𝑐𝑜𝑢𝑛𝑡==𝑎𝑙𝑙𝐹𝑖𝑙𝑒𝐿𝑖𝑠𝑡.𝑭𝒐𝒓𝑖=0;𝑖<𝑎𝑙𝑙𝐹𝑖𝑙𝑒𝐿𝑖𝑠𝑡.𝑠𝑖𝑧𝑒();𝑖=𝑖+𝐿𝑒𝑡𝑒𝑏𝑒𝑡ℎ𝑒𝑓𝑖𝑙𝑒/∗𝑉𝑒𝑟𝑡𝑒𝑥𝑣𝑠𝑡𝑎𝑟𝑡𝑎𝑛𝑑𝑣𝑒𝑛𝑑𝑎𝑟𝑒𝑒𝑑𝑔𝑒(𝑓𝑖𝑙𝑒)𝑒′𝑠𝑰𝒇𝑠(𝑒)==−1&&𝑎𝑣𝑎𝑖𝑙𝑎𝑏𝑙𝑒𝑃𝑜𝑟𝑡𝑁𝑢𝑚(𝑣𝑠𝑡𝑎𝑟𝑡)>0&&𝑎𝑣𝑎𝑖𝑙𝑎𝑏𝑙𝑒𝑃𝑜𝑟𝑡𝑁𝑢𝑚(𝑣𝑒𝑛𝑑)>0𝑠(𝑒)=𝑐𝑜𝑢𝑛𝑡+𝑎𝑣𝑎𝑖𝑙𝑎𝑏𝑙𝑒𝑃𝑜𝑟𝑡𝑁𝑢𝑚(𝑣𝑠𝑡𝑎𝑟𝑡)−𝑎𝑣𝑎𝑖𝑙𝑎𝑏𝑙𝑒𝑃𝑜𝑟𝑡𝑁𝑢𝑚(𝑣𝑒𝑛𝑑)−𝑰𝒇𝑠(𝑒)+𝑙(𝑒)>𝑡𝑚𝑎𝑘𝑒𝑠𝑝𝑎𝑛=𝑠(𝑒)+

输出：所有文件的开始传输时间𝑠(𝑒)和𝑡𝑚𝑎𝑘𝑒𝑠𝑝𝑎𝑛本文使用Coffmanetal.列表调度（ListScheduling，LS）算法[1]来生成模型M3中的参数𝑇𝑀𝐴𝑋FTSPFTSP的目将该文件的开始传输时间设置为𝑡，并将两个节点对应的可用端口数减1。模型M3中使用的𝑇𝑀𝐴𝑋。M3M4M3M4。因此，在详细介绍模型M4之前，本小节将首先介绍基本下界𝐸𝐿𝐵的定义。（1）基本下界Coffmanetal.FTSP的基本下界（ElementaryLowerBound，ELB）[1-2]。记为|𝐸𝑢|。另外，令∑𝑢∑𝑒∈𝐸𝑢𝑙(𝑒)表示节点𝑢需要传输的所有文件的传输时间之和，那件传输图𝐺=(𝑉,𝐸)的最优解𝑂𝑃𝑇(𝐺)一定满足以下不等式：𝑂𝑃𝑇(𝐺)≥𝑚𝑎𝑥𝑢⌈∑𝑢/𝑝(𝑢)⌉. 公式（3.8）FTSP的基本下界𝐸𝐿𝐵=𝑚𝑎𝑥𝑢⌈∑𝑢/𝑝(𝑢)⌉1.1节点𝑣1关联的边的集合为𝐸𝑣1={𝑒1𝑒3}，那么∑𝑣1=𝑙(𝑒1)+𝑙(𝑒3)=3+2=4⌈∑𝑣4/𝑝(𝑣4)⌉=⌈5/2⌉=3。那么图1.1中的FTSP实例的基本下界𝐸𝐿𝐵𝑚𝑎𝑥{5,3,4,3}=5更少的整数规划模型M4。FTSPELB的情况下（ELB的计算非常简单，因此引入的计算基本下界的开销基本可以忽略不计）M3中的约束（3.5）中的𝜏无需1开始，因为当𝜏𝐸𝐿𝐵𝑙(𝑒)时，∀𝑒∈𝐸，不等式𝑧≥(𝑙(𝑒𝜏1)𝑦𝑒𝜏一定成立。因此可以用以下不等式来取代模型M3中的约束（3.5）：𝑧≥(𝑙(𝑒)+𝜏−1)𝑦𝑒𝜏,∀𝑒∈𝐸,𝐸𝐿𝐵−𝑙(𝑒)+1≤𝜏≤𝑇𝑀𝐴𝑋. 𝐸𝐿𝐵≤𝑧≤ 模型M4如下所示: 𝑠𝑢𝑏𝑗𝑒𝑐𝑡∑𝑇𝑀𝐴𝑋−𝑙(𝑒)+1 =1,∀𝑒∈

( 𝑦𝑒𝑠≤

,∀𝑣∈𝑉,1≤𝜏≤𝑠=max{1,𝜏−𝑙𝑒𝑧≥(𝑙(𝑒)+𝜏−1)𝑦𝑒𝜏,∀𝑒∈𝐸,𝐸𝐿𝐵−𝑙(𝑒)+1≤𝜏≤𝑇𝑀𝐴𝑋;𝑦𝑒𝜏∈{0,1},∀𝑒∈𝐸,1≤𝜏≤ 𝐸𝐿𝐵≤𝑧≤𝑇𝑀𝐴𝑋,𝑧∈ 模型M4的变量数和模型M3相同，均为|𝐸|𝑇𝑀𝐴𝑋+1，而约束数则为|𝐸||𝑉|𝑇𝑀𝐴𝑋|𝐸|(𝑇𝑀𝐴𝑋𝐸𝐿𝐵∑𝑒∈𝐸𝑙(𝑒)ELB，和模≥𝐸𝐿𝐵∑𝑒∈𝐸𝑙(𝑒0）M4M3的表3.2中统计了现有的整数规划模型M1M2和本文新的整数规划模型M3，M1由于传输连续性约束的复杂表示方式具备大量的约束数，而模型M2虽然通过引入额外的变量大大降低了约束数，但是和模型M1相比，模型M2的变量数增|𝐸|∗ 1) |𝑉|𝑇𝑀𝐴𝑋2|𝐸|𝑇𝑀𝐴𝑋M1M2很难而本文新模型M3通过不同的表示方式定义了文件传输连续性约束和端口约M3中的变量数为|𝐸|𝑇𝑀𝐴𝑋+1，约束数为|𝐸||𝑉|𝑇𝑀𝐴𝑋+|𝐸|𝑇𝑀𝐴𝑋M1相 M3的变量数减小了|𝐸|∗𝑇𝑀𝐴𝑋，同时约束数也降低了|𝐸|∗𝑇𝑀𝐴𝑋。在此基础上，本文又在新模型M3中引入基本下界𝐸𝐿𝐵，获得了另一个新模型M4。基本下界的引入使得新模型M4的约束数和新模型M3相比，又减少了很多。和模型M3相比，模型M4的变量数不变，但是约束数又降低了|𝐸|∗𝐸𝐿𝐵−∑𝑒∈𝐸𝑙(𝑒)。3.2不同模型的变量数和约束数Tab. Thenumberofvariablesandconstraintsfordifferent模 变量 约束 |𝐸|∗𝑇𝑀𝐴𝑋+ |𝐸|+|𝑉|∗ +|𝐸|∗ +|𝐸|∗∑𝑇𝑀𝐴𝑋−2 2∗|𝐸|∗𝑇𝑀𝐴𝑋+|𝐸|+|𝑉|∗𝑇𝑀𝐴𝑋+2∗|𝐸|∗|𝑬|∗𝑻𝑴𝑨𝑿+|𝑬|+|𝑽|∗𝑻𝑴𝑨𝑿+|𝑬|∗|𝑬|∗𝑻𝑴𝑨𝑿+|𝑬|+|𝑽|∗𝑻𝑴𝑨𝑿+|𝑬|∗(𝑻𝑴𝑨𝑿−𝑬𝑳𝑩)+∑𝒆∈𝑬模型M3和M4具有更小的规模，因此理论上在求解相同的实例时会花费更少的新的启发式算法Modified-现有的求FTSP的启发式算法VNS，Gauss-GVNSGauss-VNS-LS1在计算解的方案的，情况下的时间复杂度为𝑂(𝑛𝑇𝑀𝐴𝑋)，其中𝑛为实例中需要传输的文件数目，𝑇𝑀𝐴𝑋为实例中的上界。当实例的规模很大时，文件数𝑛和𝑇𝑀𝐴𝑋也会很大，这会使得计算解FTSP的基于局部搜索的启发式算法Modified-VNS。接下来，本小节将详细介绍新算法本文使用𝑛维向量𝑥=[𝑥1,𝑥2,…,𝑥𝑛]FTSP的解，其中𝑛表示需要传输的文件的数目，𝑥𝑖表示第𝑖个被调度的文件的索引。例如对于图3.1表示的实例，向量𝑥=[2,4,5,1,3]表示按照[𝑒2,𝑒4,𝑒5,𝑒1,𝑒3]的顺序来调度文件。3.1解𝑥Fig. Anexampleoftransformingsolutionrepresentation𝑥toa0，表示端口下一个可用的时刻𝑡按照向量𝑥表示的顺序确定每个文件的开始时间。例如对文件𝑒𝑥𝑖，弹出文𝑒𝑥𝑖关联的两个节点𝑣𝑠𝑡𝑎𝑟𝑡和𝑣𝑒𝑛𝑑对应的堆顶元素，记为𝑡1和𝑡2。显然，𝑡1和𝑡2分别表示节点𝑣𝑠𝑡𝑎𝑟𝑡和𝑣𝑒𝑛𝑑最近的可以开始传输新的文件的时间。取𝑡1和𝑡2的最大值，记为𝑡𝑚𝑎𝑥 即𝑡𝑚𝑎𝑥=max𝑡1𝑡2}。令𝑡𝑚𝑎𝑥为文件𝑒𝑥的开始时间，即𝑠(𝑒𝑥)=𝑡，并将𝑡+𝑙(𝑒𝑥)分别放 那么，解𝑥对应的调度方案的目标函数值𝑓(𝑥𝑚𝑎𝑥1≤𝑘≤𝑛(𝑠(𝑒𝑘𝑙(𝑒𝑘))，即所有文3.3根据解𝑥Tab. Buildschedulingaccordingtosolution输入：文件传输图和𝑛维向量表示的解𝑥=[𝑥1𝑥2𝑥𝑛]初始化：对每一个节点𝑣𝑉，构建大小为𝑝(𝑣)的最小堆𝐻𝑣，堆𝐻𝑣中的元素为每一个端口下一个可用的时刻𝑡，初始时均为0。𝑡𝑚𝑎𝑘𝑒𝑠𝑝𝑎𝑛=𝑭𝒐𝒓𝑖=0;𝑖<𝑛;𝑖=𝑖+/∗𝑉𝑒𝑟𝑡𝑒𝑥𝑣𝑠𝑡𝑎𝑟𝑡𝑎𝑛𝑑𝑣𝑒𝑛𝑑𝑎𝑟𝑒𝑒𝑑𝑔𝑒(𝑓𝑖𝑙𝑒)𝑒𝑥𝑖′𝑠𝑡1=𝐻𝑣𝑠𝑡𝑎𝑟𝑡. 𝐻𝑣𝑠𝑡𝑎𝑟𝑡.𝑡2=𝐻𝑣𝑒𝑛𝑑. 𝐻𝑣𝑒𝑛𝑑.𝑡𝑚𝑎𝑥=max(𝑡1,𝑡2)𝑠(𝑒𝑥𝑖)=/∗𝑈𝑝𝑑𝑎𝑡𝑒𝑀𝑖𝑛𝐻𝑒𝑎𝑝𝐻𝑣𝑠𝑡𝑎𝑟𝑡𝑎𝑛𝑑𝐻𝑣𝑒𝑛𝑑𝑡𝑒𝑛𝑑=𝑡𝑚𝑎𝑥+𝐻𝑣𝑠𝑡𝑎𝑟𝑡.𝐻𝑣𝑒𝑛𝑑./∗𝑈𝑝𝑑𝑎𝑡𝑒𝑡𝑚𝑎𝑘𝑒𝑠𝑝𝑎𝑛𝑰𝒇𝑡𝑒𝑛𝑑>𝑡𝑚𝑎𝑘𝑒𝑠𝑝𝑎𝑛=输出：所有文件的开始传输时间𝑠(𝑒)和𝑡𝑚𝑎𝑘𝑒𝑠𝑝𝑎𝑛3.13.3中描述的方法，解𝑥对应的调度方案为：文件𝑒1，𝑒40开始传输，文件𝑒5从时刻1开始传输，而文件𝑒2和𝑒3从时刻2开始传输。该调度方案的目标函数值——为利用列表调度算法构建解𝑥对应的调度方案时，在每一个时刻都需要扫描整个文件3.3中描述的算法利用最小堆数的FTSP的求解，这也是新的解的表示方式另一个优势所在。在本文新算法Modified-VNS中，变邻域搜索时使用的邻域集合为{𝑁𝑘(𝑥|𝑘𝑚𝑖𝑛≤𝑘≤𝑘𝑚𝑎𝑥}，𝑘𝑚𝑖𝑛和𝑘𝑚𝑎𝑥均为预先设置的参数。其中，邻域𝑁𝑘(𝑥)=和𝑥最多有𝑘个位置不同}3.4生成解𝑥的邻居解𝑥′∈Tab. Generateneighborsolution𝑥′∈𝑁𝑘(𝑥)ofsolution输入：𝑛维向量表示的解𝑥=[𝑥1𝑥2𝑥𝑛]，参数𝑘𝐺𝑒𝑛𝑒𝑟𝑎𝑡𝑒𝑘𝑛𝑢𝑚𝑏𝑒𝑟𝑠𝑖𝑛𝑡ℎ𝑒𝑟𝑎𝑛𝑔𝑒[1,𝑛]𝑎𝑡𝑟𝑎𝑛𝑑𝑜𝑚,𝐺𝑒𝑛𝑒𝑟𝑎𝑡𝑒𝑎𝑝𝑒𝑟𝑚𝑢𝑡𝑎𝑡𝑖𝑜𝑛𝑜𝑓[1,2,…,𝑘]𝑎𝑡𝑟𝑎𝑛𝑑𝑜𝑚,[𝑖𝑛𝑑𝑒𝑥1,𝑖𝑛𝑑𝑒𝑥2,…,𝑥′=𝑭𝒐𝒓𝑖=1;𝑖≤𝑘;𝑖=𝑖+𝑥′[𝑓𝑖𝑙𝑒𝐼𝑛𝑑𝑒𝑥𝑘]=𝑥[𝑓𝑖𝑙𝑒𝐼𝑛𝑑𝑒𝑥𝑖𝑛𝑑𝑒𝑥输出：邻居解𝑥′对于解𝑥，生成邻居解𝑥𝑁𝑘(𝑥)3.4,,…,其中1≤𝑓𝑖𝑙𝑒𝐼𝑛𝑑𝑒𝑥𝑘≤𝑛，𝑛为需要传输的文件的数目。（2）[1,2𝑘]的一个置换，记为[𝑖𝑛𝑑𝑒𝑥1𝑖𝑛𝑑𝑒𝑥2𝑖𝑛𝑑𝑒𝑥𝑘]，其中1≤𝑖𝑛𝑑𝑒𝑥𝑘≤𝑘。（3）最后，令𝑥′=𝑥，并且令𝑥′[𝑓𝑖𝑙𝑒𝐼𝑛𝑑𝑒𝑥𝑘]=𝑥[𝑓𝑖𝑙𝑒𝐼𝑛𝑑𝑒𝑥𝑖𝑛𝑑𝑒𝑥𝑘](𝑥)𝑘令𝑥=[1,2,3,4,5]，那么𝑥′=[2,1,3,4,5]既是𝑥的𝑁2(𝑥)邻居解，又是𝑥的𝑁3(𝑥)邻居解。显然，𝑁3(𝑥)中邻居解的数目。在外层搜索中，如果在邻域𝑁𝑘(𝑥)中不能找到比当前找到更好邻居解的可能性也越高，只是花费的时间也会。Modified-VNS3.5所示，主要 范围为[𝑘𝑚𝑖𝑛,𝑘𝑚𝑎𝑥]，显然，𝑘𝑚𝑖𝑛和𝑘𝑚𝑎𝑥的取值会影响算法每次迭代时探索的邻域，进而𝑘𝑚𝑎𝑥=35移动规则。新算法Modified-VNS中的移动规则是，如果局部搜索子程序获得的邻居解𝑥′比当前的解𝑥要好（即𝑓(𝑥′𝑓(𝑥)），那么将进行𝑥向解𝑥′的移动，即将𝑥′作为当前解进行下一轮搜索。但是，由于FTSP本身的特性，多个解对应具有相同目标函数值的调度方案的情况会非常常见。也就是说，在探索当前解𝑥的邻域时，很可能会获得和解𝑥具有相同目标函数值的邻居解𝑥′3.13.2可知，解𝑥=[1,2,3,4,5]和解𝑥′=[1,5,4,3,2]对应的调度方案并不多样性，因此本文在算法Modified-VNS中设置了参数𝑝来控制这种特殊情况下是否进行移动。 部搜索子程序获得的邻居解𝑥′的目标函数值𝑓(𝑥′)=𝑓(𝑥)时𝑥向解𝑥′移动的概率为𝑝。在进行对比实验时，本文设置参数𝑝=0.4停止标准。本文算法Modified-VNS中将最大迭代次数作为算法停止质量越好，直至收敛。在进行对比实验时，本文将最大迭代次数设置为100。Modified-VNS和其它的变邻域搜索算法另一个不同之处。例如，当𝑘=𝑘𝑚𝑖𝑛，局部搜索子程序中使用的邻居定义也为𝑁𝑘𝑚𝑖𝑛(𝑥)。另数𝑁𝑆=50。3.5算法Modified-Tab. 𝑭𝒐𝒓𝑖𝑡𝑒𝑟𝑁𝑢𝑚=0;𝑖𝑡𝑒𝑟𝑁𝑢𝑚<𝑚𝑎𝑥𝐼𝑡𝑒𝑟𝑎𝑡𝑖𝑜𝑛;𝑖𝑡𝑒𝑟𝑁𝑢𝑚=𝑖𝑡𝑒𝑟𝑁𝑢𝑚+𝑭𝒐𝒓𝑘=𝑘𝑚𝑖𝑛;𝑘≤𝑘𝑚𝑎𝑥;𝑘=𝑘+/∗𝐿𝑜𝑐𝑎𝑙𝑆𝑒𝑎𝑟𝑐ℎ𝐿𝑒𝑡𝑥′=𝑥,𝑓(𝑥′)=𝑭𝒐𝒓𝑐𝑜𝑢𝑛𝑡=0;𝑐𝑜𝑢𝑛𝑡≤𝑁𝑆;𝑐𝑜𝑢𝑛𝑡=𝑐𝑜𝑢𝑛𝑡+𝐺𝑒𝑛𝑒𝑟𝑎𝑡𝑒𝑎𝑡𝑟𝑎𝑛𝑑𝑜𝑚𝑎𝑛𝑒𝑖𝑔ℎ𝑏𝑜𝑟𝑠𝑜𝑙𝑢𝑡𝑖𝑜𝑛𝑥′′∈𝑰𝒇𝑓(𝑥′′)<𝑥′=𝑥′′𝑎𝑛𝑑𝑓(𝑥′)=/∗𝑀𝑜𝑣𝑒𝑜𝑟𝑛𝑜𝑡𝑰𝒇𝑓(𝑥′)<𝑥=𝑥′,𝑓(𝑥)=𝑓(𝑥′)𝑎𝑛𝑑𝑬𝒍𝒔𝒆𝒊𝒇𝑓(𝑥′)=𝑥=𝑥′,𝑓(𝑥)=𝑓(𝑥′)𝑎𝑛𝑑𝒃𝒓𝒆𝒂𝒌𝑤𝑖𝑡ℎ𝑝𝑟𝑜𝑏𝑎𝑏𝑖𝑙𝑖𝑡𝑦本文新算法Modified-VNS和其它的基于局部搜索的启发式算法的不同之处Modified-VNS中设计了更简单的解的表示方式以及将解转Modified-VNS中，局部搜索子程序使用了具有更大变化的邻域定义，即和外层搜索时使用的邻域定义𝑁𝑘(𝑥)保持一致——3.2解𝑥′Fig. Anexampleoftransformingsolutionrepresentation𝑥′toa本章小本章节首先介绍了本文两个新的时间索引的整数规划模型M3和M4，然后介绍了本文新的求解FTSP的基于局部搜索的启发式算法Modified-VNS。和现有的整数规划模型M1和M2相比，本文新模型M3使用不同的表示方数。在此基础上，本文又在新模型M3中引入基本下界𝐸𝐿𝐵，获得了另一个新模型M4。基本下界的引入使得和新模型M3相比，新模M4的约束数又减少了很多。显然，本文模型M3和M4具有更小的规模——更少的约束数和变量数，因此理论上在求本文的两个新模型M3和M4的优越性。和现有的启发式算法相比，本文新算法Modified-VNS中定义了不同的解的Modified-VNS在计算解的目FTSP问题本身的特性，邻居解变化太小的话很容易导致解对应的调度方案，甚至是目Modified-VNS中局部搜索子程序使用的是邻居Modified-VNS和现有的启发式算法的对比实验，从而验证新算法Modified-VNS的优越性。实验结果与分实验环境和实例本文是在配置Windows10系统的笔记本电脑上进行的数值实验，其中CPU型号为Ini5-8250U，主存容量大小为8GB。实现算法时使用的编程语言均为C++，IDE为最大的求解时间为600秒。本文中使用的实例是随机生成的，表4.1展示了随机生成的实例的节点数和边数。生成边的长度时保证每一条边的长度均匀分布在[1𝑒𝑚𝑎𝑥]上。参数𝑝𝑚𝑎𝑥指的是节点的最数时保证每一个节点的端口数均匀分布在[1𝑝𝑚𝑎𝑥]上。另外，本文在进行实验时会保证4.1实例的规模大小Tab. Instance554.1Tab. 整数规划模型的实验结详细的实验结果分别展示在表4.2，表4.34.4中。表4.24.4中的“ntan”列记录了实例的名字，其中包含四个数一个数字表示文件传输图点的数目|𝑉|，第二个数字表示文件传输图中边的数目|𝐸|，第三个数字和第四个数字分别表示生成文件传输图时设置的节点的最大端口数𝑚𝑎𝑥和文件的最大长度𝑚𝑎𝑥ftp_5_40_10_20540条边的文件传输(0,20]的均匀分布行数值实验时，每一个相同的实例名（具有相同的参数）都生成10个不同的实例，秒内无法求解这10个实例中的任何一个（超时或者内存不足）。另外，本文在计算多无法求解的实例则不包含在内。例如对于表4.3中展示的中规模实例理时间内（600s）M3的“#Opt7，“t(s)”列对7个，并且这7个实例的平均求解时间为177.2秒。表 Tab. Comparisonofdifferentmodelsonsmall-scale 0-0-40-0-0-20-90-820-0-0-54.1-是根据4.2绘制的，统计了模M1，M2，M3M4求4.14.2解的中规模实例的数目，图4.4展示了各个模型求解所有中规模实例的平均求解时间；M1，M2，M3M4求解大规模实例的4.54.6展示了各个模型求Small-scaleSolved2Unsolved00theSmall-scaleSolved2Unsolved00thenameofthenumberof

Small-scale50 theSmall-scale50 thenameofaveragesolving4.1可以得于规模比较小的（50个节点，100个文件），M116032M2，M3根据图4.2可知，本文新模型M3和M4花费的时间更少，尤其是M4。具体而M2相比，模M3平均花费的时M23.6%，而模型M4更是只花费了模型M2所需时间的0.4%。根据4.34.5可以得M1无法求解任何中规模和大规模实M2可以求解的中规模和大规模实例的数目也远小于本文模型M3和M4，尤其是模M4。例如，160M254个，280M2只能求解129个，均不50%160个中规模实M3109个，280个大规模实M3可以求解202个，求解比例分别约为68%和70%，显然模型M3能求解的中规模和大规M24.44.6M3求解中规模和大规模实例时所需的求解时间也要小于模型M2，仅需要模型M2求解时间的54.4%和75.0%实例（高100个节点，600条边）4.44.6可知，和模M2相比，求解中规模实例时，模型M4平均仅花费了模型M2求解时间的4.0%左右；求解大规模实例时，模型M4平均仅花费了模型M2时求解时间的19.0%左右。4.3Tab. Comparisonofdifferentmodelsonmedium-scale0-0-50-30-60-0-70-480-90-0-90-0-0-0-0-0-0-0-10-0-30-190-0-80-80-48划模型M3和M4均能在合理时间（600s）求解的实例数并且花费更少的时间。其M1仅能求解总实例数目（600个）5.3%M2仅能求解总实例数目（600个）的56.8%，而本文模型M3和M4则能求解的实例，具体而言，模型M3可以（600个78.5%，模M4表现更99.7%的实例。在求解时间方面，和现有的求解最快的M2相比M3平均需要模型M272.2%M4M214.3%。要优于现有的整数规划模型M1和M2。Medium-scaleSolved Unsolved00Medium-scaleSolved Unsolved00thenameofMedium-scale500 thenameofthenumberofaveragesolving

图4.4求解中规模实例的平均求解时间Fig.4.4 Averagetimeofsolvingmedium-scale4.4Tab. Comparisonofdifferentmodelsonlarge-scale0-0-10-0-10-40-0-60-80-90-60-70-0-30-0-60-120-50-0-190-90-384.4Tab. 0-0-0-480-150-280-0-0-0-880-0-0-0-170-0-0-8图4.5求解大规模实例的实验结果Fig.4.5 Resultofsolvinglarge-scale

Large-scaleUnsolved Solved20theLarge-scaleUnsolved Solved20thenameofLarge-scale500 thenameofthenumberofaveragesolving本文也比较了本文新模型M3，M4和现有模型M1，M2规模的大小，即约M14.5中展示看出，和模型M1相比，模型M2的约束数大大减少，但是变量数却增多。而本文提出的两个模型M3和M4，和模型M1相比，变量数不变，而约束数大大减少；和模型M2相比，变量数和约束数都减少了。其中，和模M1相比，模M3的约束数平均减少了96.37%M497.47%M2M3的变量数平均减少了约49.79%，约束数平均减少了约37.29%；模型M4的变量数平均减少了约49.79%，约束数平均减少了约56.23%。4.5Tab. Comparisonofthenumberofvariablesandconstraintsofdifferent thenameoftheaveragenumberofFig.4.7 TheaveragenumberofvariablesforallinstancesinTab.4.5

thenameoftheaveragenumberofthenameoftheaveragenumberof启发式算法的实验结VNS，Gauss-GVNSGauss-VNS-LS1的的启发式算法VNS，Gauss-GVNS，Gauss-VNS-LS1和本文新算法Modified-VNS本文首先将本文新算法Modified-VNS和现有的启发式算法VNS，Gauss-GVNS，Gauss-VNS-LS1进行了对比实验，详细的实验数据在表4.64.6中件传输图点的数目|𝑉|，边（文件）的数目|𝐸|，生成节点的端口数时最大的端口数表4.6中“t(s)”列记录了各启发式算法的求解时间，单位为秒（second）本文已经提出了更好的整数规划模型M4，它可以在合理的时间内求出大规模实例数值之间的差距，其详细的定义如下所示。记启发式算法获得的解为𝑥，模型M4求得𝑓(𝑥)𝑚𝑎𝑘𝑒𝑠𝑝𝑎𝑛𝐺𝑎𝑝=

Modified-VNS中有一些需要预先设置的参数，本次实验中参数设置如下所示。其中，𝑘𝑚𝑖𝑛=15，𝑘𝑚𝑎𝑥=35100次，局部搜索子程序中使用的参数𝑁𝑆=50。数据，如表4.6所示。均可以获得最优解（即Gap为0），例如实例“ftsp_300_600_150_300”。而对于另外一4.94.10则展示了各启4.6Tab.

Modified-00000000000000000000000000000000000000000000000000000004.6Tab.

Modified-000000000000000000000000Modified-Fig. Comparisonofsolutionofheuristic根据图4.9可知，在大多数情况下，本文启发式算法Modified-VNS获得的解的质量都比现有的启发式算法VNS，Gauss-GVNSGauss-VNS-LS1要好，尤其当实例Modified-VNS在求解大规模实例时获得的解与最优解之间的差距也很小，均小于0.01。更重要的是，根据图4.10可以看出，本文启发式算法Modified-VNS的求解时间也远远小于这些现有的启发和算法VNS相比Modified-VNS平均仅需其约6.2%的求解时间；和算法Gauss-GVNS相比，新算法Modified-VNS5.6%Gauss-VNS-LS1相比，本文新算法Modified-VNS平均也只需要其约14.4%的求解时间。0Modified-0Modified-Fig. Comparisonofsolvingtimeofheuristic本文还进行了新算法Modified-VNS和本文整数规划模型M4之间的对比实划模型M4获得的最优解的𝑚𝑎𝑘𝑒𝑠𝑝𝑎𝑛的差值。M4FTSP实例的最优解。当实例规模比较M4FTSP实例的最优解。例如对于实例比算法Modified-VNS花费的时间还要更少。但是当实例规模逐渐增大时，求解时间也甚至不能在合理的时间内（600s）求出最优解。而启发式算法Modified-VNS虽然不能保证获得的解的质量，但是对于大规模的实例（100个节点，1000条边），仍然可以在Tab. ComparisonofModelM4andModified-VNSonlarge-scale Model ------24.11展示了模型M4Modified-VNS获得的解的目标函数值𝑚𝑎𝑘𝑒𝑠𝑝𝑎𝑛的对比，而图4.12展示了模型M4Modified-VNS求解时间的对比。4.11Modified-VNS获得的解虽然不一定是最优解，解时间增长很快，而算法Modified-VNS的求解时间增长很平缓，几乎在十秒以内就可显然，本文算法Modified-VNS和模型M4求解结果之间的对比进一步展现Modified-VNSM4是时间索引FTSPModified-VNS，应用于文件长度不为整数的FTSPModified-VNS的另一优势所在。900800700Model900800700Model6005004003002001000300250Model200150100500Fig.4.11 ComparisonofsolutionofModelM4andModified-VNS

4.12ModelM4Modified-VNSFig.4.12 ComparisonofsolvingtimeofModelM4andModified-VNS本章小,所有文件的长度都均匀分布在[0𝑒𝑚𝑎𝑥]上。之后，本章展示了本文新模型M3和M4与现有的模型M1和M2之间的对M3M4M1M2多，并且求解时间也更少。具体来说，对于所有实例（共600个），模型M1仅能求解其中约5.3%的实例模型M2仅能求解其中约56.8%的实例而本文新模型M3和M4则能求解的实例，模型M3可以求解其中约78.5%的实例，模型M4表现更好，可99.7%M2M3平均需要其求解时间的72.2%左右，而模型M4平均仅需其求解时间的14.3%左右。最后，本章也展示了本文新的启发式算法Modified-VNS和现有的启发式算Modified-VNS不仅获得的解的质量要优于解速度最快的启发式Gauss-VNS-LS1相比，新Modified-VNS平均也只需要其约14.4%的求解时间。显然，大量的实验结果验证了本文新模型M3和M4，尤其是模型M4，以及新的启发式算法Modified-VNS的优越性。 FTSP，即给定节点和需要在34，其中，模型4是在模型3的基础上引入基本下界获得的。通过不同的决策变量和约束的定义方式，和现有的整数规划模型相比，本文两个新模型3和4具有更一点。和现有的性能最好的模型2相比，新模型3和4可以求解的实例的规模更大，花费的求解时间也更少，尤其是模型4。具体而言，求解小规模实例时，模型4平均只花费了现有的最好的模型2所需时间的0.4%左右；求解中规模实例时，模型4平均仅花费了模型2求解时间的4.1%左右；求解大规模实例时，模型4平均仅21.%4214.3%左右。M3M4FTSP，并且随着问题Modified-VNSModified-VNS和现有的基于局部搜索的启发式算法的对比实验，验证了新算法Modified-VNS的优越性。具体而言，本文新算法Modified-VNS不仅能够获得更高质量的解（和最优解之间的gap小于0.01），并且即使和现有的求解速度最快的启发式算法相比，也只需要其约14.4%的求CoffmanJrEG,GareyMR,JohnsonDS,etal.Schedulingfiletransfersinadistributednetwork[C]//ProceedingsofthesecondannualACMsymposiumonPrinciplesofdistributedcomputing.1983:254-266.Coffman,JrEG,GareyMR,JohnsonDS,etal.Schedulingfiletransfers[J].SIAMJournaloncomputing,1985,14(3):744-780.ChoiHA,HakimiSL.Schedulingfiletransfersfortreesandoddcycles[J].SIAMJournalonComputing,1987,16(1):162-168.WhiteheadJ.Thecomplexityoffiletransferschedulingwithforwarding[J].SIAMJournalonComputing,1990,19(2):222-245.MaoW.Directedfiletransferscheduling[C]//ACM31stAnnualSoutheastConference(ACM-SE1993).1993:199-203.NakanoSI,NishizekiT.Schedulingfiletransfersunderportandchannelconstraints[J].InternationalJournalofFoundationsofComputerScience,1993,4(02):101-115.VeeraraghavanM,ZhengX,FengW,etal.Schedulingandtransportforfiletransfersonhigh-speedopticalcircuits[J].JournalofGridComputing,2003,1(4):395-405.MaoW,SimhaR.Routingandschedulingfiletransfersinpacketswitchednetworks[J].JournalofComputingandInformation,1994,1(1):559-574.HavillJT,MaoW,SimhaR.Alowerboundforon-linefiletransferroutingandscheduling[C]//Proceedingsofthe1997ConferenceonInformationSciencesandSystems.1997:225-230.HavillJT,MaoW.GreedyOn-LineFileTransferRouting[C]//Euro-PDS.1997:JiaS,JinX,GhasemiesfehG,etal.Competitiveysisforonlineschedulinginsoftware-definedopticalWAN[C]//IEEE2017-IEEEConferenceonComputerCommunications.IEEE,2017:1-9.LinC,BiY,HanG,etal.Schedulingfortime-constrainedbig-filetransferovermultiplepathsincloudcomputing[J].IEEETransactionsonEmergingTopicsinComputationalInligence,2018,2(1):25-40.SousaJP,WolseyLA.Atimeindexedformulationofnon-preemptivesinglemachineschedulingproblems[J].Mathematicalprogramming,1992,54(1):353-HigueroD,TiradoJM,IsailaF,etal.Enhancingfiletransferschedulingandserverutilizationindatadistributioninfrastructures[C]//2012IEEE20thInternationalSymposiumonModeling,ysisandSimulationofComputerandmunicationSystems.IEEE,2012:431-DražićZ,SavićA,FilipovićV.Anintegerlinearformulationforthefiletransferschedulingproblem[J].Top,2014,22(3):1062-1073.DražićZ.Modificationsofthevariableneighborhoodsearethodandtheirapplicationstosolvingthefiletransferschedulingprob