Page - 1 - in Algorithms for Scheduling Problems

algorithms Article ANewGreedyInsertionHeuristicAlgorithmwitha Multi-StageFilteringMechanismforEnergy-Efficient SingleMachineSchedulingProblems HongliangZhang*,YoucaiFang,RuilinPanandChuanmingGe SchoolofManagementScienceandEngineering,AnhuiUniversityofTechnology,Ma’anshan243032,China; ahutfangyoucai@163.com(Y.F.); rlpan9@ahut.edu.cn(R.P.); 13083209689@163.com(C.G.) * Correspondence: zhanghongliang_17@126.com;Tel.:+86-555-231-5379 Received: 25December2017;Accepted: 6February2018;Published: 9February2018 Abstract: To improve energy efficiency andmaintain the stability of thepowergrid, time-of-use (TOU)electricity tariffshavebeenwidelyusedaroundtheworld,whichbringbothopportunitiesand challenges to theenergy-efficientschedulingproblems. Singlemachineschedulingproblemsunder TOUelectricity tariffsareofgreat significanceboth in theoryandpractice.Althoughmethodsbased ondiscrete-timeor continuous-timemodels havebeenput forward for addressing this problem, theyaredeficient in solutionqualityor timecomplexity, especiallywhendealingwith large-size instances. Toaddress large-scaleproblemsmoreefficiently,anewgreedyinsertionheuristicalgorithm withamulti-stagefilteringmechanismincludingcoarsegranularityandfinegranularityfiltering isdeveloped in this paper. Basedon the concentration anddiffusion strategy, the algorithmcan quickly filter outmany impossible positions in the coarse granularity filtering stage, and then, each jobcanfinditsoptimalposition inarelatively largespace in thefinegranularityfilteringstage. Toshowtheeffectivenessandcomputationalprocessof theproposedalgorithm,areal casestudy isprovided. Furthermore, twosetsofcontrastexperimentsareconducted,aimingtodemonstrate thegoodapplicationof thealgorithm.Theexperiments indicate that thesmall-size instancescanbe solvedwithin0.02susingouralgorithm,andtheaccuracy is further improved. For the large-size instances, thecomputationspeedofouralgorithmis improvedgreatlycomparedwith theclassic greedyinsertionheuristicalgorithm. Keywords: energy-conscious single machine scheduling; time-of-use electricity tariffs; greedy insertionheuristic; coarsegranularityandfinegranularityfilteringmechanism;concentrationand diffusionstrategy 1. Introduction Drivenbytherapiddevelopmentofglobaleconomyandcivilization, therewillbeaconsistent growth inenergyconsumption in theyearsahead.Accordingtoasurveyof the InternationalEnergy Agency(IEA), theworld-widedemandforenergywill increaseby37%by2040[1].Non-renewable energy resources such as coal, oil, and gas are diminishing day-by-day,which is threatening the sustainabledevelopmentofmanycountries.Meanwhile,greenhousegasemissionsgeneratedfrom inappropriate usage of fossil fuels have taken a heavy toll on the global climate as well as the atmospheric environment [2]. Therefore, how to save energy and then improve the environment qualityhasbecomeapressingmatterof themoment. As thebackboneofmany countries, the industrial sector consumes abouthalf of theworld’s totalenergyandemits themostgreenhousegases [3,4].Hence,energysaving inthe industrysector haspriority inpromotingsustainableeconomicdevelopment.Asweallknow,mostof theenergy is converted into the formofelectricity thatnumerous industrial sectorsuseas theirmainenergy[5,6]. Algorithms 2018,11, 18;doi:10.3390/a11020018 www.mdpi.com/journal/algorithms1