Page - 11 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 18 Algorithm1:Greedyinsertionheuristicalgorithmwithmulti-stagefilteringmechanism 1. Sortall jobs innon-increasingorderof theirpowerconsumptionrates 2. Initialization: Ik=bk+1−bk, forall 1≤k≤m 3.For i=1tondo 3.1. If layer1 C1. IfCondition1 issatisfied Initial theperiod indexkk=argmink∈A(Ik≥ ti) //Job i isprocessedwithinperiodkk. C2.Else ifCondition2 issatisfied //Job i isprocessedacrossperiodskandk+1. 3.2.Else if layer2 C3. IfCondition3 issatisfied C3.1. If inequality (8) isnotsatisfied //Job i isprocessedacrossperiodsk,k+1,andk+2. C3.2.Else Initial theperiod indexkk′=argmink′∈B(Ik′ ≥ ti) //Job i isprocessedwithinperiodkk’. C4.Else ifCondition4 issatisfied C4.1. Ifdk+1=0 //Calculate cost1, cost3,and cost4andinsert job i into thepositionwithminimal insertioncost. C4.2.Else ifdk+2=0anddk+1>0 //Calculate cost1, cost2, cost3, cost4,and cost5andinsert job i into thepositionwithminimal insertioncost. C5.Else ifCondition5 issatisfied Initial theperiod indexkk′=argmink′∈B(Ik′ ≥ ti) //Job i isprocessedwithinperiodkk’. 3.3.Else if layer3 C6. IfCondition6 issatisfied //Similarly toCondition4, itneeds tocalculate the insertioncostof severalpossiblepositionsandinsert job i into thepositionwithminimal insertioncost. C7.Else ifCondition7 issatisfied C7.1. Ifmaxk′′∈Γ { Ik′′ } > ti Initial theperiod indexkk′′=argmink′′∈Γ ( Ik′′ ≥ ti ) //Job i isprocessedwithinperiodkk”. C7.2.Else //Job i traversesallnon-fullon-peakperiodsandinsert job i into thepositionwithminimal insertioncost. 4.ComputationalResults In thissection,areal-life instancefromamachinerymanufacturingcompanyinChinaisprovided to further illustrate theMILPmodel and the proposed algorithm. Then, two sets of contrasting experimentswithrandomlygenerated instancesareconducted,aimingtoshowthegoodperformance of the algorithm.The algorithm is coded inMATLABR2015b and the experiments are runon an Intel(R)Core(TM) i7-47903.60GHzprocessorwith16GBofmemoryunder theWindows7operating system. For benchmarking, the greedy insertionheuristic algorithmproposedbyChe et al. [9] is adoptedforourcontrast tests. TheTOUelectricity tariffsusedforall instancesare those implementedinShanxiProvince,China, asgiven inTable1. It canbeseenfromTable1 that theoff-peakperiod isbetweenanon-peakperiod andamid-peakperiod,whichmeans that the actual electricitypricesmeets thefirst typeofTOU electricity tariffs.Assumethat the timehorizonstartsat8:00a.m. of thefirstday. 11