資源描述：
《并行分布計算中的調(diào)度問題研究》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、中國科學(xué)技術(shù)大學(xué)博士學(xué)位論文并行分布計算中的調(diào)度問題研究姓名：孫廣中申請學(xué)位級別：博士專業(yè)：計算機軟件與理論指導(dǎo)教師：陳國良;顧鈞20050301中國科學(xué)技術(shù)大學(xué)博士學(xué)位論文(4)類似于sETI@home的大規(guī)模P2P計算系統(tǒng)中的調(diào)度策略研究：提出了相應(yīng)的理論模型來描述其中的任務(wù)調(diào)度問題。在此基礎(chǔ)上，評估現(xiàn)有的幾種不同的調(diào)度策略，設(shè)計了新的根據(jù)具體的網(wǎng)絡(luò)環(huán)境和計算資源進(jìn)行選擇的調(diào)度策略，通過理論分析和實驗分析說明該策略較之現(xiàn)有策略有更好的性能，并將該調(diào)度策略應(yīng)用于實際系統(tǒng)中。本文的主要貢獻(xiàn)和創(chuàng)新有：(1)提出了具有中斷時間代價的～致
2、并行機調(diào)度問題，給出了近似比為常數(shù)的近似算法，證明了問題求解難度和近似難度；(2)研究了多臺機器條件下具有不可用時段的調(diào)度問題，分析了經(jīng)典在線算法的性能并證明了問題的近似難度；(3)針對線性網(wǎng)絡(luò)和環(huán)狀網(wǎng)絡(luò)，研究了分布式計算環(huán)境下的任務(wù)調(diào)度模型，證明了問題的難解性，給出了近似性能良好的調(diào)度算法；(4)研究了對等計算環(huán)境下任務(wù)調(diào)度問題，給出了相應(yīng)的調(diào)度模型，針對已有策略的不足設(shè)計了新的策略。關(guān)鍵詞：調(diào)度問題，并行計算，分布式計算，近似算法，F(xiàn)界中國科學(xué)技術(shù)大學(xué)博上學(xué)位論文AbstractSchedulingproblemsareonek
3、indofbasicproblemsincombinationoptimization．Theyarec。ncernedwiththeoptimala110cationofscarceresourcestoactivitiesovertime．Moregenerally，schedulingproblemsinv01vejobsthatf【
4、ustbescheduledonmachinessubjecttocertainconstraintstooptimizesomeobjectivefunction．Fordifferenceo
5、fmachineenvironrnent，sideconstraintsandcharacteristics，optimalityobjects，schedulingproblemscontainthousandsofdifferentschedulingmodels．Manyresearchersindifferentfields，suchasappliedmathernatics，computerscience，managescience：haveachieVedlotsofimportantresultsonschedulin
6、gproblemsinboththeoryandapplication．Inparallelanddistributedcomputing，thereareamassofschedulingproblems．SolVingtheseschedulingproblemshasastrongimpactontheparallelanddistributedcomputingsystems．Toimprovetheperformanceoftheparallelanddistributedsystemseffectively，resear
7、chonthealgorithmsofthoseschedulingproblemsarevaluableintheoryandpractice．Inthispaper，someschedulingproblemsinparallelanddistributedcomputingarestudiedasf0110ws．(1)Apreemptiveschedulingproblemispresented，inwhichanadditionaltimecostisneededifajobisinterruptedonce．Thispap
8、ersh。wsthatproblemisaNP—hardproblem，presentsanoff—lineapproximationalgorithmwithtimecomplexityofO(nlogn+m)andaperformancerationomorethan1．40825．Theon一1inepropertyisalsostudiedandanon一1inealgorithmwithlinearitytimecomplexitYandacompetitiveratioof2isproposed．(2)Weconside
9、rstheon—lineschedulingonidenticalmachineswithmachlneavailabilityconstraintsandanalyzeoftheperformanceoftheLSalgorithm
