Page - 48 - in Algorithms for Scheduling Problems
Image of the Page - 48 -
Text of the Page - 48 -
Algorithms 2018,11, 80
For theprobleminstanceofExample1,weformsetEwithasingleemergingJob1andobtain
acomplementaryscheduleS1=(2,0)(3,30)(1,35)(4,40)(5,50)(6,60)(7,70), asdepicted inFigure2.
There isasinglekernelK2=K(S1)consistingof Jobs5,6and7withLmax(S1)=L7,S1 =80−52=28
inscheduleS1 (note thatL3,S1 =35−11=24).
Figure2.ComplementaryED-scheduleS1 forExample1.
Theproofofournextobservationcanbeseen in [26].
Property 1. Suppose in schedule SE there arises a (possibly zero-length) gap before kernel K = K(S).
Then, that schedule is optimal forproblem1|rj|Lmax ifK(SE)=K(S).
Notethattheabovepropertyyieldsanotherhaltingconditionforproblem1|rj|Lmax. Thefollowing
example illustrates thatactivationofanemerging jobdoesnotalwaysyieldan improvement in terms
of theminimizationof themaximumjob lateness.
Example 2. Now,we forman instancewith six jobs as follows. Jobs 4 and6 are kernel jobs, each defining
adistinct kernelwith thedelaying emerging Jobs3and5, respectively. Jobs1and2are other emerging jobs.
All emerging jobsare releasedatTime0,whereaskernel Jobs4and6are releasedatTimes20and50respectively;
p1= p2= p4= p6= 5, p3= 25, p5= 20. Theduedates of emerging jobsare large enoughnumbers, Jobs
1and2beingslightlymoreurgent thanthedelayingemerging Jobs3and5;d4=25andd6=55. ThenED
heuristicswill deliver solutionS=(1,0)(2,5)(3,10)(4,35)(5,40)(6,60)with thedelayingemerging Job3.
The lateness of Job 4 is 15, and that of Job 6 is 10; Job 4 forms the first kernelwith the only overflow Job 4.
In the complementary scheduleS4=(1,0)(2,5)(4,20)(3,25)(5,50)(6,70), there arises agap (10,20). In that
schedule, anewkernel is formedby Job6,whichcompletes atTime75andhas the latenessof20. This example
suggests that, insteadof creatingscheduleSl, it couldhavebeenbetter to consider scheduleSE, foraproperly
selected setE.
4. PartitioningtheSchedulingHorizon
In this section, we start the construction of a bridge between the two scheduling problems
1|rj|Lmax and1|rj|Cmax establishingahelpful relationshipbetweentheseproblemsandaversionof
awell-studiedbinpackingproblem. Tobeginwith,we introduceourbins. Thenotionof abin is
closely tiedto thatofakernel.GivenanED-schedulewithasetofkernels,wedefinethebins in that
ED-scheduleas thesegmentsor the intervals leftoutside thekernel intervals. Thebinswillbepacked
withnon-kernel jobs, andsince, the intervalwithinwhicheverykernel canbescheduledhassome
degreeofflexibility, thebinsaredefinedwith thesamedegreeofflexibility.Abusingthe terminology,
wewilluse the term“bin” forboth the timeintervalandthecorrespondingscheduleportion,aswell.
Note that there isabinbetweentwoadjacentkernel intervalsandabinbefore thefirstandafter the
lastkernel interval; anykerneldefines twoneighboringbinsadjacent to thatkernel,oneprecedingand
onesucceedingthatkernel.
Wefirstdescribehowweobtainapartitionof the schedulinghorizon into thekernel andbin
intervals. In thenextsection,weexplainhowthispartition isusedfor thesolutionofourbi-criteria
schedulingproblemthat is reducedtothedistributionofnon-kernel jobswithinthebins insome(near)
optimal fashion(that takes intoaccountbothobjectivecriteria).
The initialpartitionisconstructedbasedontheearliestkernel identifiedinthe initialED-schedule
(one constructed for the originally given problem instance). This kernel already defines the
correspondingtwobins in that initialpartition. For instance, inscheduleSofExample1 (Figure1),
kernelK1=K(S) isdetected,whichalreadydefinesthetwobinsinthatschedule. Inthenextgenerated
48
back to the
book Algorithms for Scheduling Problems"
Algorithms for Scheduling Problems
- Title
- Algorithms for Scheduling Problems
- Authors
- Frank Werner
- Larysa Burtseva
- Yuri Sotskov
- Editor
- MDPI
- Location
- Basel
- Date
- 2018
- Language
- English
- License
- CC BY 4.0
- ISBN
- 978-3-03897-120-7
- Size
- 17.0 x 24.4 cm
- Pages
- 212
- Keywords
- Scheduling Problems in Logistics, Transport, Timetabling, Sports, Healthcare, Engineering, Energy Management
- Categories
- Informatik
- Technik