Seite - 49 - in Algorithms for Scheduling Problems
Bild der Seite - 49 -
Text der Seite - 49 -
Algorithms 2018,11, 80
complementaryscheduleS1 (Figure2), therearisesanewkernelwithin thesecondbin.Note that the
execution intervalofkernelK1 inschedulesSandS1 isdifferent (it is [35,40) inscheduleSand [30,35)
inscheduleS1). Correspondingly, thefirstbin isextendedupto timemoment35 inscheduleS, and it
isextendeduptoTime30 inscheduleS1. ThenewlyarisenkernelK2=K(S1)defines twonewbins in
scheduleS1;hence, that schedulecontains threebins, in total.
Ingeneral, thestartingandcompletiontimesofeverybinarenotapriorifixed; theyaredefinedin
accordancewith theallowableflexibility for thecorrespondingkernel intervals.Ourschemeproceeds
inanumberof iterations. Toevery iteration,acompleteschedulewithaparticulardistributionof jobs
into thebinscorresponds,whereas thesetof jobsscheduled ineverykernel interval remains thesame.
In thisway, twoormore complete schedules for the samepartitionmightbe created (for instance,
schedulesS1 and (S1)1 ofExample1; seeFigures2and3).Atan iterationh,duringtheschedulingofa
bin, anewkernelmayarise,which isaddedto thecurrent setofkernelsK (kernelK2 ariseswithin
thesecondbin incomplementaryscheduleS1 ofExample1): theupdatedsetcontainsall the former
kernels togetherwith thenewlyarisenone (since scheduleSofFigure 1 containsonlyonekernel,
K={K1}, thereareonly twobins in it; thenextgeneratedscheduleS1 ofFigure2containsalready
twokernelsK1 andK2,K={K1,K2}andthreebins).Note that thepartitionof theschedulinghorizon
ischangedevery timeanewkernelarises.
Adjustingtimeintervalsforkernelandbinsegments: Althoughthetimeintervalwithinwhich
eachkernelcanbescheduledis restricted, ithassomedegreeofflexibility,aswehave illustrated in
Example1. Inparticular, theearliest scheduled jobofakernelKmightbedelayedbysomeamount
withoutaffecting thecurrentmaximumjob lateness. Denote thismagnitudeby δ(K).Without loss
ofgenerality, themagnitudeδ(K) cantake thevalues fromthe intervalδ(K)∈ [0,pl],where l is the
delayingemerging job forkernelK in the initially constructedED-scheduleσ. Indeed, if δ(K)= 0,
thekernelwillnotbedelayed,whereasδ(K)= pl corresponds to thedelayof thekernel in the initial
ED-scheduleS (which is19 forkernelK1 inscheduleSofFigure1). Inparticular,welet pmaxbethe
maximumjobprocessingtimeandshallassume,without lossofgenerality, thatδ(K)≤ pmax.
Todefineδ(K), letusconsiderapartial scheduleconstructedbytheEDheuristics foronly jobsof
kernelK∈K. Thefirst job inthatschedulestartsat time r(K) (weassumethat there isnoemerging job
within that sequence,asotherwisewecontinuewithourpartitioningprocess).Note that the lateness
of theoverflowjobof thatpartial schedule isa lowerboundonthemaximumjob lateness;denote this
magnitudebyL∗(K). Then,L∗=maxK∈K{L∗(K)} isalsoa lowerboundonthesameobjectivevalue.
Now,weletδ(K)=L∗−L∗(K), foreverykernelK∈K. The followingobservation isapparent:
Observation4. For δ(K) = 0, the lateness of the latest scheduled job of kernel K is a lower bound on the
optimal job lateness, and forδ(K)= pl, it is avalidupperboundonthe sameobjectivevalue.
Observation5. Ina scheduleSoptminimizing themaximumjob lateness, everykernelK starts eitherno later
thanat timer(K)+δ(K)or it isdelayedbysomeδ≥0,whereδ∈ [0,pmax].
Proof. First note that in any feasible schedule, everykernelK canbedelayedby theamount δ(K)
without increasing themaximumjob lateness.Hence,kernelKdoesnotneedtobestartedbefore time
r(K)+δ(K). Furthermore, inanycreatedED-schedule, thedelayofanykernelcannotbemore than
pmax, as foranydelayingemerging job l, pl≤ pmax.Hence,δ∈ [0,pmax].
Thus for a givenpartition, the starting and completion timeof every bin in a corresponding
completeschedulemayvaryaccordingtoObservation5.Ourschemeincorporatesabinarysearch
procedure inwhich the trialvalues forδaredrownfrominterval [0,pmax]. Toevery iteration in the
binarysearchprocedure, sometrialvalueofδ corresponds,whichdetermines themaximumallowable
job lateness,aswedescribebelow.
Weobserve thatnotallkernelsare tight in thesense that, foragivenkernelK∈K,δ(K)mightbe
strictlygreater thanzero. ByObservation5, inanygeneratedschedulewith trialvalueδ, everykernel
49
zurück zum
Buch Algorithms for Scheduling Problems"
Algorithms for Scheduling Problems
- Titel
- Algorithms for Scheduling Problems
- Autoren
- Frank Werner
- Larysa Burtseva
- Yuri Sotskov
- Herausgeber
- MDPI
- Ort
- Basel
- Datum
- 2018
- Sprache
- englisch
- Lizenz
- CC BY 4.0
- ISBN
- 978-3-03897-120-7
- Abmessungen
- 17.0 x 24.4 cm
- Seiten
- 212
- Schlagwörter
- Scheduling Problems in Logistics, Transport, Timetabling, Sports, Healthcare, Engineering, Energy Management
- Kategorien
- Informatik
- Technik