Seite - 43 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 80 minimizemaximumjob latenesswasproposedbyCarlieretal. [22],whereas thepractical importance of thesolutionswithno idle timeintervalswasemphasizedbyChrétienne[23]. In general, in an optimal solution to problem 1|rj|Lmax, some idle time intervals might be unavoidable (a non-urgent job has to wait until a more urgent one gets released; hence, thecorresponding idle timeintervalarises): aprobleminstancemighteasilybeconstructedpossessing anoptimalsolutionto1|rj|Lmax,butwithnofeasiblesolutionfor1|rj,nmit|Lmax (seeSection2). In thispaper,basedonthestudyof thepropertiesof theschedulesgeneratedbytheEDheuristics andthetiesof theschedulingproblem1|rj|Lmaxwithaversionof thebinpackingproblem,wepropose ageneral solutionmethodthat isorientedtowardbothobjectivecriteria, themaximumjoblateness andthemaximumjobcompletiontime(themakespan).Consideringasinglecriterionproblem,we firstobserve thatdifferent feasiblesolutionswithdifferentmakespansmayposses thesamemaximum joblateness. Though,aswewill see,findingonewith theminimummakespanisNP-hard.Viewing theproblemin lightof thebinpackingproblemwithdifferentbincapacities,weshowhowtheknown heuristic algorithmswith reasonablygoodapproximations canbe adopted for the solutionof the bi-criteriaproblem. Weestablish theconditionswhenthePareto-optimal frontierwith the twoobjective functions (themaximumlatenessand themakespan) canbe formed inpolynomial time. This, togetherwith a general algorithmic framework that we present, provides a method for the construction of (exponential-time) implicit enumerationalgorithmsandpolynomial-timeapproximationalgorithms (the latter approximation algorithms generate a Pareto-sub-optimal frontierwith a “fair balance” betweenthe twoobjectives). Our framework applies the partition of the scheduling horizon into two types of segments containingurgent andnon-urgent jobs, respectively. Intuitively, segmentswithurgent jobs are to occupyquite restrictedtimeintervals,whereas thesecondtypeofsegmentscanbefilledout, insome optimal fashion,withnon-urgent jobs. Theurgencyof jobs isdeterminedbasedonthefirstobjective criterion, i.e., such jobsmaypotentially realize themaximumlateness in theoptimalscheduleSopt for problem1|rj|Lmax. Wedetermine the time intervalswithinwhich a sequence of urgent jobs is to be scheduled. We refer to such sequences askernels and to the intervals inbetween themasbins. Ourscheme, iteratively,fills inthebinintervalsbythenon-urgent jobs; itdeterminesthecorresponding kernel segmentsbefore that. The lessgapsare leftwithin thebin intervals, the less is the resultant maximumjobcompletion time,whereas thewaythebin intervalsarefilledout is reflectedalsobythe maximumjob lateness. Weexploit theobservation that the total idle time interval inabinofagivenfeasibleschedule canbereducedwithout increasingthemaximumjob latenessof that schedule. Thiskindof“separate” scheduling turns out to be helpful in the search for a compromise between the two objectives. Inpractice,analyzingthecomputationalexperiments for theproblem1|rj|Lmax reportedin[9],wemay assert that, by incorporating theEDheuristics intoour scheme, abalanceddistributionof the jobs within thebins imposingalmostneglectabledelays for thekernel jobscanbeobtained. For thevast majorityof the tested instances in [9], themaximumjob lateness isveryclose to theoptimum.At the sametime, since theEDheuristicscreatesnoavoidablemachine idle time, theminimummakespanis achieved.Wediscuss this issue inmoredetail inSection5. InSection2,westudyour twoobjective functionsandestablish the timecomplexityof related Pareto-optimalproblems. InSection3,wegivenecessarypreliminaries toouralgorithmic scheme. InSection4,wedescribeourmethodforpartitioningthewholeschedulinghorizonintourgentand non-urgentzones. InSection5,we introduce thebinarysearchprocedure that isused toverify the existenceof a feasible solutionwith some threshold lateness anddescribe the rest of theproposed framework. InSection6,wegivefinal remarks. 43