Page - 5 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 18 more thanoneperiod, itmustoccupyseveral continuousperiods.Constraint (6)ensures that if a job is processedacross threeperiods, themiddleperiodmustbe fullyoccupiedbythe job. Constraint (7) ensures that,atmost,one job isprocessedacrossanypairofadjacentperiods.Anillustrationto the MILPmodel isgivenbyanexampleofa2-jobsinglemachineschedulingproblemundera3-period TOUscheme,asshowninFigure1.Note thatmoredetailedexplanationsof the formulascanbeseen inCheetal. [9]. Figure1.Anexampleof themixed-integer linearprogramming(MILP)model. 3.AGreedyInsertionHeuristicAlgorithmwithMulti-StageFilteringMechanism 3.1. TheCharacteristics ofTOUElectricityTariffs InChina, theTOUelectricity tariffscanbemainlydividedinto twotypesaccordingto therelative positionof theoff-peakperiod: (1) theoff-peakperiod liesbetweenanon-peakperiodandamid-peak period; (2) the off-peakperiod lies between twomid-peakperiods. In addition, there is only one off-peakperiod inaday,andthedurationof theoff-peakperiod is longest. Thispaperwill investigate thesingle-machineschedulingproblemunder thefirst typeofTOUelectricity tariffs,whicharebeing implemented inmanyplaces inChina, suchasShanxi,Guangxi, and JiangxiProvinces andsoon. Next, letA,B,andΓ represent theoff-peak,mid-peak,andon-peakperiods, respectively. That is,A,B, Γ⊆M,A∪B∪Γ=M,A∩B=∅,A∩Γ=∅, andB∩Γ=∅.An illustration isgiven inFigure2. Accordingly,M={1,2, . . . , 10},A={5,10},B={1,3,6,8}, andΓ={2,4,7,9}. Figure2.Anillustrationof thefirst typeof time-of-use (TOU)electricity tariffs. 3.2.Multi-StageFilteringMechanismDesign Theproposedalgorithmisbuiltontheconcentrationanddiffusionstrategy. Firstly,all thepossible positionsaredividedintothreelayersbasedonthepriceofelectricity. Specifically, inlayer1,all the jobs areprocessedwithinanoff-peakperiodorprocessedacrossapairofperiodsconsistingofanoff-peak periodandamid-peakperiod. In layer2, thevastmajorityof the jobsareprocessedwithinamid-peak 5