Page - 48 - in Algorithms for Scheduling Problems

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