Page - 6 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 18 periodorprocessedacrossasetofadjacentperiodsconsistingofanoff-peakperiod,amid-peakperiod, andanon-peakperiod.Obviously, theelectricitypricescorrespondingto thepositions in this layerare relativelyhigher than layer1. In layer3, thevastmajorityof the jobsareprocessedacrossapairof periodsconsistingofamid-peakperiodandanon-peakperiodorprocessedwithinanon-peakperiod. Theelectricitypricesof thepositionscorrespondingto3rd layerare thehighest. Then, all the jobsare sorted innon-increasingorderof their electricity consumptionratesand assigned to the layerwitha lowerprice successively toachieve thepreliminarycoarsegranularity filtering target. Once the layer towhicha jobbelongs isdetermined, thehuntingzoneofpossible positions of a job is concentrated in a certain layer. In thefine granularity filtering stage, several judgmentconditionsaresetuptodetermine thepositionofeach job tobe insertedusingcharacteristic polynomials based on considering processing time, electricity consumption rate of the job, and electricity price. What ismore, aiming tofind the optimal position, the hunting zone of possible positionsofa job isproperlyexpandedin thisstage. Assumingthata job, say job i,whoseprocessing timedoesnotexceedthedurationof theshortest on-peakperiod, is tobe inserted, the ideaof theproposedalgorithmisgivenas follows. Layer1 includesconditions1–2. If∃k∈A,ti≤maxk∈A{Ik}+ Ik+1, job i is assigned to layer1. Obviously, at thevery start, theoff-peakperiodsarepreferentiallyoccupiedby the jobswithhigh powerconsumptionrates, sinceall the jobsaresorted inadvance. Condition1:∃k∈A,ti≤ Ik. IfCondition1issatisfied, job icanbedirectlyprocessedwithinanoff-peakperiodwiththe lowest electricityprice. Note that each jobprocessedwithinaperiod isplaced to the leftmost sideof the period.AnillustrationisgiveninFigure3(i.e., job3 isa jobtobeinserted,and t3< I4). It isnoteworthy that thesmaller thenumberof the job, thegreater thepowerconsumptionrate. Figure3. IllustrationofCondition1. Condition2: ti>maxk∈A{Ik}>0anddk+1>0. WhenCondition2 issatisfied, itmeans that job icannotbeprocessedwithinanoff-peakperiod. As a second-best choice, job i can be processed across periods k and k + 1 in such a condition. Anillustration isgiven inFigure4.Note thatwhenthe job5 is inserted into theposition, it shouldbe adjacent to job2. Layer2 includesConditions3–5. If ti>maxk∈A{Ik}+ Ik+1 and∃k′ ∈B,ti≤ Ik′, job i isassigned to layer2. Condition3:maxk∈A{Ik}>0anddk+2>0. Since dk+2 > 0, it follows that period k+2 always exists. Tominimize the electricity cost for processing job i, theoff-peakperiodwithmaximal remaining idle time (period k) shouldbegiven 6