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-Thispap

2、erreconsidersonlinepacketschedulingincomputeringthisproblemwastodemonstratethatexploitingstochas-networks,wherethegoalistominimizeweightedpacketlossticinformationmayprovidesigni®cantbene®tsinonlineandwherethearrivaldistributionsofpackets,orapproxi-pa

3、cketscheduling.Theyproposedanexpectationapproachmationsthereof,areavailableforsampling.Earlierworkproposedanexpectationapproach,whichchoosesthenextwhichchoosesthenextpackettoschedulebyapproximatingpackettoschedulebyapproximatingtheexpectedlossoftheex

4、pectedlossofeachpacketclassoverthedistribution.eachdecisionoverasetofscenarios.Theexpectationap-Theapproximationsamplesthedistributionstobuildscenar-proachwasshowntosignificantlyoutperformtraditionalap-iosfromavailableandfuturepackets.Theexpectational

5、go-proachesignoringstochasticinformation.rithmwasshowntosigni®cantlyoutperformtraditionalap-Thispaperproposesanovelstochasticapproachforonlineproacheswhichignorestochasticinformationsuchasgreedypacketscheduling,whosekeyideaistoselectthenextpacketheur

6、isticsandalgorithmsoptimizingthedecisionsbasedonastheonewhichisscheduledfirstmostoftenintheoptimalknownpackets.However,theexpectationalgorithmmaybesolutionsofthescenarios.Thisconsensusapproachisshownquitedemandingcomputationally,sinceitsolveseachsce-t

7、ooutperformtheexpectationapproachsignificantlywhen-narioforeachclassofpackets.Asaconsequence,itmayevertimeconstraintsandtheproblemfeatureslimitthenum-notscalewellwhenthenumberofclassesincreasesanditberofscenariosthatcanbesolvedbeforemakingadecision.ma

8、ynotbeapplicablewhendecisionsmustbetakenwithinMoreimportantlyperhaps,thepapershowsthattheconsen-susandexpectationapproachescanbeintegratedtocombinestrongtimeconstraints.thebenefitsofbothapproaches.Thispaperreconsidersonlinepacketschedulingandpro-These