Page - 9 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 18 Toensure that cost1= pi×(xi,k×cA+xixi,k−1×cΓ)alwaysholds,Property2 isgivenfirst. Property2.WhenCondition4 is satisfiedanddk+1=0, job i canbedirectly inserted intoPosition1without movinganyalready inserted jobs inperiodk−1. Proof. Since∃k∈A, Ik>0, theremustbeno jobsprocessedwithinperiodk−1. It isonlypossible that a job, say job j, j< i, is processedacrossperiods k− 2and k− 1. Therefore,xj,k−2maybe the valueof themaximal remaining idle timeofallmid-peakperiodsbefore inserting job j. Since∃k′ ∈B, ti≤ Ik’ and j< i, it is understandable that ti ≤ Ik′ ≤ xj,k−2.Now, job i is to be inserted, it follows that ti+xj,k−1≤ xj,k−2+xj,k−1= tj.Asmentionedearlier, theprocessingtimesofall the jobsdonot exceedthedurationof theshorteston-peakperiod, that is, tj≤dk−1.Hence, ti+xj,k−1≤dk−1. If job i isprocessedacrossperiodskandk−1, thenxi,k−1+xj,k−1≤ xi,k−1+xi,k+xj,k−1= ti+xj,k−1≤ dk+1. That is, xi,k−1+xj,k−1 ≤ dk−1. Thus, dk−1−xj,k−1−xi,k−1 = Ik−1 ≥ 0. This suggestswhen job i is inserted intoPosition1,periodk−1cannotbe full.Hence, job icanbedirectly inserted intoPosition1 withoutmovinganyalreadyinserted jobs inperiodk−1.Note that thispropertyapplies toScenario2 aswell. AccordingtoProperty2,cost1 = pi× (xi,k×cA+xi,k−1×cΓ) isalwayssatisfied. Inthefollowing part, three formulas forcalculatingthe insertioncostsofPositions1,3,and4aregiven. cost1 = pi× (xi,k×cA+xi,k−1×cΓ); (9) cost3 = pi× (xi,ksm×cA+xi,ksm+1×cB+xi,ksm+2×cΓ); (10) cost4 = pi× ti×cB. (11) Since cost1 isalways less than cost2, there isnoneedtocompute cost2. Eventually, the insertion costsofall thepossiblepositions that job icanbe inserted intocanbeeasilyanddirectlycalculatedby theaboveformulas,andthenthepositionwithminimuminsertioncostwillbechosen. Scenario2: It canbeseenfromFigure6bthat thePositions1,4,and5 inScenario2are thesame as thePositions1,3,and4 inScenario1. TheonlydifferencebetweenScenarios1and2 iswhetherdk+1 >0ornot (i.e.,periodk+1exists). Sinceperiodk+1isamid-peakperiod, twoadditionalpositions needtobeconsidered incomparisonwithScenario1. 1. Aset of already inserted jobs inperiod karemoved to the rightmost sideof theperiod k+1, andthen job i isprocessedacrossperiodskandk−1. 2. Asetofalready inserted jobs inperiodk shouldbemovedto the leftuntil job icanbeprocessed acrossperiodskandk+1. Thesizeof the twoinsertioncosts (i.e., theprocessingelectricitycostof job6plus themovement costsof jobs3,4, and5)correspondingtoPositions2and3 isuncertain,because theelectricitycost forprocessing job i isgreateratPosition2 thanatPosition3,while themovementcostsare just the opposite. Eventually, it shouldcalculate insertioncostsoffivepossiblepositions,andthenchoose the positionwithminimumcost. Condition5:∀k∈A, Ik=0. WhenCondition5 is satisfied, thismeansall theoff-peakperiodsare full and job icanbedirectly processedwithinamid-peakperiod. Layer 3 includesConditions 6 and7. Most of the jobs areprocessed across apair of periods consistingof amid-peakperiodandanon-peakperiodorprocessedwithin anon-peakperiod in this layer. Condition6: ti>maxk′∈B{Ik′}>0. 9