Seite - 3 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 18 electricitytariffssystematicallytominimizethetotalelectricitycosts. Theydividedtheproblemintothe twocasesofuniform-speedandspeed-scalable, inwhichapreemptiveversionandanon-preemptive versionwere investigatedrespectively. For theuniform-speedcasewithnon-preemptiveassumption (ProblemU-pyr), theydemonstratedthat theproblemisstronglynon-deterministicpolynomial-time hard(NP-Hard).Note that theProblemU-pyr is thesameasourproblem.BasedonFangetal. [29], Che et al. [9] investigated a continuous-time MILP model for Problem U-pyr and developed a greedy insertion heuristic algorithm(GIH) that is themost classicmethod for this problemuntil now,accordingtoourbestknowledge. In theiralgorithm, the jobsare inserted intoavailableperiods with lowerelectricityprices insequence,andthe jobswithhigherpowerconsumptionratesaremostly assigned to periodswith lower electricity prices by traversing all non-full “forward blocks” and “backwardblocks”. However,Fangetal. [29]didnotestablishacompletemathematicalmodel for thesinglemachine schedulingproblem(ProblemU-pyr)underTOUelectricity tariffs, andtheiralgorithmisonly feasible in the condition that all the jobs have the sameworkload and the TOU tariffs follow a so-called pyramidal structure. Regrettably, the TOU electricity tariffs rarely follow a complete pyramidal structure inmostprovinces inChina. Toperfect the theoryofFangetal. [29],Cheetal. [9]developed anewmodelandalgorithm,but theiralgorithmrequires thatall the jobsmust traverseallnon-full “forwardblocks”and“backwardblocks”, causingastronghigh-timecomplexity. Especiallywhen theprocessingtimesof the jobsarerelativelyshort, itusually takesseveral jobs tofilloneperiodand generatesuneven remaining idle times,which leads to an increase in thenumber of forwardand backwardblocksrequiredtobecalculated. Inaddition, thegenerationprocessof“forward(backward) block” is limitedto the jobmovements thatdonot incuradditionalelectricitycost,whichmaycause some jobs tomiss theoptimumpositions. Thus, by focusing on the jobs with short processing times, this paper proposes a more efficient greedy insertion algorithmwith amulti-stage filteringmechanism (GIH-F) based on the continuous-timeMILPmodel toaddress these issues. Theproposedalgorithmmainlyconsistsof two stages: coarsegranularityfilteringandfinegranularityfiltering. In thecoarsegranularityfiltering stage,all thepossiblepositionsarefirstdivided into three levels (i.e., three layers)according to the priceofelectricity, correspondingtohigh-price,medium-price,andlow-price layers. Then,all the jobs aresorted innon-increasingorderof theirelectricityconsumptionratesandassignedto the layerwith a lowerpricesuccessively. Basedontheconcentrationanddiffusionstrategy,once the layer towhicha jobbelongs isdetermined, thehuntingzoneofpossiblepositionsofa job isconcentrated inacertain layer. Tofindtheoptimalposition, the job tobe insertedcansearch for itsposition inarelatively large space in theselected layer. Then,consideringprocessingtimes,electricityconsumptionratesof the jobsandelectricityprices, theelectricitycostwithrespect toeachpossiblepositioncanbecompared usingcharacteristicpolynomials. Basedonthese, several judgmentconditionscanbesetupinfora finegranularityfilteringstage todetermine thepositionofeach jobtobe inserted. To summarize, the proposed algorithmcanfilter out impossible layers, and then judge each conditionthatbelongs to theselected layersuccessively.Once thecondition is satisfied, the job is just inserted into thecorrespondingposition. Throughcoarsegranularityfilteringandfinegranularity filtering,ouralgorithmdoesnothavetotraverseallpossiblepositions,whichleadstoagreatreduction in the timecomplexity.Arealcasestudyandtwosetsof randomlygenerated instancesareusedto test theperformanceof theproposedalgorithminthispaper. Therestofthispaperisorganizedasfollows. Section2presentsadescriptionofthesinglemachine schedulingproblemunderTOUelectricity tariffs. InSection3,anefficientGIH-F isdeveloped.Next, a real casestudyandtwosetsofexperimental testsareprovidedinSection4. Finally, theconclusions andprospectsarepresented inSection5. 3