{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T14:00:35Z","timestamp":1778853635269,"version":"3.51.4"},"reference-count":29,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2018,2,9]],"date-time":"2018-02-09T00:00:00Z","timestamp":1518134400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["71772002"],"award-info":[{"award-number":["71772002"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>To improve energy efficiency and maintain the stability of the power grid, time-of-use (TOU) electricity tariffs have been widely used around the world, which bring both opportunities and challenges to the energy-efficient scheduling problems. Single machine scheduling problems under TOU electricity tariffs are of great significance both in theory and practice. Although methods based on discrete-time or continuous-time models have been put forward for addressing this problem, they are deficient in solution quality or time complexity, especially when dealing with large-size instances. To address large-scale problems more efficiently, a new greedy insertion heuristic algorithm with a multi-stage filtering mechanism including coarse granularity and fine granularity filtering is developed in this paper. Based on the concentration and diffusion strategy, the algorithm can quickly filter out many impossible positions in the coarse granularity filtering stage, and then, each job can find its optimal position in a relatively large space in the fine granularity filtering stage. To show the effectiveness and computational process of the proposed algorithm, a real case study is provided. Furthermore, two sets of contrast experiments are conducted, aiming to demonstrate the good application of the algorithm. The experiments indicate that the small-size instances can be solved within 0.02 s using our algorithm, and the accuracy is further improved. For the large-size instances, the computation speed of our algorithm is improved greatly compared with the classic greedy insertion heuristic algorithm.<\/jats:p>","DOI":"10.3390\/a11020018","type":"journal-article","created":{"date-parts":[[2018,2,9]],"date-time":"2018-02-09T12:46:27Z","timestamp":1518180387000},"page":"18","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":16,"title":["A New Greedy Insertion Heuristic Algorithm with a Multi-Stage Filtering Mechanism for Energy-Efficient Single Machine Scheduling Problems"],"prefix":"10.3390","volume":"11","author":[{"given":"Hongliang","family":"Zhang","sequence":"first","affiliation":[{"name":"School of Management Science and Engineering, Anhui University of Technology, Ma\u2019anshan 243032, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Youcai","family":"Fang","sequence":"additional","affiliation":[{"name":"School of Management Science and Engineering, Anhui University of Technology, Ma\u2019anshan 243032, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ruilin","family":"Pan","sequence":"additional","affiliation":[{"name":"School of Management Science and Engineering, Anhui University of Technology, Ma\u2019anshan 243032, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chuanming","family":"Ge","sequence":"additional","affiliation":[{"name":"School of Management Science and Engineering, Anhui University of Technology, Ma\u2019anshan 243032, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2018,2,9]]},"reference":[{"key":"ref_1","unstructured":"International Energy Agency (2015). World Energy Investment Outlook, International Energy Agency (IEA)."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"911","DOI":"10.1007\/s10845-013-0812-4","article-title":"A quantitative approach to analyze carbon emissions of CNC-based machining systems","volume":"26","author":"Li","year":"2015","journal-title":"J. Intell. Manuf."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"641","DOI":"10.1016\/j.cirp.2008.09.010","article-title":"The incoming global technological and industrial revolution towards competitive sustainable manufacturing","volume":"57","author":"Jovane","year":"2008","journal-title":"CIRP Ann. Manuf. Technol."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1016\/j.jclepro.2017.01.011","article-title":"Energy-efficient permutation flow shop scheduling problem using a hybrid multi-objective backtracking search algorithm","volume":"144","author":"Lu","year":"2017","journal-title":"J. Clean. Prod."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1109\/TASE.2012.2216876","article-title":"Opportunity estimation for real-time energy control of sustainable manufacturing systems","volume":"10","author":"Sun","year":"2013","journal-title":"IEEE Trans. Autom. Sci. Eng."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/s12541-009-0107-z","article-title":"Energy consumption reduction technology in manufacturing\u2014A selective review of policies, standards, and research","volume":"10","author":"Park","year":"2009","journal-title":"Int. J. Precis. Eng. Manuf."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1138","DOI":"10.1109\/TASE.2015.2495328","article-title":"Parallel machine scheduling under time-of-use electricity prices: New models and optimization approaches","volume":"13","author":"Ding","year":"2016","journal-title":"IEEE Trans. Autom. Sci. Eng."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/j.compchemeng.2014.05.024","article-title":"Scheduling and energy\u2014Industrial challenges and opportunities","volume":"72","author":"Merkert","year":"2015","journal-title":"Comput. Chem. Eng."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"565","DOI":"10.1016\/j.jclepro.2016.03.150","article-title":"An efficient greedy insertion heuristic for energy-conscious single machine scheduling problem under time-of-use electricity tariffs","volume":"129","author":"Che","year":"2016","journal-title":"J. Clean. Prod."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Longe, O., Ouahada, K., Rimer, S., Harutyunyan, A., and Ferreira, H. (2017). Distributed demand side management with battery storage for smart home energy scheduling. Sustainability, 9.","DOI":"10.3390\/su9010120"},{"key":"ref_11","first-page":"497","article-title":"Rethinking reform of electricity markets","volume":"40","author":"Shapiro","year":"2005","journal-title":"Wake For. Law Rev."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/j.cirp.2014.03.011","article-title":"Energy-conscious flow shop scheduling under time-of-use electricity tariffs","volume":"63","author":"Zhang","year":"2014","journal-title":"CIRP Ann. Manuf. Technol."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1016\/j.cor.2017.04.004","article-title":"Energy-efficient bi-objective single-machine scheduling with power-down mechanism","volume":"85","author":"Che","year":"2017","journal-title":"Comput. Oper. Res."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"He, F., Shen, K., Guan, L., and Jiang, M. (2017). Research on energy-saving scheduling of a forging stock charging furnace based on an improved SPEA2 algorithm. Sustainability, 9.","DOI":"10.3390\/su9112154"},{"key":"ref_15","unstructured":"Erlebach, T., and Persiano, G. (2005, January 6\u20137). Speed scaling of tasks with precedence constraints. Proceedings of the 3rd International Workshop on Approximation and Online Algorithms, Palma de Mallorca, Spain."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"234","DOI":"10.1016\/j.jmsy.2011.08.004","article-title":"A new approach to scheduling in manufacturing for power consumption and carbon footprint reduction","volume":"30","author":"Fang","year":"2011","journal-title":"J. Manuf. Syst."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"418","DOI":"10.1016\/j.rcim.2013.04.001","article-title":"Energy-efficient scheduling for a flexible flow shop using an improved genetic-simulated annealing algorithm","volume":"29","author":"Dai","year":"2013","journal-title":"Robot. Comput. Integr. Manuf."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1080\/00207543.2013.825740","article-title":"Reduction of power consumption and carbon footprints by applying multi-objective optimisation via genetic algorithms","volume":"52","author":"Liu","year":"2014","journal-title":"Int. J. Prod. Res."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"4247","DOI":"10.1080\/00207540701450013","article-title":"Operational methods for minimization of energy consumption of manufacturing equipment","volume":"45","author":"Mouzon","year":"2007","journal-title":"Int. J. Prod. Res."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1080\/19397030802257236","article-title":"A framework to minimise total energy consumption and total tardiness on a single machine","volume":"1","author":"Mouzon","year":"2008","journal-title":"Int. J. Sustain. Eng."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"318","DOI":"10.1016\/j.jclepro.2014.07.025","article-title":"Sustainable performance oriented operational decision-making of single machine systems with deterministic product arrival time","volume":"85","author":"Liu","year":"2014","journal-title":"J. Clean. Prod."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1016\/j.ijpe.2013.01.028","article-title":"Hybrid flow shop scheduling considering machine electricity consumption cost","volume":"146","author":"Luo","year":"2013","journal-title":"Int. J. Prod. Econ."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1016\/j.jclepro.2015.06.002","article-title":"Econological scheduling of a manufacturing enterprise operating under a time-of-use electricity tariff","volume":"108","author":"Sharma","year":"2015","journal-title":"J. Clean. Prod."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"523","DOI":"10.1007\/s00170-013-4749-8","article-title":"Optimization of production scheduling with time-dependent and machine-dependent electricity cost for industrial energy efficiency","volume":"68","author":"Moon","year":"2013","journal-title":"Int. J. Adv. Manuf. Technol."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"688","DOI":"10.1016\/j.jclepro.2017.04.018","article-title":"Energy-conscious unrelated parallel machine scheduling under time-of-use electricity tariffs","volume":"156","author":"Che","year":"2017","journal-title":"J. Clean. Prod."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"1205","DOI":"10.1016\/j.jclepro.2016.07.206","article-title":"Bi-objective optimization of a single machine batch scheduling problem with energy cost consideration","volume":"137","author":"Wang","year":"2016","journal-title":"J. Clean. Prod."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/j.jclepro.2013.12.024","article-title":"Optimizing the production scheduling of a single machine to minimize total energy consumption costs","volume":"67","author":"Shrouf","year":"2014","journal-title":"J. Clean. Prod."},{"key":"ref_28","unstructured":"Kara, S. (2015, January 7\u20139). An energy-cost-aware scheduling methodology for sustainable manufacturing. Proceedings of the 22nd CIRP Conference on Life Cycle Engineering (LCE) Univ New S Wales, Sydney, Australia."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1007\/s10479-015-2003-5","article-title":"Scheduling on a single machine under time-of-use electricity tariffs","volume":"238","author":"Fang","year":"2016","journal-title":"Ann. Oper. Res."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/2\/18\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T14:54:25Z","timestamp":1760194465000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/2\/18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,2,9]]},"references-count":29,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2018,2]]}},"alternative-id":["a11020018"],"URL":"https:\/\/doi.org\/10.3390\/a11020018","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,2,9]]}}}