Page - 18 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 18 environments.Thus,accordingtoRule2,all the jobsdonothaveto traverseon-peakperiods,andthen CTH2 isgreatly reduced.Conversely,when e is setas1.2, thenumberofperiodsdecreasesandthe jobs arearrangedvery tightly. Therewill bemany jobs inserted into theperiodswithhigherelectricity prices. Therefore,ouralgorithmshouldfiltermorepositionswithlowerelectricitypricesandconstantly judgewhetherthejobneedstobemoved.Obviously,all theseoperationsmayincreasethecomputation time. Thus,whendealingwithlarge-size instancesandsetting e to1.2or1.5,ouralgorithmrunslonger, but thecomputationtimeisstill far less thanGIH2. 5.ConclusionsandProspects This paper develops a newgreedy insertion heuristic algorithmwith amulti-stage filtering mechanismforsinglemachineschedulingproblemsunderTOUelectricity tariffs. Thealgorithmcan quicklyfilteroutmany impossiblepositions in thecoarsegranularityfilteringstageand theneach jobtobe insertedcansearchfor itsoptimalposition inarelatively largespace in thefinegranularity filteringstage.Comparedwith theclassicgreedyinsertionalgorithm, thegreatestadvantageofour algorithm is that it no longer needs to traverse all non-full periods, so the time complexity of the algorithmisquite low,andit caneasilyaddress the large-scalesinglemachineschedulingproblems underTOUelectricity tariffs. The real case studydemonstrates thatwithour scheduling, the total electricitycostforprocessingallthepartscanbereducedby42.0%.Inaddition,twosetsofexperimental instancesareprovided. Thecomputational resultsdemonstrate that thesmall-size instancescanbe solvedwithin 0.02 s using our algorithm, and the accuracy of the algorithm is further improved. For the large-size instances,weaddtworules to theclassicgreedy insertionalgorithm,whichreduces the computation timewithout changing the calculation precision, but the results show that our algorithmstilloutperformsit. Specifically,whenaddressingthe large-scale instanceswith5000 jobs, thecomputationspeedofouralgorithmimprovesbynearly2700 times.Computationalexperiments alsoreveal that thesmaller theparameter e, themoresignificant thefilteringmechanismis. This paper focuses on the singlemachine scheduling problems under the first type of TOU electricity tariffs. In our future research,wewill continue to study theproblemunder the second typeofTOUtariffs (i.e., theoff-peakperiod liesbetweentwomid-peakperiods). Inaddition,wewill alsostrive to improveouralgorithmandextendit toothermachineenvironments, suchasparallel machinesandflowshop. Acknowledgments: This research is supportedby theNationalNatural Science FoundationofChina (Grant No.71772002). AuthorContributions:HongliangZhangcontributedtotheoverall idea,algorithm,andwritingofthemanuscript; YoucaiFangcodedthealgorithminMATLABandcontributedto thedetailedwriting;RuilinPancontributed to the ideas anddiscussionson the schedulingproblemunderTOUelectricity tariffs, aswell as the revision, preparation, andpublishingof thepaper; ChuanmingGeanalyzed the characteristics of the singlemachine schedulingproblemunderTOUelectricity tariffs.Allauthorshavereadandapprovedthefinalmanuscript. Conflictsof Interest:Theauthorsdeclarenoconflictof interest. References 1. InternationalEnergyAgency.WorldEnergyInvestmentOutlook; InternationalEnergyAgency(IEA):Paris, France,2015. 2. Li,C.;Tang,Y.;Cui,L.;Li,P.AquantitativeapproachtoanalyzecarbonemissionsofCNC-basedmachining systems. J. Intell.Manuf. 2015,26, 911–922. [CrossRef] 3. Jovane,F.;Yoshikawa,H.;Alting,L.;Boër,C.R.;Westkamper,E.;Williams,D.;Tseng,M.;Seliger,G.;Paci,A.M. Theincomingglobal technologicalandindustrial revolutiontowardscompetitivesustainablemanufacturing. CIRPAnn.Manuf. Technol. 2008,57, 641–659. [CrossRef] 4. Lu,C.;Gao,L.;Li,X.;Pan,Q.;Wang,Q.Energy-efficientpermutationflowshopschedulingproblemusinga hybridmulti-objectivebacktrackingsearchalgorithm. J.Clean. Prod. 2017,144, 228–238. [CrossRef] 18