{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T04:19:51Z","timestamp":1772252391185,"version":"3.50.1"},"reference-count":16,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2017,10,28]],"date-time":"2017-10-28T00:00:00Z","timestamp":1509148800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1156475"],"award-info":[{"award-number":["1156475"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>This paper examines an important problem in smart grid energy scheduling; peaks in power demand are proportionally more expensive to generate and provision for. The issue is exacerbated in local microgrids that do not benefit from the aggregate smoothing experienced by large grids. Demand-side scheduling can reduce these peaks by taking advantage of the fact that there is often flexibility in job start times. We focus attention on the case where the jobs are non-preemptible, meaning once started, they run to completion. The associated optimization problem is called the peak demand minimization problem, and has been previously shown to be NP-hard. Our results include an optimal fixed-parameter tractable algorithm, a polynomial-time approximation algorithm, as well as an effective heuristic that can also be used in an online setting of the problem. Simulation results show that these methods can reduce peak demand by up to 50% versus on-demand scheduling for household power jobs.<\/jats:p>","DOI":"10.3390\/a10040122","type":"journal-article","created":{"date-parts":[[2017,10,30]],"date-time":"2017-10-30T12:16:23Z","timestamp":1509365783000},"page":"122","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Scheduling Non-Preemptible Jobs to Minimize Peak Demand"],"prefix":"10.3390","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6791-2691","authenticated-orcid":false,"given":"Sean","family":"Yaw","sequence":"first","affiliation":[{"name":"Los Alamos National Laboratoy, Los Alamos, NM 87545, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7151-2124","authenticated-orcid":false,"given":"Brendan","family":"Mumey","sequence":"additional","affiliation":[{"name":"Gianforte School of Computing, Montana State University, Bozeman, MT 59717,USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2017,10,28]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"1049","DOI":"10.1109\/JSAC.2012.120704","article-title":"Optimal control policies for power demand scheduling in the smart grid","volume":"30","author":"Koutsopoulos","year":"2012","journal-title":"IEEE J. Sel. Areas Commun."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1576","DOI":"10.1109\/TPWRD.2013.2257877","article-title":"Adaptive Energy Consumption Scheduling for Connected Microgrids Under Demand Uncertainty","volume":"28","author":"Fathi","year":"2013","journal-title":"IEEE Trans. Power Deliv."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/978-3-319-12691-3_1","article-title":"An Exact Algorithm for Non-preemptive Peak Demand Job Scheduling","volume":"Volume 8881","author":"Yaw","year":"2014","journal-title":"Combinatorial Optimization and Applications"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"1244","DOI":"10.1109\/TSG.2012.2195686","article-title":"Demand Side Management in Smart Grid Using Heuristic Optimization","volume":"3","author":"Logenthiran","year":"2012","journal-title":"IEEE Trans. Smart Grid"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"1403","DOI":"10.1109\/TSG.2014.2379618","article-title":"Social Networking Reduces Peak Power Consumption in Smart Grid","volume":"6","author":"Huang","year":"2015","journal-title":"IEEE Trans. Smart Grid"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Tang, S., Huang, Q., Li, X.Y., and Wu, D. (2013, January 14\u201319). Smoothing the energy consumption: Peak demand reduction in smart grid. Proceedings of the 2013 IEEE INFOCOM, Turin, Italy.","DOI":"10.1109\/INFCOM.2013.6566904"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Yaw, S., Mumey, B., Mcdonald, E., and Lemke, J. (2014, January 3\u20136). Peak demand scheduling in the Smart Grid. Proceedings of the 2014 IEEE International Conference on Smart Grid Communications (SmartGridComm), Venice, Italy.","DOI":"10.1109\/SmartGridComm.2014.7007741"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1109\/TSG.2015.2445491","article-title":"Residential demand response scheduling with multiclass appliances in the smart grid","volume":"7","author":"Roh","year":"2016","journal-title":"IEEE Trans. Smart Grid"},{"key":"ref_9","unstructured":"Chuzhoy, J., Guha, S., Khanna, S., and Naor, J. (2004, January 17\u201319). Machine minimization for scheduling jobs with interval constraints. Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, Rome, Italy."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/1-4020-8141-3_18","article-title":"Scheduling with release times and deadlines on a minimum number of machines","volume":"Volume 155","author":"Levy","year":"2004","journal-title":"Exploring New Frontiers of Theoretical Informatics"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1016\/j.ejor.2009.07.024","article-title":"New and improved level heuristics for the rectangular strip packing and variable-sized bin packing problems","volume":"203","author":"Ortmann","year":"2010","journal-title":"Eur. J. Oper. Res."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/s10878-005-5481-6","article-title":"Average-Case Performance Analysis of a 2D Strip Packing Algorithm\u2014NFDH","volume":"9","author":"Gu","year":"2005","journal-title":"J. Comb. Optim."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"508","DOI":"10.1137\/0212033","article-title":"Shelf algorithms for two-dimensional packing problems","volume":"12","author":"Baker","year":"1983","journal-title":"SIAM J. Comput."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/BF02579324","article-title":"Randomized Rounding: A Technique for Provably Good Algorithms and Algorithmic Proofs","volume":"7","author":"Raghavan","year":"1987","journal-title":"Combinatorica"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Raghavan, P. (1986, January 27\u201329). Probabilistic construction of deterministic algorithms: Approximating packing integer programs. Proceedings of the 27th Annual Symposium on Foundations of Computer Science, Toronto, ON, Canada.","DOI":"10.1109\/SFCS.1986.45"},{"key":"ref_16","unstructured":"Kolter, J.Z., and Johnson, M.J. (2011, January 21). Redd: A public data set for energy disaggregation research. Proceedings of the SustKDD Workshop on Data Mining Applications in Sustainability, San Diego, CA, USA."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/10\/4\/122\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T18:48:45Z","timestamp":1760208525000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/10\/4\/122"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,10,28]]},"references-count":16,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2017,12]]}},"alternative-id":["a10040122"],"URL":"https:\/\/doi.org\/10.3390\/a10040122","relation":{"has-preprint":[{"id-type":"doi","id":"10.20944\/preprints201709.0108.v1","asserted-by":"object"}]},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,10,28]]}}}