Page - 2 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 18 Nevertheless, electricity ishardtostoreeffectively,andthus,mustbeproducedanddeliveredto its customersatonce [7]. Inaddition, theelectricitydemandisalwaysuneven,which leads toan increase ingeneratingcostowingto theutilizationofbackuppower facilitiesduringpeakhours [8]. Inorder tomaintainbalancebetweenelectricitysupplyanddemand,electricityprovidersusually implement demand-sidemanagementprograms[9],whichareanessential componentof realizingthegoalsofa smartgridandrationalizingtheallocationofpowerresources [10]. Oneof thedemand-sidemanagementprograms is time-of-use (TOU)electricity tariffs,which have beenwidely used around theworld.Usually, a commonTOU tariff scheme can bedivided into three typesofperiods: off-peak,mid-peak, andon-peakperiods.Thebasicnatureof theTOU schemeis that theretailpricessetbyelectricityprovidersvaryhourly throughout thedayaccordingto theamountofelectricitydemands;whenthere isan increase indemand, theelectricitycostgoesup correspondingly,andviceversa[11].ThepracticeofTOUelectricitytariffsnotonlyprovidessignificant opportunities for the industrial sector toenhanceenergyefficiency,butalsoavoidspowerrationing duringon-peakperiods,andimproves thestabilityof thepowergrid [7]. Using low-energyequipmentandimprovingtheefficiencyofproductionmanagementare two importantmethodstosaveenergy[12].Asawidelyusedproductionmanagementmethod,scheduling caneffectivelycontrol energyconsumption [13],whichbringsa lowercostofoperation. However, thestudiesaboutenergy-savingschedulingarestill limited[14].Overrecentyears,energy-efficient schedulingproblemshavegraduallyarousedtheattentionofscholars. Toachieve thegoalofenergy savingduringtheproductionprocess, someresearchershave investigatedtheproblemswithvarious energy-efficientmechanismstoreduceelectricitycostsbyminimizingoverall energyconsumption, suchasspeed-scaling[15–18]andpower-down[19–21],whileothershavestudiedtheproblemsfrom theperspectiveofTOUelectricity tariffs,whichhasbecomeafrontier issue in thisfield. AsforresearchingschedulingproblemsunderTOUelectricity tariffs, therehasbeenagrowing interest recently. Considering bothproduction and energy efficiency, Luo et al. [22] proposed an antcolonyoptimizationmeta-heuristicalgorithmforhybridflowshopschedulingproblemsunder TOUelectricity tariffs. Zhanget al. [12] studiedaflowshopschedulingproblemwithproduction throughputconstraints tominimizeelectricitycostandthecarbonfootprint simultaneously. Sharma etal. [23]presentedasocalled“econological scheduling”model foraspeed-scalingmulti-machine schedulingproblemaimedtominimize theelectricitycostandenvironmental impact.Moonetal. [24] examinedtheunrelatedparallelmachineschedulingproblemunderTOUelectricity tariffs tooptimize theweightedsumofmakespanandelectricitycost.Dingetal. [7]andCheetal. [25]addressedasimilar parallelmachineschedulingproblemunderTOUelectricity tariffs tominimize the totalelectricitycost. Theformerdevelopedatime-interval-basedmixed-integer linearprogramming(MILP)modelanda columngenerationheuristicalgorithm.The latter improvedthe formermodelbyprovidinga linear programmingrelaxationandatwo-stageheuristicalgorithm. Single machine scheduling problems are of great significance both in theory and practice. Ononehand, therearemanysinglemachineschedulingproblemsin thereal industrial environment. Forexample,aComputerNumericalControl (CNCforshort)planerhorizontalmillingandboring machinecanberegardedasasinglemachine.Ontheotherhand, theresearchresultsandmethodsof singlemachineschedulingproblemscanprovidereferenceforotherschedulingproblems,suchasflow shop, jobshop,andparallelmachineschedulingproblems.Forsinglemachineschedulingproblems underTOUelectricity tariffs,Wangetal. [26] investigatedasingle-machinebatchschedulingproblem tominimize themakespanandthe totalenergycosts simultaneously.Considering theTOUelectricity tariffsandthepower-downmechanism,Shroufetal. [27]proposedamodel thatenables theoperations managertodeterminethe“turningon”time,“turningoff”time,andidletimeatmachinelevel, leading toasignificant reduction inelectricitycostbyavoidingon-peakperiods.Gongetal. [28]developeda mixed integer linearprogrammingmodelandagenetic algorithmfor thesameproblem, reducing electricitycostandgreenhousegasemissionseffectivelyduringpeaktimeperiods.Withoutconsidering apower-downmechanism,Fangetal. [29] studiedthesinglemachineschedulingproblemunderTOU 2