文件傳輸調(diào)度問題算法研究

M3M4。與現(xiàn)有的M1M2相比，通過不同的決策變量和約束的表示方式，本文提出了具有更少變M3M3中引入基本下界，進(jìn)一步減M4。本文進(jìn)行了大量的數(shù)值實(shí)驗(yàn)，驗(yàn)證了本文新模型M3和M4的優(yōu)越性。與現(xiàn)有的最好的整數(shù)規(guī)劃模型相比，求解相同的實(shí)例時(shí)本文新模型M4平均只需要其約14.3%的時(shí)間另外，本文新模型M4可以求解更大規(guī)模的實(shí)例（100個(gè)節(jié)點(diǎn)，600條邊），150秒，而現(xiàn)有的模型在合理的時(shí)間內(nèi)（600秒）無法求解這樣的實(shí)例。Modified-VNS的高效性。和現(xiàn)有的基于局部搜索的啟發(fā)式算法相比，本文算法Modified-VNS獲得的解不僅具有更高的質(zhì)量（和最優(yōu)解之間的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........................................................................................................................ 緒 問題定 國(guó)內(nèi)外研究現(xiàn) 本文主要貢 章節(jié)介 求解文件傳輸調(diào)度問題的現(xiàn)有方 FTSP相關(guān)定 ????????????????的定 FTSP的公式化定 求解FTSP的整數(shù)規(guī)劃模 現(xiàn)有的整數(shù)規(guī)劃模型 現(xiàn)有的整數(shù)規(guī)劃模型 求解FTSP的啟發(fā)式算 局部搜索的相關(guān)概 通用的局部搜索算 通用的變鄰域搜索算 現(xiàn)有的求解FTSP的啟發(fā)式算 本章小 改進(jìn)的新模型和新的啟發(fā)式算 新的整數(shù)規(guī)劃模型M3和 新的整數(shù)規(guī)劃模型 進(jìn)一步改進(jìn)的整數(shù)規(guī)劃模型 和現(xiàn)有整數(shù)規(guī)劃模型的對(duì) 新的啟發(fā)式算法Modified- 解的表示方 鄰域的定 新的啟發(fā)式算法Modified- 本章小 實(shí)驗(yàn)結(jié)果與分 本文主要研究求解文件傳輸調(diào)度問題（FileTransferSchedulingProblem，F(xiàn)TSP）的問題定文件傳輸調(diào)度問題可以用無向圖??=(??,??)來表示，即文件傳輸圖（FileTransferGraph），1.1所示。其中，圖中的節(jié)點(diǎn)??∈??表示分布式網(wǎng)絡(luò)中的計(jì)算機(jī)，每?jī)蓚€(gè)1.1文件傳輸調(diào)度圖Fig. Filetransfer??4和??5），滿足端口約束意味著節(jié)點(diǎn)??3最多只能同時(shí)傳輸這三個(gè)文件中的兩個(gè)Coffmanetal.[1-2]提出，描述該問題的文件傳輸圖也是由FTSP，并且不允許文件經(jīng)Coffmanetal.研究了具有不同特征的文件傳輸調(diào)度問題的復(fù)雜度，其中涵蓋了很多特殊的情況，比如文件傳輸圖點(diǎn)的端口數(shù)均為1，每一對(duì)節(jié)點(diǎn)間最多只有一條邊，NP-hard，而在一些特殊的FTSP（例如文件的長(zhǎng)度相同，或者文件傳輸圖是二分圖等）是存在多項(xiàng)式時(shí)間復(fù)雜度的算法的。另外，Coffmanetal.FTSP的基本下NP-hardNakanoNishizeki考慮了帶有端口約束和通道約束的除此之外，也有一些研究者更關(guān)注FTSP在更復(fù)雜的實(shí)際場(chǎng)景中的應(yīng)用。例如，Veeraraghavanetal.研究了高速光電路中文件的調(diào)度和傳輸問題[7]。另外，MaoSimha調(diào)度和路由問題（FileTransferRoutingandScheduling）[8]。他們提出了三個(gè)貪心的列表調(diào)度算法（GreedyListScheduling），并證明了這些算法的高效性。之后，Havill，Mao和Simha首次考慮了的文件傳輸調(diào)度和路由問題（On-LineFileTransferRoutingandSchedulingMao也提出了一個(gè)簡(jiǎn)單的貪心算法，并給出了該算法的競(jìng)爭(zhēng)比[10]。另外，Jiaetal.還分析[11]。Linetal.則研究了在云計(jì)算中大文件傳輸?shù)恼{(diào)度問題，并提出了求解該問題的FTSP的法已經(jīng)在不同的調(diào)度問題的求解中得到了很廣泛的應(yīng)用[13]，Higueroetal.首次將該方法外，Dra?i?Zetal.重新模型化了文件傳輸時(shí)間為整數(shù)的FTSP，并且首次提出了求解該問節(jié)點(diǎn)，200個(gè)文件），但是求解時(shí)間依舊很長(zhǎng)，仍然存在可提升的空間?？紤]到現(xiàn)有的整數(shù)規(guī)劃模型的缺點(diǎn)，本文提出了兩個(gè)新的更好的求解FTSP的整數(shù)規(guī)劃模型。雖然包括整數(shù)規(guī)劃在內(nèi)的精確方法可以保證獲得的解是最優(yōu)的，但是由于問題FTSP本身固有的復(fù)雜性，隨著實(shí)例規(guī)模的增大，求解時(shí)間將呈指數(shù)增長(zhǎng)，很難在合理Akbarietal.HopfieldFTSP[17]。但Algorithm，GA）[25]和變鄰域搜索算法（VariableNeighborhoodSearch，VNS）[26-27]等。模擬退火算法和搜索算法都是采用允許往比當(dāng)前解更壞的鄰居解移動(dòng)的策略來避了廣泛的關(guān)注[28-29]，Dra?i?ZFTSPFTSP的基FTSP的基于變鄰域搜索的啟發(fā)式算法，以及兩個(gè)新的求解FTSP的局部搜索子程FTSP的基于局部搜索的啟發(fā)式算法，但是這些算法求解大FTSP的啟發(fā)式算法性能不夠的求解FTSP的啟發(fā)式算法。本文主要貢M3M4。通過更改決策變量和約束的定義方式，本文新模型M3和M4具有更小的規(guī)模——更少的約束數(shù)和變量數(shù)。本了大量的數(shù)值實(shí)驗(yàn)，驗(yàn)證了新模型M3和M4的優(yōu)越性。和現(xiàn)有的整數(shù)規(guī)劃模型相比，求解相同實(shí)例時(shí)新模型M3M4會(huì)花費(fèi)更少的求解時(shí)間，因此可以在合理的時(shí)間內(nèi)（600s）求解更大的實(shí)例，高達(dá)100個(gè)節(jié)點(diǎn)，600條邊。本文的第二個(gè)工作是設(shè)計(jì)了更高效的基于局部搜索的啟發(fā)式算法Modified-VNS。通過設(shè)計(jì)不同的解的表示方式，本文算法可以在更短的時(shí)間內(nèi)解析出解對(duì)應(yīng)的調(diào)發(fā)式算法相比，本文新算法Modified-VNS可以獲得更高質(zhì)量的解，并且花費(fèi)更章節(jié)介本文在第2章介紹了文件傳輸調(diào)度問題的相關(guān)概念以及求解該類問題的方法——本章節(jié)首先將詳細(xì)介紹本文研究的文件傳輸調(diào)度問題（FileTransferSchedulingProblem，F(xiàn)TSP）的更公式化的定義，然后介紹求解文件傳輸調(diào)度問題的兩大類FTSP，考慮的約束包括節(jié)點(diǎn)的端口約束和文FTSP中，一個(gè)調(diào)度??可以視為一個(gè)函數(shù)????0，給每一個(gè)文件????都分配一個(gè)開始時(shí)間??(??)。令??(??)表示在調(diào)度方案??對(duì)應(yīng)的每一個(gè)文件??∈??的開始傳輸時(shí)間，max??(??)+ 2.1給出了一個(gè)時(shí)序圖表示的文件調(diào)度方案，圖中表示文件??1，??4和??5輸?shù)奈募??3，在時(shí)刻5完成傳輸，那么該調(diào)度方案的????????????????為5。1：令調(diào)度方案????0FTSP的可行解，那么一定存在調(diào)度方案??????使得??????(??′′)≤??????(??′)[15]定理1中的??????(??′)表示調(diào)度方案??的????????????????。由于文件的傳輸時(shí)間都是整數(shù)，定理1→個(gè)文件??∈??都分配一個(gè)整數(shù)的開始時(shí)間??(??)FTSPFTSP可以模型FTSP給定文件傳輸圖??=(????)，其中每一個(gè)節(jié)點(diǎn)????關(guān)聯(lián)一個(gè)整數(shù)的端口數(shù)??(??)，每一條邊??∈??關(guān)聯(lián)一個(gè)整數(shù)的文件傳輸時(shí)間??(??)FTSP的調(diào)度方案可以描述為函數(shù)????其中，端口約束指的是對(duì)于任意一個(gè)節(jié)點(diǎn)??∈??和任意一個(gè)時(shí)刻??≥|{??:??是??需要傳輸?shù)奈募⑶??(??)≤??<??(??)??(??)}|≤??(??)不允許中斷。另外，本文研究的FTSP中認(rèn)為任意兩個(gè)節(jié)點(diǎn)之間均具有直接相連的通信2.1一個(gè)調(diào)度方案Fig. A求解FTSP的整數(shù)規(guī)劃模關(guān)注的求解FTSP的精確方法也是這種。為了方便和本文新的整數(shù)規(guī)劃模型進(jìn)行本小節(jié)將介紹由Dra?i?Zetal.整數(shù)規(guī)劃模型[15]，記為模型M1。模型M1中1,eτ??????=

0,

其中，文件??τ對(duì)應(yīng)的時(shí)間段[??1??]是活躍的，也即文件??τ對(duì)應(yīng)的時(shí)間段[??1??]??????????????∑??????????????=??(??),???∈∑??∈??,???????????≤??(??),?????????????????∑??????????????=??(??),???∈∑??∈??,???????????≤??(??),???∈??,1≤??≥????????,???∈??,1≤??≤??????≥??????+???????1,???∈??,1≤≤<??<??≤??????∈{0,1},???∈??,1≤??≤??∈其中，約束（2.4）確保每一個(gè)文件??∈??都在????????之前被完整地傳輸。約束（2.5）（2.6束（2.7）例如如果文件??∈??在時(shí)間段??和時(shí)間段??活躍，那么它一定在滿足??<??<??的任一時(shí)間段??活躍。約束（2.8）保證了??????是個(gè)二進(jìn)制變量，而約束（2.9）保證了變量??，即調(diào)度的模型M1的變量數(shù)為|??|????????+1，而約束數(shù)為|??||??|????????+|??|?????????|??|?∑?????????2???(??+1)。盡管 是預(yù)先求得的常量，但是 實(shí)際和文件數(shù) 以及節(jié)點(diǎn)數(shù)|??|M1具有關(guān)于|??|和|??|偽多項(xiàng)式的約束數(shù)。顯然，當(dāng)實(shí)例有|??|?∑?????????2???(??+1)個(gè)約束。當(dāng)文件的數(shù)目和??非常大的時(shí)候，由公式（2.7）引入 本小節(jié)將介紹由Dra?i?Z另一個(gè)整數(shù)規(guī)劃模型[16]，記為模型M2。和模型1,eτ??????= 0,引入變量??????之后，文件傳輸?shù)倪B續(xù)性約束可以表示為如下形式∑??????????????=1,???∈ ???????????(???1)≥??????,???∈??,2≤??≤ ????1=????1,???∈ ????????????????????????????∑??????????????=??(??),???∈∑??∈??,???????????≤??(??),???∈??,1≤≤??≥????????,???∈??,1≤??≤∑??????????????=1,???∈???????????(???1)≥??????,???∈??,2≤≤????1=????1,???∈??????∈{0,1},???∈??,1≤??≤??∈數(shù)目大大減少，即由原來的|??|∑?????????2???(??+1)減小為|??||??|?? M2的變量數(shù)卻增多了，從原來的|??|?????????+1增加為2?|??|?????????+1，幾乎增加了一倍。不過后模M2的性能有了比較大的提M1相點(diǎn)，200個(gè)文件）。盡管和模型M1相比，模型M2的性能有了一定的提升，但是最根本的問題并沒有M2求解FTSP的啟發(fā)式算本文研究的問題FTSP已經(jīng)被證明是NP-hard的最優(yōu)化問題[1-2]。在研究求解某個(gè)問NP類問題則無法找到求解該問題的多項(xiàng)式時(shí)間復(fù)雜度的算法。其中，多項(xiàng)式時(shí)間復(fù)雜??(??(??))求解最優(yōu)化問題的方法一般可以分為兩類——精確方法和啟發(fā)式算法。對(duì)于像FTSPNP-hard最優(yōu)化問題，精確方法雖然可以保證獲得的解一定是最優(yōu)解，但的整數(shù)規(guī)劃模型的設(shè)計(jì)，還關(guān)注求解FTSP的啟發(fā)式算法的設(shè)計(jì)。????:??→?表示目標(biāo)函數(shù)。目標(biāo)函數(shù)??給每一個(gè)解??∈??分配一個(gè)實(shí)數(shù)的目標(biāo)函數(shù)值，可以min??.??.??∈

前，本文將首先引入一個(gè)重要的概念——鄰域（Neighborhood）和鄰居解（Neighbor鄰域和鄰居解：鄰居函數(shù)??給每一個(gè)解??∈??都分配了一個(gè)鄰居解的集合??(??)，??(??)即解??的鄰域。如果解??′∈??(??)，那么稱解??′是解??的鄰居解。min??(??)=??1+??2+??.??.??∈

令??(??)={??′||??′???|2≤1}。那么當(dāng)??=(1,1,1)時(shí)，其鄰域??(??){(0,1,1),(1,0,1),(1,1,0),(2,1,1),(1,2,1),(1,1,2)}，如圖2.2所示。2.2鄰居解Fig. Neighbor前解的鄰域中選擇一個(gè)更好的鄰居解來取代當(dāng)前的解，如圖2.3所示。當(dāng)所有的鄰居解2.4中，如果將???作為初始解開始搜索，那么得到局部最優(yōu)解??′后算法2.3局部搜索的思想Fig. Theprincipleoflocal，搜索算法，遺傳算法，變鄰域搜索算法等。其中，模擬退火算法和搜索算法都是通過允許選擇比當(dāng)前解更差的鄰居解來跳出局部最優(yōu)因buit），通過向近的居解移2.4局部搜索Fig. Local2.5所示，在第一種鄰域定義中，解???已經(jīng)是局解的表示方式，鄰居的定的移動(dòng)規(guī)則和搜索的停止規(guī)則。2.5包含兩種鄰居的變鄰域搜索Fig. Variableneighborhoodsearchusino有解，因此需要花費(fèi)更久的時(shí)間。表2.1中描述的是第一種鄰居選擇策略。2.1局部搜索Tab. Local′∈2.2描述了通用的變鄰域搜變鄰域搜索通常需要預(yù)先指定包含多種鄰域定義的集合????(??=1,2????????)????????為預(yù)先定義的常數(shù)，可以通過這個(gè)參數(shù)來控制不同鄰域的數(shù)目。如果????????比較大，變鄰域搜索類似于多個(gè)局部搜索算法；如果????????比較小，例如????????=1時(shí)，那么變鄰域個(gè)鄰域????(??)通常包含前一個(gè)鄰域?????1(??)：??1??2??????????。變鄰域搜索時(shí)首先會(huì)對(duì)當(dāng)前的解??進(jìn)行一個(gè)抖動(dòng)（shaking），隨機(jī)生成當(dāng)前解??鄰和當(dāng)前解??進(jìn)行比較，如果??(??′′)<??(??)，那么令??=??′′，并進(jìn)行下一次迭代。否則，繼續(xù)探索當(dāng)前鄰域????(??)的下一個(gè)鄰域????+1(??)，直至找到鄰居解??′′滿足條件??(??′′)<??(??)或者探索完最后一個(gè)鄰域????????(??)，如圖2.6所示。2.6變鄰域搜索的思想Fig. Theprincipleofvariableneighborhood時(shí)間地花費(fèi)在抖動(dòng)階段則可以將搜索到整個(gè)解空間潛在的包括更好的解的區(qū)域，即搜索整個(gè)解空間的區(qū)域。因此在設(shè)計(jì)基于變鄰域搜索的啟發(fā)式算法時(shí)，需要根據(jù)問本小節(jié)將簡(jiǎn)單介紹Dra?i?Zetal.求解FTSP的變鄰域搜索算法[30]記為VNS。VNS2.2中描述的通用的變鄰域搜索框架，嵌入的局部搜索子程序使2.1VNS中解的表示方式2.2Tab. 輸入：給定鄰域????，??=1,2????????。 令??=1，重復(fù)以下步驟，直至??>????????′∈??(??)′∈??(??)以??′為初始解進(jìn)行局部搜索，獲得局部最優(yōu)解??′′如果??(??′′)<??(??)，那么令??=??′′，??(??)=??(??′′)1。否則，令??=??+1。VNS中，作者使用??維向量??=(??1??2????)來表示=個(gè)節(jié)點(diǎn)在時(shí)刻??均有可用的端口，那么令文件??的開始傳輸時(shí)間??(??)=??，并繼續(xù)掃描接下來的文件。每完成一次文件列表的掃描，時(shí)刻????1，直至所有的文件都被分配一VNS算法中解的表示方式轉(zhuǎn)換成文件傳輸調(diào)度問題的具體調(diào)度然后是鄰域的定義。算法VNS中外層搜索時(shí)的鄰域集合為{????(??)????????≤??≤????????}，????????和????????均為預(yù)先設(shè)置的參數(shù)。????(??)的含義為 {??′|??′和??最多有個(gè)元素不同}。而變鄰域搜索中內(nèi)層局部搜索子程序的鄰域定義為??2(??)本小節(jié)將簡(jiǎn)單介紹Dra?i?Zetal.求解FTSP的變鄰域搜索算法[32]，記為Gauss-VNSGauss-VNSVNS相同的解的表示方式，不同之處Gauss-VNS中外層搜索時(shí)的鄰域集合為{??′(??),

≤??≤

為預(yù)先設(shè)置的參數(shù)。另外，預(yù)先給定參數(shù){????,????????≤??≤????????}。對(duì)于??，生成其鄰居解∈??(??)①首先隨機(jī)生成??個(gè)滿足分布??(0,1)的數(shù)??1,??2,…,????，構(gòu)成??維向量??=(??1,??2,…,????)。??′=????????VNS，Gauss-GVNS和Gauss-VNS-LS1。由于Gauss-VNS和Gauss-GVNS本質(zhì)上相差不大，因此本文主要關(guān)注算法Gauss-GVNS和Gauss-VNS-LS1。Gauss-VNSVNS2.1中描述的通用的局部搜索算法，局部搜索算法中使用的鄰域定義也和VNS算法相同。定義????-????(??)，????-????(??)={??′|交換??中任意兩個(gè)距離為??的元素}，??=1,…,???1。Gaussian-GVNS中使用的局部搜索算法如下所示①令??=1????′1；否則令????1。如果令????，那么結(jié)束搜索。否則，繼續(xù)執(zhí)行步驟2。Gaussian-GVNS中使用的局部搜索算法在所有的鄰居解都沒有當(dāng)前解好時(shí)，會(huì)繼續(xù)探索的鄰居解，直至完成預(yù)先定義的所有鄰域的探索；反之，則不會(huì)。這樣一來，Gauss-VNS-LS12.1中描述的通用的局部搜索算本章小義。對(duì)于本文關(guān)注的FTSP，其????????????????的含義為最后一個(gè)文件完成傳輸?shù)臅r(shí)間。FTSP方法的分類，主要分為精確方法和啟發(fā)式算法兩大FTSPM1M2；啟發(fā)式解FTSP的基于局部搜索的啟發(fā)式算法VNSGauss-VNS。本章將介紹本文求解文件傳輸調(diào)度問題（FileTransferSchedulingProblem，F(xiàn)TSP）FTSPM3M4FTSP的新的基于局部搜索的啟發(fā)式算法Modified-VNS。Dra?i?Zetal.FTSPM1M2[15-16]，但是模型M1的變量數(shù)有|??|?????????+1，而約束數(shù)為|??||??|????????+|??|?????????+|??|∑?????????2???(??+1)M2的變量數(shù)有2|??|??1，約束數(shù)為|??||??|??2 |??|????????。其中|??|為文件的數(shù)目，|??|為節(jié)點(diǎn)的數(shù)目，????????為問題FTSP的一個(gè)上界。M14050M2雖然可M1M2中引入了啟發(fā)式算法獲得的上界????????來減少模型的約束數(shù)和變量數(shù)，那接下來，本小節(jié)將詳細(xì)介紹本文求解FTSP的兩個(gè)新的整數(shù)規(guī)劃模型，記為模型M3和模型M4。本文第一個(gè)整數(shù)規(guī)劃模型M3是時(shí)間索引的整數(shù)規(guī)劃模型，M3的改進(jìn)版，通過利用基本下界進(jìn)一步地減少了約束數(shù)。FTSPM3。數(shù)規(guī)劃模型M3。??????=

1,如果文件??在時(shí)間索引??對(duì)應(yīng)的時(shí)間開始傳輸0,

包含排序和調(diào)度的問題可以很自然地使用由(??,??)索引的變量??????模型化為整數(shù)規(guī)劃其中，??表示需要被傳輸?shù)奈募乃饕????+表示時(shí)間段[??1??]的索引，例如對(duì)于時(shí)間索引1，表示時(shí)刻0到時(shí)刻1的時(shí)間段[0,1]?？紤]到文件的數(shù)目是有限的，顯然在有 ??????????????∑???????????(??)+1 =1,???∈

( ??????≤??(??),???∈??,1≤??≤??=max{1,?????????≥(??(??)+???1)??????,???∈??,1≤??≤ ??????∈{0,1},???∈??,1≤??≤ ??∈ 束（3.5）保證了所有文件????的完成傳輸?shù)淖畲髸r(shí)間小于等于??，該約束實(shí)際上也是變本文新模型M3中的變量數(shù)為|??|?????????+1，約束數(shù)為|??|+|??|?????????|??|?????????。和模型M1相比，模型M3的變量數(shù)保持不變，但是約束數(shù)降低了|??|∑?????????2???(??+1)。而和模型M2相比，模型M3的變量數(shù)減小了|??|? （1）上界????????3.1列表調(diào)度算法Tab. Listscheduling輸入：文件傳輸圖??=(????)初始化：將所有文件??∈??按照文件長(zhǎng)度??(??從大到小的順序排序，記為??????????????????????，并設(shè)置所有文件????的開始傳輸時(shí)間??(??1，所有節(jié)點(diǎn)????的可用端口數(shù)????????????????????????????????(??)=??(??)。??????????= /????????????????????????????????????????????????????????????????????????=????????=0;;??=??+??????????????==??????????????????????.????????=0;??<??????????????????????.????????();??=??+?????????????????????????/?????????????????????????????????????????????????????(????????)??′????????(??)==?1&&????????????????????????????????(????????????)>0&&????????????????????????????????(????????)>0??(??)=??????????+????????????????????????????????(????????????)?????????????????????????????????(????????)???????(??)+??(??)>??????????????????=??(??)+

輸出：所有文件的開始傳輸時(shí)間??(??)和??????????????????本文使用Coffmanetal.列表調(diào)度（ListScheduling，LS）算法[1]來生成模型M3中的參數(shù)????????FTSPFTSP的目將該文件的開始傳輸時(shí)間設(shè)置為??，并將兩個(gè)節(jié)點(diǎn)對(duì)應(yīng)的可用端口數(shù)減1。模型M3中使用的????????。M3M4M3M4。因此，在詳細(xì)介紹模型M4之前，本小節(jié)將首先介紹基本下界??????的定義。（1）基本下界Coffmanetal.FTSP的基本下界（ElementaryLowerBound，ELB）[1-2]。記為|????|。另外，令∑??∑??∈??????(??)表示節(jié)點(diǎn)??需要傳輸?shù)乃形募膫鬏敃r(shí)間之和，那件傳輸圖??=(??,??)的最優(yōu)解??????(??)一定滿足以下不等式：??????(??)≥?????????∑??/??(??)?. 公式（3.8）FTSP的基本下界??????=?????????∑??/??(??)?1.1節(jié)點(diǎn)??1關(guān)聯(lián)的邊的集合為????1={??1??3}，那么∑??1=??(??1)+??(??3)=3+2=4?∑??4/??(??4)?=?5/2?=3。那么圖1.1中的FTSP實(shí)例的基本下界????????????{5,3,4,3}=5更少的整數(shù)規(guī)劃模型M4。FTSPELB的情況下（ELB的計(jì)算非常簡(jiǎn)單，因此引入的計(jì)算基本下界的開銷基本可以忽略不計(jì)）M3中的約束（3.5）中的??無需1開始，因?yàn)楫?dāng)??????????(??)時(shí)，???∈??，不等式??≥(??(????1)??????一定成立。因此可以用以下不等式來取代模型M3中的約束（3.5）：??≥(??(??)+???1)??????,???∈??,?????????(??)+1≤??≤????????. ??????≤??≤ 模型M4如下所示: ??????????????∑???????????(??)+1 =1,???∈

( ??????≤

,???∈??,1≤??≤??=max{1,?????????≥(??(??)+???1)??????,???∈??,?????????(??)+1≤??≤????????;??????∈{0,1},???∈??,1≤??≤ ??????≤??≤????????,??∈ 模型M4的變量數(shù)和模型M3相同，均為|??|????????+1，而約束數(shù)則為|??||??|????????|??|(??????????????∑??∈????(??)ELB，和?！??????∑??∈????(??0）M4M3的表3.2中統(tǒng)計(jì)了現(xiàn)有的整數(shù)規(guī)劃模型M1M2和本文新的整數(shù)規(guī)劃模型M3，M1由于傳輸連續(xù)性約束的復(fù)雜表示方式具備大量的約束數(shù)，而模型M2雖然通過引入額外的變量大大降低了約束數(shù)，但是和模型M1相比，模型M2的變量數(shù)增|??|? 1) |??|????????2|??|????????M1M2很難而本文新模型M3通過不同的表示方式定義了文件傳輸連續(xù)性約束和端口約M3中的變量數(shù)為|??|????????+1，約束數(shù)為|??||??|????????+|??|????????M1相 M3的變量數(shù)減小了|??|?????????，同時(shí)約束數(shù)也降低了|??|?????????。在此基礎(chǔ)上，本文又在新模型M3中引入基本下界??????，獲得了另一個(gè)新模型M4?；鞠陆绲囊胧沟眯履Ｐ蚆4的約束數(shù)和新模型M3相比，又減少了很多。和模型M3相比，模型M4的變量數(shù)不變，但是約束數(shù)又降低了|??|????????∑??∈????(??)。3.2不同模型的變量數(shù)和約束數(shù)Tab. Thenumberofvariablesandconstraintsfordifferent模 變量 約束 |??|?????????+ |??|+|??|? +|??|? +|??|?∑?????????2 2?|??|?????????+|??|+|??|?????????+2?|??|?|??|?????????+|??|+|??|?????????+|??|?|??|?????????+|??|+|??|?????????+|??|?(???????????????)+∑??∈??模型M3和M4具有更小的規(guī)模，因此理論上在求解相同的實(shí)例時(shí)會(huì)花費(fèi)更少的新的啟發(fā)式算法Modified-現(xiàn)有的求FTSP的啟發(fā)式算法VNS，Gauss-GVNSGauss-VNS-LS1在計(jì)算解的方案的，情況下的時(shí)間復(fù)雜度為??(??????????)，其中??為實(shí)例中需要傳輸?shù)奈募?shù)目，????????為實(shí)例中的上界。當(dāng)實(shí)例的規(guī)模很大時(shí)，文件數(shù)??和????????也會(huì)很大，這會(huì)使得計(jì)算解FTSP的基于局部搜索的啟發(fā)式算法Modified-VNS。接下來，本小節(jié)將詳細(xì)介紹新算法本文使用??維向量??=[??1,??2,…,????]FTSP的解，其中??表示需要傳輸?shù)奈募臄?shù)目，????表示第??個(gè)被調(diào)度的文件的索引。例如對(duì)于圖3.1表示的實(shí)例，向量??=[2,4,5,1,3]表示按照[??2,??4,??5,??1,??3]的順序來調(diào)度文件。3.1解??Fig. Anexampleoftransformingsolutionrepresentation??toa0，表示端口下一個(gè)可用的時(shí)刻??按照向量??表示的順序確定每個(gè)文件的開始時(shí)間。例如對(duì)文件??????，彈出文??????關(guān)聯(lián)的兩個(gè)節(jié)點(diǎn)????????????和????????對(duì)應(yīng)的堆頂元素，記為??1和??2。顯然，??1和??2分別表示節(jié)點(diǎn)????????????和????????最近的可以開始傳輸新的文件的時(shí)間。取??1和??2的最大值，記為???????? 即????????=max??1??2}。令????????為文件????的開始時(shí)間，即??(????)=??，并將??+??(????)分別放 那么，解??對(duì)應(yīng)的調(diào)度方案的目標(biāo)函數(shù)值??(????????1≤??≤??(??(??????(????))，即所有文3.3根據(jù)解??Tab. Buildschedulingaccordingtosolution輸入：文件傳輸圖和??維向量表示的解??=[??1??2????]初始化：對(duì)每一個(gè)節(jié)點(diǎn)????，構(gòu)建大小為??(??)的最小堆????，堆????中的元素為每一個(gè)端口下一個(gè)可用的時(shí)刻??，初始時(shí)均為0。??????????????????=????????=0;??<??;??=??+/?????????????????????????????????????????????????????(????????)??????′????1=??????????????. ??????????????.??2=??????????. ??????????.????????=max(??1,??2)??(??????)=/?????????????????????????????????????????????????????????????????=????????+??????????????.??????????./???????????????????????????????????????????>??????????????????=輸出：所有文件的開始傳輸時(shí)間??(??)和??????????????????3.13.3中描述的方法，解??對(duì)應(yīng)的調(diào)度方案為：文件??1，??40開始傳輸，文件??5從時(shí)刻1開始傳輸，而文件??2和??3從時(shí)刻2開始傳輸。該調(diào)度方案的目標(biāo)函數(shù)值——為利用列表調(diào)度算法構(gòu)建解??對(duì)應(yīng)的調(diào)度方案時(shí)，在每一個(gè)時(shí)刻都需要掃描整個(gè)文件3.3中描述的算法利用最小堆數(shù)的FTSP的求解，這也是新的解的表示方式另一個(gè)優(yōu)勢(shì)所在。在本文新算法Modified-VNS中，變鄰域搜索時(shí)使用的鄰域集合為{????(??|????????≤??≤????????}，????????和????????均為預(yù)先設(shè)置的參數(shù)。其中，鄰域????(??)=和??最多有??個(gè)位置不同}3.4生成解??的鄰居解??′∈Tab. Generateneighborsolution??′∈????(??)ofsolution輸入：??維向量表示的解??=[??1??2????]，參數(shù)?????????????????????????????????????????????????????[1,??]????????????????,????????????????????????????????????????????[1,2,…,??]????????????????,[??????????1,??????????2,…,??′=????????=1;??≤??;??=??+??′[????????????????????]=??[????????????????????????????輸出：鄰居解??′對(duì)于解??，生成鄰居解??????(??)3.4,,…,其中1≤????????????????????≤??，??為需要傳輸?shù)奈募臄?shù)目。（2）[1,2??]的一個(gè)置換，記為[??????????1??????????2????????????]，其中1≤????????????≤??。（3）最后，令??′=??，并且令??′[????????????????????]=??[??????????????????????????????](??)??令??=[1,2,3,4,5]，那么??′=[2,1,3,4,5]既是??的??2(??)鄰居解，又是??的??3(??)鄰居解。顯然，??3(??)中鄰居解的數(shù)目。在外層搜索中，如果在鄰域????(??)中不能找到比當(dāng)前找到更好鄰居解的可能性也越高，只是花費(fèi)的時(shí)間也會(huì)。Modified-VNS3.5所示，主要 范圍為[????????,????????]，顯然，????????和????????的取值會(huì)影響算法每次迭代時(shí)探索的鄰域，進(jìn)而????????=35移動(dòng)規(guī)則。新算法Modified-VNS中的移動(dòng)規(guī)則是，如果局部搜索子程序獲得的鄰居解??′比當(dāng)前的解??要好（即??(??′??(??)），那么將進(jìn)行??向解??′的移動(dòng)，即將??′作為當(dāng)前解進(jìn)行下一輪搜索。但是，由于FTSP本身的特性，多個(gè)解對(duì)應(yīng)具有相同目標(biāo)函數(shù)值的調(diào)度方案的情況會(huì)非常常見。也就是說，在探索當(dāng)前解??的鄰域時(shí)，很可能會(huì)獲得和解??具有相同目標(biāo)函數(shù)值的鄰居解??′3.13.2可知，解??=[1,2,3,4,5]和解??′=[1,5,4,3,2]對(duì)應(yīng)的調(diào)度方案并不多樣性，因此本文在算法Modified-VNS中設(shè)置了參數(shù)??來控制這種特殊情況下是否進(jìn)行移動(dòng)。 部搜索子程序獲得的鄰居解??′的目標(biāo)函數(shù)值??(??′)=??(??)時(shí)??向解??′移動(dòng)的概率為??。在進(jìn)行對(duì)比實(shí)驗(yàn)時(shí)，本文設(shè)置參數(shù)??=0.4停止標(biāo)準(zhǔn)。本文算法Modified-VNS中將最大迭代次數(shù)作為算法停止質(zhì)量越好，直至收斂。在進(jìn)行對(duì)比實(shí)驗(yàn)時(shí)，本文將最大迭代次數(shù)設(shè)置為100。Modified-VNS和其它的變鄰域搜索算法另一個(gè)不同之處。例如，當(dāng)??=????????，局部搜索子程序中使用的鄰居定義也為??????????(??)。另數(shù)????=50。3.5算法Modified-Tab. ????????????????????=0;??????????????<????????????????????????;??????????????=??????????????+????????=????????;??≤????????;??=??+/??????????????????????????????′=??,??(??′)=????????????????=0;??????????≤????;??????????=??????????+???????????????????????????????????????????????????????????????????′′∈??????(??′′)<??′=??′′????????(??′)=/?????????????????????????(??′)<??=??′,??(??)=??(??′)????????????????????(??′)=??=??′,??(??)=??(??′)?????????????????????????????????????????????本文新算法Modified-VNS和其它的基于局部搜索的啟發(fā)式算法的不同之處Modified-VNS中設(shè)計(jì)了更簡(jiǎn)單的解的表示方式以及將解轉(zhuǎn)Modified-VNS中，局部搜索子程序使用了具有更大變化的鄰域定義，即和外層搜索時(shí)使用的鄰域定義????(??)保持一致——3.2解??′Fig. Anexampleoftransformingsolutionrepresentation??′toa本章小本章節(jié)首先介紹了本文兩個(gè)新的時(shí)間索引的整數(shù)規(guī)劃模型M3和M4，然后介紹了本文新的求解FTSP的基于局部搜索的啟發(fā)式算法Modified-VNS。和現(xiàn)有的整數(shù)規(guī)劃模型M1和M2相比，本文新模型M3使用不同的表示方數(shù)。在此基礎(chǔ)上，本文又在新模型M3中引入基本下界??????，獲得了另一個(gè)新模型M4?；鞠陆绲囊胧沟煤托履Ｐ蚆3相比，新模M4的約束數(shù)又減少了很多。顯然，本文模型M3和M4具有更小的規(guī)?！俚募s束數(shù)和變量數(shù)，因此理論上在求本文的兩個(gè)新模型M3和M4的優(yōu)越性。和現(xiàn)有的啟發(fā)式算法相比，本文新算法Modified-VNS中定義了不同的解的Modified-VNS在計(jì)算解的目FTSP問題本身的特性，鄰居解變化太小的話很容易導(dǎo)致解對(duì)應(yīng)的調(diào)度方案，甚至是目Modified-VNS中局部搜索子程序使用的是鄰居Modified-VNS和現(xiàn)有的啟發(fā)式算法的對(duì)比實(shí)驗(yàn)，從而驗(yàn)證新算法Modified-VNS的優(yōu)越性。實(shí)驗(yàn)結(jié)果與分實(shí)驗(yàn)環(huán)境和實(shí)例本文是在配置Windows10系統(tǒng)的筆記本電腦上進(jìn)行的數(shù)值實(shí)驗(yàn)，其中CPU型號(hào)為Ini5-8250U，主存容量大小為8GB。實(shí)現(xiàn)算法時(shí)使用的編程語言均為C++，IDE為最大的求解時(shí)間為600秒。本文中使用的實(shí)例是隨機(jī)生成的，表4.1展示了隨機(jī)生成的實(shí)例的節(jié)點(diǎn)數(shù)和邊數(shù)。生成邊的長(zhǎng)度時(shí)保證每一條邊的長(zhǎng)度均勻分布在[1????????]上。參數(shù)????????指的是節(jié)點(diǎn)的最數(shù)時(shí)保證每一個(gè)節(jié)點(diǎn)的端口數(shù)均勻分布在[1????????]上。另外，本文在進(jìn)行實(shí)驗(yàn)時(shí)會(huì)保證4.1實(shí)例的規(guī)模大小Tab. Instance554.1Tab. 整數(shù)規(guī)劃模型的實(shí)驗(yàn)結(jié)詳細(xì)的實(shí)驗(yàn)結(jié)果分別展示在表4.2，表4.34.4中。表4.24.4中的“ntan”列記錄了實(shí)例的名字，其中包含四個(gè)數(shù)一個(gè)數(shù)字表示文件傳輸圖點(diǎn)的數(shù)目|??|，第二個(gè)數(shù)字表示文件傳輸圖中邊的數(shù)目|??|，第三個(gè)數(shù)字和第四個(gè)數(shù)字分別表示生成文件傳輸圖時(shí)設(shè)置的節(jié)點(diǎn)的最大端口數(shù)??????和文件的最大長(zhǎng)度??????ftp_5_40_10_20540條邊的文件傳輸(0,20]的均勻分布行數(shù)值實(shí)驗(yàn)時(shí)，每一個(gè)相同的實(shí)例名（具有相同的參數(shù)）都生成10個(gè)不同的實(shí)例，秒內(nèi)無法求解這10個(gè)實(shí)例中的任何一個(gè)（超時(shí)或者內(nèi)存不足）。另外，本文在計(jì)算多無法求解的實(shí)例則不包含在內(nèi)。例如對(duì)于表4.3中展示的中規(guī)模實(shí)例理時(shí)間內(nèi)（600s）M3的“#Opt7，“t(s)”列對(duì)7個(gè)，并且這7個(gè)實(shí)例的平均求解時(shí)間為177.2秒。表 Tab. Comparisonofdifferentmodelsonsmall-scale 0-0-40-0-0-20-90-820-0-0-54.1-是根據(jù)4.2繪制的，統(tǒng)計(jì)了模M1，M2，M3M4求4.14.2解的中規(guī)模實(shí)例的數(shù)目，圖4.4展示了各個(gè)模型求解所有中規(guī)模實(shí)例的平均求解時(shí)間；M1，M2，M3M4求解大規(guī)模實(shí)例的4.54.6展示了各個(gè)模型求Small-scaleSolved2Unsolved00theSmall-scaleSolved2Unsolved00thenameofthenumberof

Small-scale50 theSmall-scale50 thenameofaveragesolving4.1可以得于規(guī)模比較小的（50個(gè)節(jié)點(diǎn)，100個(gè)文件），M116032M2，M3根據(jù)圖4.2可知，本文新模型M3和M4花費(fèi)的時(shí)間更少，尤其是M4。具體而M2相比，模M3平均花費(fèi)的時(shí)M23.6%，而模型M4更是只花費(fèi)了模型M2所需時(shí)間的0.4%。根據(jù)4.34.5可以得M1無法求解任何中規(guī)模和大規(guī)模實(shí)M2可以求解的中規(guī)模和大規(guī)模實(shí)例的數(shù)目也遠(yuǎn)小于本文模型M3和M4，尤其是模M4。例如，160M254個(gè)，280M2只能求解129個(gè)，均不50%160個(gè)中規(guī)模實(shí)M3109個(gè)，280個(gè)大規(guī)模實(shí)M3可以求解202個(gè)，求解比例分別約為68%和70%，顯然模型M3能求解的中規(guī)模和大規(guī)M24.44.6M3求解中規(guī)模和大規(guī)模實(shí)例時(shí)所需的求解時(shí)間也要小于模型M2，僅需要模型M2求解時(shí)間的54.4%和75.0%實(shí)例（高100個(gè)節(jié)點(diǎn)，600條邊）4.44.6可知，和模M2相比，求解中規(guī)模實(shí)例時(shí)，模型M4平均僅花費(fèi)了模型M2求解時(shí)間的4.0%左右；求解大規(guī)模實(shí)例時(shí)，模型M4平均僅花費(fèi)了模型M2時(shí)求解時(shí)間的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均能在合理時(shí)間（600s）求解的實(shí)例數(shù)并且花費(fèi)更少的時(shí)間。其M1僅能求解總實(shí)例數(shù)目（600個(gè)）5.3%M2僅能求解總實(shí)例數(shù)目（600個(gè)）的56.8%，而本文模型M3和M4則能求解的實(shí)例，具體而言，模型M3可以（600個(gè)78.5%，模M4表現(xiàn)更99.7%的實(shí)例。在求解時(shí)間方面，和現(xiàn)有的求解最快的M2相比M3平均需要模型M272.2%M4M214.3%。要優(yōu)于現(xiàn)有的整數(shù)規(guī)劃模型M1和M2。Medium-scaleSolved Unsolved00Medium-scaleSolved Unsolved00thenameofMedium-scale500 thenameofthenumberofaveragesolving

圖4.4求解中規(guī)模實(shí)例的平均求解時(shí)間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求解大規(guī)模實(shí)例的實(shí)驗(yàn)結(jié)果Fig.4.5 Resultofsolvinglarge-scale

Large-scaleUnsolved Solved20theLarge-scaleUnsolved Solved20thenameofLarge-scale500 thenameofthenumberofaveragesolving本文也比較了本文新模型M3，M4和現(xiàn)有模型M1，M2規(guī)模的大小，即約M14.5中展示看出，和模型M1相比，模型M2的約束數(shù)大大減少，但是變量數(shù)卻增多。而本文提出的兩個(gè)模型M3和M4，和模型M1相比，變量數(shù)不變，而約束數(shù)大大減少；和模型M2相比，變量數(shù)和約束數(shù)都減少了。其中，和模M1相比，模M3的約束數(shù)平均減少了96.37%M497.47%M2M3的變量數(shù)平均減少了約49.79%，約束數(shù)平均減少了約37.29%；模型M4的變量數(shù)平均減少了約49.79%，約束數(shù)平均減少了約56.23%。4.5Tab. Comparisonofthenumberofvariablesandconstraintsofdifferent thenameoftheaveragenumberofFig.4.7 TheaveragenumberofvariablesforallinstancesinTab.4.5

thenameoftheaveragenumberofthenameoftheaveragenumberof啟發(fā)式算法的實(shí)驗(yàn)結(jié)VNS，Gauss-GVNSGauss-VNS-LS1的的啟發(fā)式算法VNS，Gauss-GVNS，Gauss-VNS-LS1和本文新算法Modified-VNS本文首先將本文新算法Modified-VNS和現(xiàn)有的啟發(fā)式算法VNS，Gauss-GVNS，Gauss-VNS-LS1進(jìn)行了對(duì)比實(shí)驗(yàn)，詳細(xì)的實(shí)驗(yàn)數(shù)據(jù)在表4.64.6中件傳輸圖點(diǎn)的數(shù)目|??|，邊（文件）的數(shù)目|??|，生成節(jié)點(diǎn)的端口數(shù)時(shí)最大的端口數(shù)表4.6中“t(s)”列記錄了各啟發(fā)式算法的求解時(shí)間，單位為秒（second）本文已經(jīng)提出了更好的整數(shù)規(guī)劃模型M4，它可以在合理的時(shí)間內(nèi)求出大規(guī)模實(shí)例數(shù)值之間的差距，其詳細(xì)的定義如下所示。記啟發(fā)式算法獲得的解為??，模型M4求得??(??)??????????????????????=

Modified-VNS中有一些需要預(yù)先設(shè)置的參數(shù)，本次實(shí)驗(yàn)中參數(shù)設(shè)置如下所示。其中，????????=15，????????=35100次，局部搜索子程序中使用的參數(shù)????=50。數(shù)據(jù)，如表4.6所示。均可以獲得最優(yōu)解（即Gap為0），例如實(shí)例“ftsp_300_600_150_300”。而對(duì)于另外一4.94.10則展示了各啟4.6Tab.

Modified-00000000000000000000000000000000000000000000000000000004.6Tab.

Modified-000000000000000000000000Modified-Fig. Comparisonofsolutionofheuristic根據(jù)圖4.9可知，在大多數(shù)情況下，本文啟發(fā)式算法Modified-VNS獲得的解的質(zhì)量都比現(xiàn)有的啟發(fā)式算法VNS，Gauss-GVNSGauss-VNS-LS1要好，尤其當(dāng)實(shí)例Modified-VNS在求解大規(guī)模實(shí)例時(shí)獲得的解與最優(yōu)解之間的差距也很小，均小于0.01。更重要的是，根據(jù)圖4.10可以看出，本文啟發(fā)式算法Modified-VNS的求解時(shí)間也遠(yuǎn)遠(yuǎn)小于這些現(xiàn)有的啟發(fā)和算法VNS相比Modified-VNS平均僅需其約6.2%的求解時(shí)間；和算法Gauss-GVNS相比，新算法Modified-VNS5.6%Gauss-VNS-LS1相比，本文新算法Modified-VNS平均也只需要其約14.4%的求解時(shí)間。0Modified-0Modified-Fig. Comparisonofsolvingtimeofheuristic本文還進(jìn)行了新算法Modified-VNS和本文整數(shù)規(guī)劃模型M4之間的對(duì)比實(shí)劃模型M4獲得的最優(yōu)解的????????????????的差值。M4FTSP實(shí)例的最優(yōu)解。當(dāng)實(shí)例規(guī)模比較M4FTSP實(shí)例的最優(yōu)解。例如對(duì)于實(shí)例比算法Modified-VNS花費(fèi)的時(shí)間還要更少。但是當(dāng)實(shí)例規(guī)模逐漸增大時(shí)，求解時(shí)間也甚至不能在合理的時(shí)間內(nèi)（600s）求出最優(yōu)解。而啟發(fā)式算法Modified-VNS雖然不能保證獲得的解的質(zhì)量，但是對(duì)于大規(guī)模的實(shí)例（100個(gè)節(jié)點(diǎn)，1000條邊），仍然可以在Tab. ComparisonofModelM4andModified-VNSonlarge-scale Model ------24.11展示了模型M4Modified-VNS獲得的解的目標(biāo)函數(shù)值????????????????的對(duì)比，而圖4.12展示了模型M4Modified-VNS求解時(shí)間的對(duì)比。4.11Modified-VNS獲得的解雖然不一定是最優(yōu)解，解時(shí)間增長(zhǎng)很快，而算法Modified-VNS的求解時(shí)間增長(zhǎng)很平緩，幾乎在十秒以內(nèi)就可顯然，本文算法Modified-VNS和模型M4求解結(jié)果之間的對(duì)比進(jìn)一步展現(xiàn)Modified-VNSM4是時(shí)間索引FTSPModified-VNS，應(yīng)用于文件長(zhǎng)度不為整數(shù)的FTSPModified-VNS的另一優(yōu)勢(shì)所在。900800700Model900800700Model6005004003002001000300250Model200150100500Fig.4.11 ComparisonofsolutionofModelM4andModified-VNS

4.12ModelM4Modified-VNSFig.4.12 ComparisonofsolvingtimeofModelM4andModified-VNS本章小,所有文件的長(zhǎng)度都均勻分布在[0????????]上。之后，本章展示了本文新模型M3和M4與現(xiàn)有的模型M1和M2之間的對(duì)M3M4M1M2多，并且求解時(shí)間也更少。具體來說，對(duì)于所有實(shí)例（共600個(gè)），模型M1僅能求解其中約5.3%的實(shí)例模型M2僅能求解其中約56.8%的實(shí)例而本文新模型M3和M4則能求解的實(shí)例，模型M3可以求解其中約78.5%的實(shí)例，模型M4表現(xiàn)更好，可99.7%M2M3平均需要其求解時(shí)間的72.2%左右，而模型M4平均僅需其求解時(shí)間的14.3%左右。最后，本章也展示了本文新的啟發(fā)式算法Modified-VNS和現(xiàn)有的啟發(fā)式算Modified-VNS不僅獲得的解的質(zhì)量要優(yōu)于解速度最快的啟發(fā)式Gauss-VNS-LS1相比，新Modified-VNS平均也只需要其約14.4%的求解時(shí)間。顯然，大量的實(shí)驗(yàn)結(jié)果驗(yàn)證了本文新模型M3和M4，尤其是模型M4，以及新的啟發(fā)式算法Modified-VNS的優(yōu)越性。 FTSP，即給定節(jié)點(diǎn)和需要在34，其中，模型4是在模型3的基礎(chǔ)上引入基本下界獲得的。通過不同的決策變量和約束的定義方式，和現(xiàn)有的整數(shù)規(guī)劃模型相比，本文兩個(gè)新模型3和4具有更一點(diǎn)。和現(xiàn)有的性能最好的模型2相比，新模型3和4可以求解的實(shí)例的規(guī)模更大，花費(fèi)的求解時(shí)間也更少，尤其是模型4。具體而言，求解小規(guī)模實(shí)例時(shí)，模型4平均只花費(fèi)了現(xiàn)有的最好的模型2所需時(shí)間的0.4%左右；求解中規(guī)模實(shí)例時(shí)，模型4平均僅花費(fèi)了模型2求解時(shí)間的4.1%左右；求解大規(guī)模實(shí)例時(shí)，模型4平均僅21.%4214.3%左右。M3M4FTSP，并且隨著問題Modified-VNSModified-VNS和現(xiàn)有的基于局部搜索的啟發(fā)式算法的對(duì)比實(shí)驗(yàn)，驗(yàn)證了新算法Modified-VNS的優(yōu)越性。具體而言，本文新算法Modified-VNS不僅能夠獲得更高質(zhì)量的解（和最優(yōu)解之間的gap小于0.01），并且即使和現(xiàn)有的求解速度最快的啟發(fā)式算法相比，也只需要其約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