The Value of Consensus in Online Stochastic Scheduling

《The Value of Consensus in Online Stochastic Scheduling》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、TheValueofConsensusinOnlineStochasticSchedulingRussellBentandPascalVanHentenryckBrownUniversityProvidence,RI02912frbent,pvhg@cs.brown.eduAbstractpracticalissuesarisinginonlineoptimization.Indeed,themainpurposeof(Chang,Givan,&Chong2000)instudy-Thispaperreconsidersonlinepacketschedulingincom

2、puteringthisproblemwastodemonstratethatexploitingstochas-networks,wherethegoalistominimizeweightedpacketlossticinformationmayprovidesigni®cantbene®tsinonlineandwherethearrivaldistributionsofpackets,orapproxi-packetscheduling.Theyproposedanexpectationapproachmationsthereof,areavailableforsa

3、mpling.Earlierworkproposedanexpectationapproach,whichchoosesthenextwhichchoosesthenextpackettoschedulebyapproximatingpackettoschedulebyapproximatingtheexpectedlossoftheexpectedlossofeachpacketclassoverthedistribution.eachdecisionoverasetofscenarios.Theexpectationap-Theapproximationsamplest

4、hedistributionstobuildscenar-proachwasshowntosignificantlyoutperformtraditionalap-iosfromavailableandfuturepackets.Theexpectationalgo-proachesignoringstochasticinformation.rithmwasshowntosigni®cantlyoutperformtraditionalap-Thispaperproposesanovelstochasticapproachforonlineproacheswhichignor

5、estochasticinformationsuchasgreedypacketscheduling,whosekeyideaistoselectthenextpacketheuristicsandalgorithmsoptimizingthedecisionsbasedonastheonewhichisscheduledfirstmostoftenintheoptimalknownpackets.However,theexpectationalgorithmmaybesolutionsofthescenarios.Thisconsensusapproachisshownqu

6、itedemandingcomputationally,sinceitsolveseachsce-tooutperformtheexpectationapproachsignificantlywhen-narioforeachclassofpackets.Asaconsequence,itmayevertimeconstraintsandtheproblemfeatureslimitthenum-notscalewellwhenthenumberofclassesincreasesanditberofscenariosthatcanbesolvedbeforemakingad

7、ecision.maynotbeapplicablewhendecisionsmustbetakenwithinMoreimportantlyperhaps,thepapershowsthattheconsen-susandexpectationapproachescanbeintegratedtocombinestrongtimeconstraints.thebenefitsofbothapproaches.Thispaperreconsidersonlinepacketschedulingandpro-These