Page - 8 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 18 TheonlydifferencebetweenConditions 3 and4 iswhether dk+2 = 0ornot. This implies that periodk is the lastoff-peakperiodandperiodk+2doesnotexist.Hence,periodkmustbe in the last cycle (i.e.,on the lastday)andthereare twoscenarios thatshouldbeconsideredas follows(thezero pointsof the twoscenariosaredifferent). Scenario1: In this scenario,neitherperiodk+1norperiodk+2existsandfourpossiblepositions markedinFigure6aaregiven. Similar toCondition3,periodk is criticaldueto its lowestpriceand the longest remaining idle time. To insert job i intoperiodk, theother jobsprocessedwithinperiodk shouldbemovedrightor left.Hence, twopositionsareanalyzedfirst. 1. Tooccupyoff-peakperiodsasmuchaspossible,asetofalreadyinserted jobs inperiodk should bemovedto therightmostside,andthen job icanbeprocessedacrossperiodskandk−1. 2. All inserted jobs inperiodk shouldbemovedleft so that job icanbeprocessedwithinperiodk. Notethatthemovementof jobsmayleadtoachangeintheirelectricitycosts,definedasmovement cost. The insertioncostof job i isequal to theelectricitycost forprocessing job iplus thecorresponding movementcost if somealreadyinserted jobsmustbemovedtoenlarge the idle timeofperiod(s). If the movementcost iszero, thenthe insertioncost isequal to theelectricitycost forprocessingthe job. Let cost1and cost2, respectively,denote the insertioncostsof theabovecorrespondingpositions. Since thepower consumption rate of job i is not higher thananyoneof the already inserted jobs, it followsthat cost1≤ cost2. That is, thePosition1 is theonlyone that shouldbeconsideredwhen job i is inserted intoperiodk.Next, letksmdenote theoff-peakperiodwithsubmaximalremaining idle time. Positions3and4aregivenas follows. 3. Suppose that job i isprocessedacrossperiodsksm,ksm+1,andksm+2. If Iksm is slightlysmaller than Ik, cost3maybe less than cost1asperiod ksm+1 is amid-peakperiod. Hence,Position3 needs tobeconsidered. 4. Similar toCondition3, job icanbeprocessedwithinamid-peakperiod. (a) Illustration of Scenario 1 (b) Illustration of Scenario 2 Figure6. IllustrationofCondition4. 8