Page - 53 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 80 Theorem2. Suppose, in the iterationof thebinarysearchprocedurewith trialδ, all thebinsare scheduledat Phase1, i.e.,no IA(b2)atPhase1arises. Then, a complete schedule inwhich the latenessofno job isgreater than L(δ) is constructed in timeO(n2 logn). This schedule isPareto sub-optimal, and it isParetooptimal ifno idle time interval inanybin is created. Proof. For every bin B, since no IA(b2) during its construction at Phase 1 arises, this phase will output a partial schedule for that bin, in which the lateness of no job is greater than L(δ) (Lemmas 2 and 3). At the same time, by our construction, no kernel jobmay result in a lateness greater thanL(δ). Then, the maximumjoblateness in theresultantcompleteschedule isnogreater thanL(δ). This schedule isParetosub-optimaldueto theDNFheuristics (withaknownsub-optimal approximationratio). Furthermore, ifno idle time interval inanybin iscreated, theremayexistno feasiblesolutionwith themaximumjob latenessL(δ) suchthat the latest scheduled job in it completes earlier than in theabovegeneratedsolution;hence, it isParetooptimal. Let us now estimate the cost of Phase 1. For the purpose of this estimation, suppose n1 (n2, respectively) is thenumberofy-jobs (x-jobs, respectively). In thefirstpass,y-jobsarescheduledby theEDheuristics in timeO(n1 logn1) if all the scheduledbinsarey-complete. Otherwise, sinceno IA(b2)arises, each timetheschedulingofabincannotbecompletedbyall they-jobs,anewkernel is declared that includes the corresponding y-jobs (Lemma1). Since theremay arise less than n1 different kernels, thenumber of times anewkernelmayarise is less thann1. Thus, the same job willberescheduledless thann1 times (asabinorakernel job),whichyields the timecomplexityof O(n21 logn1) for thefirst pass. Since the time complexityof theDNFheuristics is the sameas that ofEDheuristicsusedat thefirstpassandnewkernelsaresimilarlydeclared(Lemma3), thecostof thesecondpass issimilarlyO(n22 logn2). Thus, theoverall cost for theconstructionofall thebins is O(n2 logn),which is also the cost of theoverall schemesince thekernel jobs are scheduledby the EDheuristics. Notethatthesecondconditionintheabovetheoremissufficient,butnotnecessaryforminimizing themakespan; i.e., somebins in a feasible schedule respecting threshold L(δ)mayhave idle time intervals, but that schedulemayminimize themakespan. In general, we rely on the efficiency of theheuristicsusedforpackingourbins for theminimizationof themakespancriterion.Wealso straightforwardlyobservethatbytheDNFheuristicss,nounscheduledjobmayfitwithinanyavailable gapinanybinwithout forcingsomeother jobtosurpass thecurrentallowable latenessL(δ)atPhase1, whereas theDNF-heuristicss tends tokeepreserved“short”unscheduled jobs. Continuingwith the issueof thepracticalbehavior,aswehavementionedintheIntroduction, the EDheuristics turns out to be an efficient tool for a proper distribution of the jobswithin the bins. In [9], computationalexperimentswereconductedfor200randomlygenerated instancesofour problem. For themajorityof these instances, the forceddelayofkernelK(S) in the initialED-schedule S (i.e., thedifferencebetweenthecompletiontimeof thecorrespondingdelayingemerging joband r(K))wasneglectable. Therefore, the latenessof thecorrespondingoverflowjobwaseitheroptimal orveryclose to theoptimalmaximumjob lateness (asno jobofkernelK canbestartedearlier than at time r(K) inanyfeasiblesolution).At thesametime,since theEDheuristicscreatesnoavoidable machine idle time interval, theminimummakespan isalsoachieved. Thus, for themajorityof the testedprobleminstances,bothobjectivecriteriaweresimultaneouslyminimizedor themaximumjobs latenesswasveryclose to theoptimum,whereas themakespanwasoptimal. Thecomputationalexperiments from[9]alsoyield that, formostof the tested instances,already forsmalltrialδ’s, thebinswouldhavebeenscheduledinPhase1(i.e.,noIA(b2)wouldarise).Moreover, therewill benoavoidable gap leftwithin thebins for these δ’s. In otherwords, the conditions in Theorem2wouldbesatisfied, andPhase1wouldsuccessfully completed. In theory,however,we cannotguaranteesuchabehavior,andweproceedwithourconstruction inPhase2. 53