T. Models and algorithms for stochastic online scheduling

Scheduling󰀁

NicoleMegow1,MarcUetz2andTjarkVredeveld2

TechnischeUniversit¨atBerlin,Institutf¨urMathematikStrassedes17.Juni136,10623Berlin,Germany

nmegow@math.tu-berlin.de

MaastrichtUniversity,DepartmentofQuantitativeEconomicsP.O.Box616,6200MDMaastricht,TheNetherlands

{m.uetz,t.vredeveld}@ke.unimaas.nl

1

2

Abstract.Weintroduceamodelfornon-preemptiveschedulingunderuncertainty.Inthismodel,wecombinethemaincharacteristicsofonlineandstochasticschedulinginasimpleandnaturalway.Jobprocessingtimesareassumedtobestochastic,butincontrasttotraditionalstochas-ticschedulingmodels,weassumethatjobsarriveonline,andthereisnoknowledgeaboutthejobsthatwillarriveinthefuture.Theparticularsettingweanalyzeisparallelmachinescheduling,withtheobjectivetominimizethetotalweightedcompletiontimesofjobs.Weproposesim-ple,combinatorialonlineschedulingpoliciesforthatmodel,andderiveperformanceguaranteesthatmatchthecurrentlybestknownperfor-manceguaranteesforstochasticandonlineparallelmachinescheduling.ForprocessingtimesthatfollowNBUEdistributions,weimproveuponpreviouslybestknownperformanceboundsfromstochasticscheduling,eventhoughweconsideramoregeneralsetting.

Keywords.Stochasticscheduling,onlineoptimization,averagecomple-tiontime,policies.

1Introduction&Model

Weconsidertheclassicalproblemofnonpreemptiveschedulingonsingleandidenticalparallelmachinestominimizethesumofweightedcompletiontimesunderuncertainty.

Inordertocopewithuncertaintyaboutthefuture,therearetwomajorframe-worksinthetheoryofmachinescheduling,oneisthestochasticschedulingmodel,theotheronlineschedulingmodel(s).Themaincharacteristicofstochas-ticscheduling,incontrasttodeterministicmodels,isthefactthattheprocessingtimesofjobsaresubjecttorandomfluctuations,andtheactualprocessingtimes

󰀁

ResearchpartiallysupportedbytheDFGResearchCenterMatheon”Mathe-maticsforkeytechnologies”.Afullversionofthisabstractcanbefoundathttp://www.math.tu-berlin.de/˜nmegow/muv05sos.pdf.

Dagstuhl Seminar Proceedings 05031

Algorithms for Optimization with Incomplete Informationhttp://drops.dagstuhl.de/opus/volltexte/2005/110

2N.Megow,M.Uetz,T.Vredeveld

becomeknownonlyuponcompletionofthejobs.Itisgenerallyassumed,though,thattherespectiverandomvariables,oratleasttheirfirstmoments,areknownbeforehand.Inonlinescheduling,theassumptionisthattheinstanceispre-sentedtothescheduleronlypiecewise.Dependingontheprecisemodel,jobsarearrivingeitherone-by-one(sequencemodel),orovertime(time-stampmodel).Thejobcharacteristicssuchasweightandprocessingtimeareusuallydiscloseduponarrivalofthejob,anddecisionsmustbemadewithoutanyknowledgeofthejobstocome.

Inthispaper,wesuggestamodelthatgeneralizesboth,thestochasticschedulingmodelaswellastheonlineschedulingmodels.WecallittheStochasticOnlineScheduling(Sos)model.Likeinonlinescheduling,weassumethattheinstanceispresentedtotheschedulerpiecewise,andnothingisknownaboutjobsthatmightarriveinthefuture.Onceajobarrives,likeinstochasticscheduling,weassumethatitsweightandfirstmomentofitsprocessingtimearedisclosed,buttheactualprocessingtimeremainsunknownuntilthejobcompletes.

2Policies&Performance

Wederiveworstcaseperformanceguaranteesfortheexpectedperformanceofsimple,combinatorialonlineschedulingpoliciesforthestochasticonlineschedul-ingmodelonasinglemachineandonidenticalparallelmachines,respectively.Fortheanalysisofpoliciesrespectingreleasedates,werestrictourselvestoran-domvariablesthatwecallδ-NBUE.ThisisageneralizationofNBUErandomvariables.

Definition1(δ-NBUE).Anon-negativerandomvariableXisδ-NBUEif,forδ≥1,

E[X−t|X>t]≤δE[X]forallt≥0.OrdinaryNBUEdistributionsarebydefinition1-NBUE.

Inourperformanceanalysis,wecruciallyexploitthefactthatlowerboundson

theexpectedvalueofanoptimalpolicyknownfromstochasticschedulingcarryovertotheSossetting.Weutilizethefollowingohring,Schulz󰀄lower󰀁boundbyM¨OPTandUetz[1]ontheexpectedperformanceEZofanoptimalstochasticschedulingpolicy.

󰀂

Lemma1(M¨ohringetal.[1]).ForanyinstanceofP|rj|E[wjCj],wehavethat

E[Zopt]≥

󰀃

j

wj

k∈H(j)

󰀃E[Pk](m−1)(∆−1)󰀃

−wjE[Pj],m2mj

where∆boundsthesquaredcoefficientofvariationoftheprocessingtimes,that

2

is,Var[Pj]/E[Pj]≤∆foralljobsj=1,...,nandsome∆≥0.

StochasticOnlineScheduling

2.1

Stochasticonlineschedulingonasinglemachine

3

󰀂

Forthesinglemachineproblem1|rj|E[wjCj]inthestochasticonlineschedul-ingmodelweconsiderthefollowingpolicywhichwasproposedforparallelma-chinesbyMegowandSchulzin[2]inthedeterministiconlinesetting.

α-Shift-WSEPT

󰀂

Modifythereleasedaterjofeachjobjsuchthatrj=max{rj,αE[Pj]},forsomefixedα>0.Atanytimet,whenthemachineisidle,startthejobwithhighestpriorityintheWSEPTorder(i.e.,thejobwithhighestratioofweighttoexpectedprocessingtime)amongallavailablejobs,respectingthemodifiedreleasedates.

Theorem1.Theα-Shift-WSEPTalgorithmisa(δ+2)-approximationfor󰀂

theSosproblem1|rj|E[wjCj],forδ-NBUEprocessingtimes.Thebestchoiceoftheparameterαisα=1.

ForNBUEdistributedprocessingtimesthisresultmatchesthebestknownLPbasedperformanceboundderivedbyM¨ohringet.al[1]forstochasticscheduling.Intheonlinesetting,thebestpossiblealgorithmisexactly2-competitivewhichisshownin[3],[4].2.2

Stochasticonlineschedulingonparallelmachines

Intheparallelmachineenvironmentweapplythefollowingsimple,combinato-rialschedulingpolicythatwecallMinIncrease.Weschedulejobsthathavebeenassignedtothesamemachineintheα-Shift-WSEPTorder.Theonlinedecisionsonjob-to-machineassignmentsaremadeasfollows:assoonasajobispresented,weassignittothatmachinewhereitcausestheminimalincreaseintotalexpectedobjectivevalue,giventhejobsoneachmachinewouldbesched-uledinWSEPTorder(non-increasingratiosofweightoverexpectedprocessingtimes).Note,thatinordertoassignjobstomachines,wecompletelyignorere-leasedatesandinformationaboutrealprocessingtimeswhichcouldbeobservedfromtheschedule.

󰀂

Theorem2.ConsiderthestochasticonlineschedulingproblemP|rj|E[wjCj].Giventhatallprocessingtimesareδ-NBUE,theMinIncreasepolicyisaρ–approximation,where

ρ=1+max{1+

δ(m−1)(∆+1),α+δ+}.α(2m)

2

Here,∆issuchthatVar[Pj]/E[Pj]≤∆foralljobsj.Inparticular,sinceall

processingtimesareδ-NBUE,weknowthat∆≤2δ−1intheaboveperformancebound.

4N.Megow,M.Uetz,T.Vredeveld

ForNBUEprocessingtimes,where√wecanchoose∆=δ=1,theapprox-2imationratioisminimal√forα=(5m−2m+1−m+1)/(2m),obtainingaratiooflessthan(5+5)/2−1/(2m)≈3.62−1/(2m),improvinguponthepreviouslybestknownapproximationratioof4−1/mfrom[1]forthestochas-ticproblem.Moreover,fordeterministicinstancesthisperformancematchesthecurrentlybestknowncompetitiveratioof3.28from[2]fordeterministiconlinescheduling.

Inthespecialsettingwhereallreleasedatesareequal,ourMinIncreasepolicyindeedchoosesforeachjobjthemachinewhereitcausestheleastincreaseintheexpectedvalue,giventhepreviouslyassignedjobs.Weproveaperformanceratioof

(∆+1)(m−1)1+

2m

whichmatchesexactlythecurrentlybestknownperformanceguaranteefortheclassicalstochasticsetting,whichwasderivedfortheperformanceoftheWSEPTrulein[1].TheWSEPTrule,however,requirestheknowledgeofalljobswiththeirweightswjandexpectedprocessingtimesE[Pj]attheoutset.

Finally,weremarkthattheMinIncreasepolicycanbeseenasderandomizedversionofapolicythatassignjobsuniformlyatrandomtooneofthemachines.

References

1.M¨ohring,R.H.,Schulz,A.S.,Uetz,M.:Approximationinstochasticscheduling:thepowerofLP-basedprioritypolicies.JournaloftheACM46(1999)924–942

2.Megow,N.,Schulz,A.S.:On-lineschedulingtominimizeaveragecompletiontimerevisited.OperationsResearchLetters32(5)(2004)485–490

3.Anderson,E.J.,Potts,C.N.:On-lineschedulingofasinglemachinetominimizetotalweightedcompletiontime.MathematicsofOperationsResearch29(2004)686–697

4.Hoogeveen,H.,Vestjens,A.P.A.:Optimalon-linealgorithmsforsingle-machinescheduling.InCunningham,W.H.,McCormick,S.T.,Queyranne,M.,eds.:Proceed-ingsoftheFifthConferenceonIntegerProgrammingandCombinatorialOptimiza-tionIPCO.Volume1084ofLectureNotesinComputerScience.,Berlin,Springer(1996)404–414