02 Semi-online scheduling with decreasing job sizes

半在线调度与减少工件的大小

OperationsResearchLetters27(2000)

215–221

http://wendang.chazidian.com/locate/dsw

Semi-onlineschedulingwithdecreasingjobsizes

SteveSeidena; ;1,JiÄrà Sgallb;c;2,GerhardWoegingerd;3

ofComputerScience,LouisianaStateUniversity,298CoatesHall,BatonRouge,LA70803,USAbMathematicalInstitute,ASCR,ZitnÃÄa25,CZ-11567Praha1,CzechRepublic

cDepartmentofAppliedMathematics,FacultyofMathematicsandPhysics,CharlesUniversity,Praha,CzechRepublic

dInstitutf urMathematik,TechnischeUniversit atGraz,Steyrergasse30,A-8010Graz,Austria

Received28October1998;receivedinrevisedform1July2000

aDepartment

Abstract

Weinvestigatetheproblemofsemi-onlineschedulingjobsonmidenticalparallelmachineswherethejobsarriveinorder

ofdecreasingsizes.Wepresentacompletesolutionforthepreemptivevariantofsemi-onlineschedulingwithdecreasingjobsizes.Wegivematchinglowerandupperboundsonthecompetitiveratioforanyÿxednumbermofmachines;these√

boundstendto(1+=2≈1:36603,asthenumberofmachinesgoestoinÿnity.Ourresultsarealsothebestpossibleforrandomizedalgorithms.Forthenon-preemptivevariantofsemi-onlineschedulingwithdecreasingjobsizes,aresultofGraham(SIAMJ.Appl.Math.17(1969)263–269)yieldsa(4=3 1=(3m))-competitivedeterministicnon-preemptivealgorithm.Form=2machines,√weprovethatthisalgorithmisthebestpossible(itis7=6-competitive).Form=3machineswegivealowerboundof(1+=6≈1:18046.Finally,wepresentarandomizednon-preemptive8=7-competitivealgorithm

c2000ElsevierScienceB.V.Allrightsreserved.form=2machinesandprovethatthisisoptimal.

Keywords:Analysisofalgorithms;Onlinealgorithms;Competitiveratio;Scheduling

1.Introduction

Considerthefollowingschedulingproblem:we

areconfrontedwithasequenceofjobswithprocess-Correspondingauthor.

E-mailaddresses:sseiden@http://wendang.chazidian.com(S.Seiden),sgall@math.cas.cz(J.Sgall),gwoegi@opt.math.tu-graz.ac.at(G.Woeginger).1ThisresearchwasdoneattheTechnischeUniversit atGraz,supportedbytheSTARTprogramY43-MAToftheAustrianMinistryofScience.

2PartiallysupportedbygrantA1019901ofGAAVCR,Äpost-Ädoctoralgrant201=97=P038ofGACR,andcooperativeresearch

ÄgrantINT-9600919=ME-103fromtheNSFandMSMTCR.

3ThisresearchhasbeensupportedbytheSTARTprogramY43-MAToftheAustrianMinistryofScience.

ingtimesp1;p2;:::;pnthatmustbeassignedtommachines.Theloadofamachineisthesumoftheprocessingtimesofthejobsassignedtothatma-chine.Ourgoalistominimizethemakespan,i.e.,themaximummachineload.Iftheproblemisonline,theneachjobmustbeassignedwithoutknowledgeofsuccessivejobs.(However,theorderofjobshasnocorrelationwiththetimeintheschedule,somefuturejobmaybeassignedtostartrunningearlierthanthecurrentone.)Iftheproblemissemi-onlinewithde-creasingjobsizes,thenweknowthatpi¿pi+1foralli¿1.Hence,inthisvariantwedohavesomepartialknowledgeonthefuturejobs,whichmakestheprob-lemeasiertosolvethanstandardonlineschedulingproblems.

c2000ElsevierScienceB.V.Allrightsreserved.0167-6377/00/$-seefrontmatter

PII:S0167-6377(00)00053-5

半在线调度与减少工件的大小

216S.Seidenetal./OperationsResearchLetters27(2000)215–221

AThetheismeasuredqualityofbyanitsonlinecompetitiveorsemi-onlineratioalgorithmL;smallestnumbercsuchthatforevery,listdeÿnedofjobsasofA(L)6copt(L),whereA(L)denotestheainglistscheduleLofjobs,producedandopt(byLalgorithm)denotesAthefortheschedulingmakespaningWemakespanofsomeoptimalschedule.

correspond-non-preemptivejobstudysizesinsemi-onlinethethreemainschedulingvariants:withpreemptive,decreas-randomizeddeterministicscheduling.deterministic,ulesnon-preemptiveNotethatandformnon-preemptive=1thetrivialingforanyalljobsidleonthesinglemachinealgorithmwithoutthatintroduc-sched-jobthebemayrestbeoftimepreempted,theispaper.optimal.Thus,weassumem¿2i.e.,Inthesplitpreemptiveintopiecesvariant,thatmayanon-consecutivespreadoverseveralsametimeslots.machinesHowever,and=orpiecesassignedtoonsigneddi erentjobmustmachines.notoverlapintime,evenifscheduledoftheortotimeslots(sIn;totherwords,ifajobisas-11];(s2;t2];::mustseveralassignbedisjoint.machines,Uponthen:;(sk;tk]ononearrivalanypairofeachofthesejobwetimeslotsmayever,createittocasebyObservationidleparticulartimethattimeslots,whichinprinciplehaveto4:1inisused[7],bylaterjobs.How-algorithmaswell,whichappliesinournon-preemptivesowethatmayalwaysmodifyanypreemptivereasons.

variantsitnevertheintroducessameistrueidletimes,fortrivialforlower(1)Foranyandtheupperpreemptiveboundsonvariant,thewegivematchingcreaseÿhttp://wendang.chazidian.competitiveratiofor(1+√These=2≈1bounds:36603,in-asarenumberOuralsotheofbestmachinespossiblegoesforrandomizedtoinÿnity.Ourresultssizesupperofaredecreasing;bounddoesevennotreallyrequirethatalgorithms.thejobwe(2)thelargesttheknowledgeofthesizeForthejobwouldbesu cient.

boundgiveshownofa(1lowernon-preemptive+√

bound=6offor7=m6=fordeterministicm=2andvariant,alowergorithmthatformm=Listfordecreasingjobsizes,3.Grahamthegreedy[11]hasal-2is(4=3 1=(3m))-competitive.Hence,the¿3,theproblemmachinesremainswehaveopen.matchingQuitesurprisingly,bounds.Forratiosnon-preemptivethanthepreemptivevariantvariantallowsdoes.betterIncompetitivefact,even

Listblelimit.withachievessicalInthepreemption)abetterforcompetitiveeverym¿2ratioaswell(thanaspossi-intheunexpectedonlinelightschedulingofthecorrespondingoccurrenceandtoour(seeknowledge,below)thisresultsforclas-itiswasalsocertainlythevariant,(3)Finally,ofthisforphenomenon.

ÿrstthenon-preemptiverandomized8Our=7-competitiveform=2machines,wepresentarandomizedtionalgorithmisalgorithmbarelyrandomandprovethatitisoptimal.Eachoveraÿxednumberofdeterministic[15],i.e.,algorithms.adistribu-usestheunboundedotherO(1)jobishand,space.scheduledinO(1)time,andthealgorithmtheForknownclassicaloptimalonlinealgorithmscheduling,onalsospaceusesoverall. (numberi)Fortimeofmtorandom¿3,schedulechoicestheproblemtheith[3].remainsjobInusesandfact,anopen. (nit)Relatedaresemi-onlineobtainedwork.byOtherAzarresultsandonsemi-onlineproblemsisconsiderknownschedulingwhereRegevtheoptimum[2]whomakespanconsiderproblem,severalinadvance,semi-onlineandbyversionsKellereretal.[13]whochines.whichcorrespondstoschedulingoftheonpartition2ma-scheduleLiunumbermustetal.be[14]investigatetheproblemwhereatimes.

ofjobsandcreatedtheorderingwithknowledgeoftheironlyprocessingoftheareInthestandardonlineproblem(wherethejobsizesants,notnon-preemptivepreemptive,necessarilynon-preemptivedecreasing)allthethreemainvari-incompletelytheliterature.randomized,Thepreemptivehavedeterministic,beeninvestigatedandalgorithmbyChenetal.[7]whovariantdesignedwasansolvedwithcompetitiveforpreemptiveratio

schedulingonmmachinesonlineÿ(m)=mme

→

≈1:58198:(1)

TheywhichalsoItevengaveholdsamatchingforlowerboundconstruction

lineisageneralphenomenonrandomizedthatforonlinepreemptivealgorithms.on-andschedulingsemi-onlineaswenotedproblemsvariantabove,studiedtherandomizationdoesnothelp,insamethisispaper.

truealsoforthehamForplaces[10]theeachdeÿnednon-preemptivejobonathesimplemachinegreedydeterministicvariant,Gra-whichalgorithmiscurrentlyListwhichleast

半在线调度与减少工件的大小

S.Seidenetal./OperationsResearchLetters27(2000)215–221217

loaded.onseminalmmachines;HeshowedthisthatanalysisListisis(2tight. 1=mSince)-competitiveGraham’shavepetitiveinvestigatedwork,manythisproblem.researchers[3–6,8,9,12,16–18]knowntoratiolieinforthealargeintervalnumberThe[1:852ofbest;1machinespossible:923];cf.[1].iscom-nowizedOnlyal.onlinelittlescheduling.isknownaboutFormnon-preemptive=2random-gorithm.[3]giveshowChena4=3-competitiverandomizedmachines,onlineBartalal-etNoteBartalthatanonlineetthisboundloweral.[5]exactlyboundandSgallofmatchesÿ[19](m)forindependentlytheanym¿1.domizedetal.form=2.Seiden[16,17]presentsboundran-ofterministiconlinecounterpartsalgorithmsforwhichm=3outperform;:::;7.theirde-2.Preemptivescheduling

lossThroughoutthissection,wewillassume,withoutjobthehasofgenerality,size1.First,thattothedevelopÿrst(andhencelargest)sequenceoptimalthatwillbeofalgorithm,wedescribetheitsintuitionactionbehindontheusedjobsinofthesize1;thisisalsothesequenceWeSupposebeforeschedulewewanttoachievelowerboundcompetitiveargument.

ratioc¿1.bytimec;theweÿrstdothatmjobsduringthetimeslotsmachinesone(sincekandcthe¿1,twoeachtimejobbyÿllingslotsissplitthemachinesonedonotontooverlap).atmosttwoLetthat= ici=mm=c of.Foritsloadi6kis,thescheduled(m+i)thafterjobisscheduledsojobmachines,machinesisscheduledeachreceivingbeforetimeloadc.c=mThe,andtimeilargesttheconresttheÿrstloadsoftheof1slots=m),whichwillguaranteesbec(1+i=mthat),inc(1+(thei 1)=m);:::;c(1+jobssimilararedonotscheduledoverlap.onlyAfterduringthe(mnextthe+kround,thetimeslots)thjob,afterthecnewinatovaluechoosemanner,enoughofctheonatmostk+1machines.Weneedsorightthatthisvalueschemeofkandworks,thecorrespondingtimesothattheloadweneedtoschedulei.e.,cisbeforelargeForc0is6atk6mostm,wecm.

deÿnevalues m;k

=

2m2+2mk

; m=k=0max;:::;m

m;k:

For any m¿2,letk(m)bethelargestintegersatisfyingm=m;k(m).

Lemmahold(i):2.1.Foreverym¿2thefollowingconditions16 √

m6(1+=≈1:36603.Moreover;as(iii)(ii)m1 6→k(∞m);= (1+2√

m→=2..

m= m ¡m.m¡ m+1Proof.x(i)Obviously16 m;k6(2+x)=(2+x2),where√=for k=mconvergesm1largeand.Thishasrationalfunctionismaximized√forx=andmaximalkvalue√= m√(1+=2.Moreover,(ii)Ifkto+1(16+m= =2.( 1) ,thevalueof m;km;kthen m;k+1=

(2m2+2mk)+2m

¿min

2m2+2mkm;

= m;k;

andkimplies¿thusm= k=k(m).Similarly,wecanverifythat,ifm;k,then m;k 1¿andk(mthusthatk(mk)(¿m)1.=For m= m;kandk=k(m).Thismm¿ .2Wewehavehave m;0=16 m;1m;m¿1,thusguish(iii))=twoLet m= km= 6k(m m= ),andm;m hence¡m.

m= m;k.Wedistin-thatFirst,assumecases.k≥(√

1)m.Inthiscaseweprovein m;k¡ m+1;k,whichimplies m¡ m+1.Pluggingshowsthedeÿnitions2mk¡that(k+1)the2 of¡ m;k and m+1;kandsimplifyingm;km+1;kisequivalentto2m2 2m2 2mk6k.2However,¡the2

assumptionimpliesthat

Second,assume(kk¡+1)(√,and 1)wem.areWedone.

provethatgingm;k¡ m+1;k+1,whichalsoimplies plifyingintheshowsdeÿnitionsthat of¡ m¡ m+1.Plug-m;k and m+1;k+1andsim-m;km+1;k+1isequivalentto(k m)(k2+2km 2m2)+k(3k m+2)¿0:Ourpositive.assumption Fromimpliesthattheÿrsttermisondm= (ii)and(i)weobtainthatk=termm ¿ ism=non-negative,2 ¿m=2 1.andThistheimpliesproofisthatcomplete.

thesec-

半在线调度与减少工件的大小

218S.Seidenetal./OperationsResearchLetters27(2000)215–221

Theorempetitiveemptivedeterministic2.2.Foreverym¿2;thereexistsa mcom-jobsizes.

schedulingonalgorithmmmachinesforsemi-onlinewithdecreasingpre-Proof.integerLetc= m,andletk=k(m)bethelargestalgorithm:forofSupposewhich mthat= atm;kthe.ConsiderthefollowingofingsizetotaltimeTarealreadyscheduledcurrentandmoment,thatajobsjobassignmentanyt6idle1timearrives.betweenWescheduleconsecutiveitwithoutjobintroduc-eralnevercases;overlap:

wetotheprovemachineslaterthatisdescribedtheassignedbelowpieces.timeinslotssev-The1.IfuledT+t6m,wescheduleMorebeforetimec,onthetheÿrstjobmachinesothatitissched-rentscheduleloadprecisely,lessthanifthechasÿrstmachinewithavailable.thecur-onthewholejobonloadit.Ifatnot,mostc t,we2.cIf,anditaportionofthejob,sothattheloadweschedulebecomesitc=m,1T6¿imthe6+resti 1onandtheTnext+t6machine.

m+iforsomeintegerjobofthek,schedulejob,andonscheduleeachoftheÿrstimachines3.inIfStepbefore1.

timecontheÿrstavailabletheremaindermachine,oftheas0tc=m6Ti66mk,+scheduleiandT+onteach¿m+ofitheforÿrstsomeintegeri,ofofthejob,onmachinei+1,(T+t immachines—thethethisjob(orthewholeremainder,ifitis smalleri)c=mremaindercanhappenoftheonlyjobbeforeifi=k),andschedule4.availableIfchinesT¿mmachine,asinStep1.

timecontheÿrstmachinetc=m+kk+of,schedule1.thejob,onandeachtheofremaindertheÿrstonkma-thetotalAtthemomentwherethealgorithmhasassignedinhavetheloadmiddleofmof+somei;i=0jobs),;:::;kthe(thisamachinesmoment1;may2;:comerespectively.loadsexactlyallThiscfollows(1+i=m);c(1+(i 1)=m):;::;:i:+1;c,thatcontributions.ifact¡ktheloadofmachineTheonlyi+non-trivialfromadding1is(notlesspartthethan)istoloadsverifyofc.Forcalculationthat,thiskis=truein alreadyaftertotalsizem(fromthethem=cnext ).Forparagraph.

i=k,itfollowsfromthescheduledBeforetimebeforem+timek,thecis

totalsizeofportionsofjobsm+k k(k+1)c

=cm

usingclaimthedeÿnitionofkandc= k.Thisimpliestheittimeisactuallyinthepreviouspossibleparagraph.toÿtallAlso,thisimpliesthatsamec.Theyarescheduledsothatthesenotwoportionspartsbeforeofsincejobrunatthesametimeondi erentmachines,theaAfterc¿1.

loadssingletotalc=mofmachineloadanytwoafterm,theofthesetimeportionofajobscheduledonmachinescisatmostdi erc=m.Sincethescheduledatalltimes,thesepiecesdonotoverlap.byForataleastjobmassigned+i,itatatotalloadT¡m+ibutÿnishedaftermachinemachineitoisstartsmachinesalsonecessaryatloadicandto(1+(iarguethatitsportionsT++11are notinparallel:mneed i)=mi),+1startsatcandÿnishesatm c(1i)+=m(),Twhile+t onwithmachinetoverifywhichk+1isthatissmallerinStepthesincet.Thelastfactwe4remaindersarenotscheduledofjobsscheduledinparallelakjobotherdi er= m=cofsizeportionsbyat .tisatofmostthesamet ktc=mjob.The¡tc=mremainder,becauseofleastThusc=mtheloadsofmachineskandk+1theTheabovecompetitiveclaimsaboutratioaftertheoftimetheloadsalgorithmm+k.

ofthealgorithm.isimpliedbyTheoremgorithm2.3.No(deterministicorrandomizedmcompetitive¿2machinesforsemi-onlineratiowithlessdecreasingpreemptivethan jobsizesscheduling)al-canhaveonam.

Proof.poseFixk6mandthatratioonthatthealgorithmisarandomizedc-competitive.algorithm.WewillproveSup-mLetisatheatsequenceleastrandomized ofm+kunitjobsthecompetitivem;k.Thisalgorithmimpliesrunc¿on m.

ai+kunitjobs.LetXsequenceofibethelasttimewhenatnotejobsisrandomized.thatareXrunningisa(afterschedulingallm+kjobs);leastiWerandomclaimvariable,thatfor0since6i6thek,

algorithmE[Xk+1 i]6

c(m+i)

:(2)Asthelongÿrstmas+ki+jobs1 isijobsrunning.arerunning,Therefore,atleasttheaverageoneof

半在线调度与减少工件的大小

S.Seidenetal./OperationsResearchLetters27(2000)215–221219

makespanleastmE[Xofthealgorithmontheÿrstm+ijobsisatk+1 i].Sincethefollows+ijobsThefromhasthemakespanoptimalc-competitiveness(m+i)=mschedulefortheseof,inequality(2)foreverytotalsizerandomofjobschoice,scheduledatmost

bythethealgorithmalgorithm.is, mXi6

kXi+(m k)Xk+1:

i=1

i=1

Thisobtain

sizehastobeatleastm+k,andbyusing(2)wem+k6

k Xi+(m k)Xk+16cm+k(k+1):i=1

(3)

Thislows.

isequivalenttoc¿ m;k.Thelowerboundfol-Corollaryrithm2.4.Thereexistsdecreasingforsemi-onlineadeterministicalgo-(1jobsizespreemptiveschedulingwithcan+√

achieve=2a≈better1:36603.whosecompetitiveratioiscompetitiveNorandomizedratio.algorithm3.Non-preemptivedeterministicschedulingTheoremsemi-online3.1.ingmjobsizesnon-preemptiveAnydeterministichascompetitiveschedulingalgorithmratioatwithforleastdecreas-√7=for=ingm2=;and3.Moreovercompetitive;forratiom=atleast(1+6for=6[11]).

7=6-competitivedeterministic2therealgorithmexistsa(match-duetoProof.instanceThecasem=2followsasin2.onIfadeterministicwith2jobsofalgorithmsize3followed[11]:putsthebyConsideran2jobs3jobsofsizeitstheofcompetitivesamemachine,ratioisnoatotherleastjobs2.Ifmayitputsarrive;ofsize3thehence,onsize3ondi erentmachines,itis7=2jobscompetitiveGraham’stightupperboundratiosequence.ofofListGraham[11]shows6-competitivethatthe7=6isfor4=m3 =12.

=(3m),thisgivesaboundNext,of

considerthecasem=3.Weshowalowerc=

1+√≈1:18046:Letjobxthreelist:=(7x; x;3c1) =6x;≈10 :57643.x;1Considerthefollowing(otherwisejobsmust=3;1=3and1=3.Theÿrst3thecompetitivegoonthreeratiopairwiseisatdistinctleastmachinesplacedc)¿1jobs,on:73479thesame¿c).1=x=6=(7 machineConsiderthefourthjob.Ifitisoptimalthen2o inethealgorithm’smakespanismakespanasone2(1 x);isofnote1,thewhereasÿrsttwothat1=(2thesamex)=3ÿnalmachine=(3c 1)as=thec.If thirdthefourthjob,jobisplacedonthemakespanmakespanonlinealgorithmfortheisathasentireleastcompetitivelist7=3is then1.2xthealgorithm’sratioSummarizing,=c.Theoptimalatleastc.any4.Non-preemptiverandomizedscheduling

non-preemptiveInthissection,wediscussrandomizedsemi-onlineonboundsm=2schedulingwithdecreasingjobsizesofmachines.8=7forthisWeproblem.

givematchinglowerandupperTheoremonlinesizesnon-preemptive4.1.Norandomizedschedulingalgorithmwithdecreasingforsemi-jobbetteronthanm=82=7.

machinescanhaveacompetitiveratioProof.ofalgorithmsize3Wefollowedconsideraprobleminstancewith2jobschinepetitivewithplacesby3jobsofsize2,asin[11].Iftheprobabilitytheÿrstmoretwothanjobs1onthesamema-andgorithmweratioaredone.isatleastIf((1=7)×6+(6=7,=7)then×3)the=3=8com-=7tiontheremainingnot,threethejobs.adversaryTheoptimalgivesthesolu-al-2linejobsplacesthe2size3jobstogetherandthe3size1jobs=7.algorithmtogether,Iftheonlinecanyieldingalgorithmdothisamakespanwithof6.Theon-hasprobabilityplacedthe2atmostachieveon((1=7)×isseparate67.machines,thebestmakespansizeitcan3+Therefore,(6=7)×7)the=6=competitive8=7.

ratioisatleastTheoremcompetitive4.2.Thereexistsschedulingchines.

withalgorithmarandomized8=7-decreasingforsemi-onlinejobsizesnon-preemptiveonm=2ma-Proof.placestheWeÿrstcalltwoourjobsmachinesonmachineAandABwith.Theprobability

algorithm