排序博弈及相關(guān)排序問題研究.pdf

1、浙江大學(xué)博士學(xué)位論文排序博弈及相關(guān)排序問題研究姓名：萬龍申請(qǐng)學(xué)位級(jí)別：博士專業(yè)：運(yùn)籌學(xué)與控制論指導(dǎo)教師：談之奕201204AbstractSchedulingproblemisoneoftheclaSsiealcombinatorialoptimizationproblems。Inthetraditi。nalschedulingmodels)jobsonlyarenegativelyassignedtomachinesandexclud

2、edfromdecision—makers，Inrecent”ars，manyresearcbersconsiderjobsaSsel士ishagentstochoosemachinesarbi七rarilyandintroducegame屯heoreticalldeastoanalyzeschedulingproblemThethesis，whichmainlydealswithschedulinggamesandrelatedsch

3、edulingproblems，consistsof矗vechaDters1IlChapter1)wepresentrelatedbasicconcepts，preliminaryknowledge、themainresultsofthethesisandsomeusen】】no七atjonsChapter2mainlyinVestigatesthemachinecoveringgameontwouniformmachineswithm

4、akespanpolicyⅥregivethetightparametricboundsofPOSandt5rPOSabouttheratiobetweenthespeedsoftwomachinesInChapter3，westudysomeschedulinggameswithparallelprocessingpolicyFirstly，f6rparallel—maehineenvironmentⅥ傖giveaeharacteri

5、zationoflistschedulebasedonwhichweshowtherelationshipbetweennashequilibriumandlistscheduleSecondly，wegiVesomeanalysisfortheiIle母ciencyofna_ShequilibriumFbrm】den缸c烈machlnes，wegettheexactPOSfortheschedulinggamewithsocialco

6、stasthemaⅪmumloadoVerthemachines，andtheexactPOA，POSforthemaellinecoVerlnggamePbrtworelatedmachines，weshow七h(yuǎn)etightparametricboundsofPOAabouttheratiobetweenthespeedsoftwonlachinesfortheschedulinggamewlthsoclalcostalsthemaX

7、imumloadoverthemachinesandthemachinecoveringgame，respectivelyU上1apter4presentsameasureaboutschedulescalledequilibriumratioproblemandshowsfullanalysisf6rthreemachinetypesandthreeprocessmodeswegivethetightboundsofstrongequ

8、ilibriumratioforallschedulingmodels，andthetightboundofweakequilibriumratiowhenweconsidertheschedulingmodelwithldelltlcalmachlnesandthepreenlptiVeprocessmodeorunif6rmmachinesandthe上ractlona上processmodewealsoshowthatthelow