Page - 7 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 18 priority, comparedwithotheroff-peak,mid-peak,andon-peakperiods. Thus, job i ispreferredtobe processedacrossperiodsk,k+1,andk+2.Meanwhile, thecorrespondingelectricitycost isnamed as cost1. However, if job i isprocessedwithinamid-peakperiod (i.e., thecorrespondingelectricity cost isnamedas cost2), theelectricitycostmaybe lower.Hence, twopositionsareconsideredandan illustration isgiven inFigure5. Let cA, cB, and cΓ represent theelectricitypricesofoff-peak,mid-peak, andon-peakperiods, respectively. Toselect theoptimalposition, thekeyproperty1 isgivenas follows. Figure4. IllustrationofCondition2. Figure5. IllustrationofCondition3. Property1. IfCondition3 is satisfiedandxi,k×(cB−cA)< xi,k+2×(cΓ−cB)holds, thebest choice for job i is tobeprocessedwithinamid-peakperiod. Proof. cost1= pi×(xi,k×cA+xi,k+1×cB+xi,k+2×cΓ)and cost2= pi× ti×cB. It is assumedthat cost1> cost2, that is, cost1− cost2= pi× (xi,k×cA+xi,k+1×cB+xi,k+2×cΓ)− pi× ti× cB > 0. Since ti=xi,k+xi,k+1+xi,k+2, it followsthat: xi,k×(cB−cA)< xi,k+2×(cΓ−cB). (8) Therefore,wheninequality (8)holds, job icanbedirectlyprocessedwithinamid-peakperiod. Otherwise, job imustbeprocessedacrossperiodsk,k+1,andk+2. Thisends theproof. Condition4:maxk∈A{Ik}>0anddk+2=0. 7