{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,1]],"date-time":"2025-04-01T06:24:35Z","timestamp":1743488675944,"version":"3.37.3"},"reference-count":51,"publisher":"Springer Science and Business Media LLC","issue":"12","license":[{"start":{"date-parts":[[2020,6,18]],"date-time":"2020-06-18T00:00:00Z","timestamp":1592438400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,6,18]],"date-time":"2020-06-18T00:00:00Z","timestamp":1592438400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000836","name":"University of Liverpool","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000836","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000836","name":"University of Liverpool","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000836","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005057","name":"National Tsing Hua University","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100005057","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,12]]},"DOI":"10.1007\/s00453-020-00733-3","type":"journal-article","created":{"date-parts":[[2020,6,18]],"date-time":"2020-06-18T08:02:41Z","timestamp":1592467361000},"page":"3415-3457","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Non-preemptive Scheduling in a Smart Grid Model and Its Implications on Machine Minimization"],"prefix":"10.1007","volume":"82","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6073-8179","authenticated-orcid":false,"given":"Fu-Hong","family":"Liu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hsiang-Hsuan","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Prudence W. H.","family":"Wong","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,6,18]]},"reference":[{"key":"733_CR1","doi-asserted-by":"crossref","unstructured":"Alamdari, S., Biedl, T., Chan, T.M., Grant, E., Jampani, K.R., Keshav, S., Lubiw, A., Pathak, V.: Smart-grid electricity allocation via strip packing with slicing. In: WADS, pp. 25\u201336. Springer (2013)","DOI":"10.1007\/978-3-642-40104-6_3"},{"issue":"5","key":"733_CR2","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1145\/1735223.1735245","volume":"53","author":"S Albers","year":"2010","unstructured":"Albers, S.: Energy-efficient algorithms. Commun. ACM 53(5), 86\u201396 (2010)","journal-title":"Commun. ACM"},{"key":"733_CR3","doi-asserted-by":"crossref","unstructured":"Azar, Y.: On-line load balancing. In: Online Algorithms, pp. 178\u2013195. Springer (1998)","DOI":"10.1007\/BFb0029569"},{"issue":"1","key":"733_CR4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1206035.1206038","volume":"54","author":"N Bansal","year":"2007","unstructured":"Bansal, N., Kimbrel, T., Pruhs, K.: Speed scaling to manage energy and temperature. J. ACM 54(1), 1\u201339 (2007)","journal-title":"J. ACM"},{"issue":"4","key":"733_CR5","doi-asserted-by":"crossref","first-page":"739","DOI":"10.1007\/s10878-013-9618-8","volume":"29","author":"PC Bell","year":"2015","unstructured":"Bell, P.C., Wong, P.W.H.: Multiprocessor speed scaling for jobs with arbitrary sizes and deadlines. J. Comb. Optim. 29(4), 739\u2013749 (2015)","journal-title":"J. Comb. Optim."},{"issue":"6","key":"733_CR6","doi-asserted-by":"crossref","first-page":"687","DOI":"10.1007\/s10951-015-0447-8","volume":"19","author":"M Burcea","year":"2016","unstructured":"Burcea, M., Hon, W., Liu, H., Wong, P.W.H., Yau, D.K.Y.: Scheduling for electricity cost in a smart grid. J. Sched. 19(6), 687\u2013699 (2016)","journal-title":"J. Sched."},{"key":"733_CR7","doi-asserted-by":"crossref","unstructured":"Caron, S., Kesidis, G.: Incentive-based energy consumption scheduling algorithms for the smart grid. In: SmartGridComm, pp. 391\u2013396. IEEE (2010)","DOI":"10.1109\/SMARTGRID.2010.5622073"},{"key":"733_CR8","doi-asserted-by":"publisher","unstructured":"Chau, V., Feng, S., Thang, N.K.: Competitive algorithms for demand response management in smart grid. In: M.A. Bender, M.\u00a0Farach-Colton, M.A. Mosteiro (eds.) LATIN 2018: Theoretical Informatics - 13th Latin American Symposium, Buenos Aires, Argentina, April 16-19, 2018, Proceedings, Lecture Notes in Computer Science, vol. 10807, pp. 303\u2013316. Springer (2018). https:\/\/doi.org\/10.1007\/978-3-319-77404-6_23","DOI":"10.1007\/978-3-319-77404-6_23"},{"issue":"1","key":"733_CR9","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1109\/TSG.2012.2224388","volume":"4","author":"C Chen","year":"2013","unstructured":"Chen, C., Nagananda, K.G., Xiong, G., Kishore, S., Snyder, L.V.: A communication-based appliance scheduling scheme for consumer-premise energy management systems. IEEE Trans. Smart Grid 4(1), 56\u201365 (2013)","journal-title":"IEEE Trans. Smart Grid"},{"key":"733_CR10","doi-asserted-by":"crossref","unstructured":"Chen, L., Megow, N., Schewior, K.: An $${O}(\\log m)$$-competitive algorithm for online machine minimization. In: SODA, pp. 155\u2013163. ACM (2016)","DOI":"10.1137\/1.9781611974331.ch12"},{"key":"733_CR11","unstructured":"Chuzhoy, J., Guha, S., Khanna, S., Naor, J.S.: Machine minimization for scheduling jobs with interval constraints. In: FOCS, pp. 81\u201390. IEEE (2004)"},{"key":"733_CR12","doi-asserted-by":"crossref","unstructured":"Cieliebak, M., Erlebach, T., Hennecke, F., Weber, B., Widmayer, P.: Scheduling with release times and deadlines on a minimum number of machines. In: IFIP TCS, pp. 209\u2013222. Springer (2004)","DOI":"10.1007\/1-4020-8141-3_18"},{"key":"733_CR13","unstructured":"Djurovi\u0107, M.\u017d., Mila\u010di\u0107, A., Kr\u0161ulja, M.: A simplified model of quadratic cost function for thermal generators. In: DAAAM, pp. 25\u201328. DA (2012)"},{"key":"733_CR14","unstructured":"European Commission: Europen smartgrids technology platform. ftp:\/\/ftp.cordis.europa.eu\/pub\/fp7\/energy\/docs\/smartgrids_en.pdf (2006)"},{"issue":"1\u20132","key":"733_CR15","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1007\/s10479-015-2003-5","volume":"238","author":"K Fang","year":"2016","unstructured":"Fang, K., Uhan, N.A., Zhao, F., Sutherland, J.W.: Scheduling on a single machine under time-of-use electricity tariffs. Ann. OR 238(1\u20132), 199\u2013227 (2016)","journal-title":"Ann. OR"},{"issue":"4","key":"733_CR16","doi-asserted-by":"crossref","first-page":"944","DOI":"10.1109\/SURV.2011.101911.00087","volume":"14","author":"X Fang","year":"2012","unstructured":"Fang, X., Misra, S., Xue, G., Yang, D.: Smart grid: the new and improved power grid\u2014a survey. IEEE Commun. Surv. Tutor. 14(4), 944\u2013980 (2012)","journal-title":"IEEE Commun. Surv. Tutor."},{"issue":"1","key":"733_CR17","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1109\/MPE.2009.934876","volume":"8","author":"H Farhangi","year":"2010","unstructured":"Farhangi, H.: The path of the smart grid. IEEE Power Energy Mag. 8(1), 18\u201328 (2010)","journal-title":"IEEE Power Energy Mag."},{"key":"733_CR18","doi-asserted-by":"crossref","unstructured":"Feng, X., Xu, Y., Zheng, F.: Online scheduling for electricity cost in smart grid. In: COCOA, pp. 783\u2013793. Springer (2015)","DOI":"10.1007\/978-3-319-26626-8_58"},{"issue":"3","key":"733_CR19","doi-asserted-by":"crossref","first-page":"835","DOI":"10.2140\/pjm.1965.15.835","volume":"15","author":"D Fulkerson","year":"1965","unstructured":"Fulkerson, D., Gross, O.: Incidence matrices and interval graphs. Pac. J. Math. 15(3), 835\u2013855 (1965)","journal-title":"Pac. J. Math."},{"issue":"3","key":"733_CR20","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1007\/BF02579236","volume":"2","author":"R Halin","year":"1982","unstructured":"Halin, R.: Some remarks on interval graphs. Combinatorica 2(3), 297\u2013304 (1982)","journal-title":"Combinatorica"},{"issue":"3","key":"733_CR21","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1109\/MPE.2010.936352","volume":"8","author":"K Hamilton","year":"2010","unstructured":"Hamilton, K., Gulhar, N.: Taking demand response to the next level. IEEE Power Energy Mag. 8(3), 60\u201365 (2010)","journal-title":"IEEE Power Energy Mag."},{"issue":"2","key":"733_CR22","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1109\/MPE.2008.931384","volume":"7","author":"A Ipakchi","year":"2009","unstructured":"Ipakchi, A., Albuyeh, F.: Grid of the future. IEEE Power Energy Mag. 7(2), 52\u201362 (2009)","journal-title":"IEEE Power Energy Mag."},{"issue":"1","key":"733_CR23","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1137\/140952636","volume":"30","author":"K Jansen","year":"2016","unstructured":"Jansen, K., Land, F., Land, K.: Bounding the running time of algorithms for scheduling and packing problems. SIAM J. Discrete Math. 30(1), 343\u2013366 (2016)","journal-title":"SIAM J. Discrete Math."},{"key":"733_CR24","doi-asserted-by":"crossref","unstructured":"Kannberg, L., Chassin, D., DeSteese, J., Hauser, S., Kintner-Meyer, M., (U.S.), P.N.N.L., of\u00a0Energy, U.S.D.: GridWise: The Benefits of a Transformed Energy System. Pacific Northwest National Laboratory (2003)","DOI":"10.2172\/15010370"},{"key":"733_CR25","doi-asserted-by":"crossref","unstructured":"Karbasioun, M.M., Shaikhet, G., Kranakis, E., Lambadaris, I.: Power strip packing of malleable demands in smart grid. In: ICC, pp. 4261\u20134265. IEEE (2013)","DOI":"10.1109\/ICC.2013.6655233"},{"key":"733_CR26","doi-asserted-by":"crossref","unstructured":"Koutsopoulos, I., Tassiulas, L.: Control and optimization meet the smart power grid: Scheduling of power demands for optimal energy management. In: e-Energy, pp. 41\u201350. ACM (2011)","DOI":"10.1145\/2318716.2318723"},{"issue":"2","key":"733_CR27","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1109\/MPE.2007.915179","volume":"6","author":"R Krishnan","year":"2008","unstructured":"Krishnan, R.: Meters of tomorrow [in my view]. IEEE Power Energy Mag. 6(2), 94\u201396 (2008)","journal-title":"IEEE Power Energy Mag."},{"key":"733_CR28","doi-asserted-by":"crossref","unstructured":"Li, H., Qiu, R.C.: Need-based communication for smart grid: When to inquire power price? In: GLOBECOM, pp. 1\u20135. IEEE (2010)","DOI":"10.1109\/GLOCOM.2010.5683173"},{"issue":"1","key":"733_CR29","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1109\/TSG.2012.2223242","volume":"4","author":"Z Li","year":"2013","unstructured":"Li, Z., Liang, Q.: Performance analysis of multiuser selection scheme in dynamic home area networks for smart grid communications. IEEE Trans. Smart Grid 4(1), 13\u201320 (2013)","journal-title":"IEEE Trans. Smart Grid"},{"key":"733_CR30","unstructured":"Liu, F., Liu, H., Wong, P.W.H.: Optimal nonpreemptive scheduling in a smart grid model. In: ISAAC, pp. 53:1\u201353:13. LIPIcs (2016)"},{"issue":"10","key":"733_CR31","doi-asserted-by":"crossref","first-page":"1009","DOI":"10.1002\/ett.2625","volume":"25","author":"A Llaria","year":"2014","unstructured":"Llaria, A., Jim\u00e9nez, J., Curea, O.: Study on communication technologies for the optimal operation of smart grids. Trans. Emerg. Telecommun. Technol. 25(10), 1009\u20131019 (2014)","journal-title":"Trans. Emerg. Telecommun. Technol."},{"key":"733_CR32","unstructured":"Lockheed Martin: SEELoad\u2122 Solution. http:\/\/www.lockheedmartin.co.uk\/us\/products\/energy-solutions\/seesuite\/seeload.html"},{"issue":"3","key":"733_CR33","doi-asserted-by":"crossref","first-page":"1244","DOI":"10.1109\/TSG.2012.2195686","volume":"3","author":"T Logenthiran","year":"2012","unstructured":"Logenthiran, T., Srinivasan, D., Shun, T.Z.: Demand side management in smart grid using heuristic optimization. IEEE Trans. Smart Grid 3(3), 1244\u20131252 (2012)","journal-title":"IEEE Trans. Smart Grid"},{"issue":"3","key":"733_CR34","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1109\/MPE.2010.936353","volume":"8","author":"T Lui","year":"2010","unstructured":"Lui, T., Stirling, W., Marcy, H.: Get smart. IEEE Power Energy Mag. 8(3), 66\u201378 (2010)","journal-title":"IEEE Power Energy Mag."},{"issue":"1","key":"733_CR35","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1109\/TSG.2012.2223243","volume":"4","author":"CYT Ma","year":"2013","unstructured":"Ma, C.Y.T., Yau, D.K.Y., Rao, N.S.V.: Scalable solutions of markov games for smart-grid infrastructure protection. IEEE Trans. Smart Grid 4(1), 47\u201355 (2013)","journal-title":"IEEE Trans. Smart Grid"},{"issue":"1","key":"733_CR36","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1109\/TSG.2012.2223766","volume":"4","author":"S Maharjan","year":"2013","unstructured":"Maharjan, S., Zhu, Q., Zhang, Y., Gjessing, S., Basar, T.: Dependable demand response management in the smart grid: a stackelberg game approach. IEEE Trans. Smart Grid 4(1), 120\u2013132 (2013)","journal-title":"IEEE Trans. Smart Grid"},{"key":"733_CR37","volume-title":"Renewable and efficient electric power systems","author":"GM Masters","year":"2013","unstructured":"Masters, G.M.: Renewable and efficient electric power systems. Wiley, Hoboken (2013)"},{"key":"733_CR38","doi-asserted-by":"crossref","unstructured":"Mohsenian-Rad, A.H., Wong, V., Jatskevich, J., Schober, R.: Optimal and autonomous incentive-based energy consumption scheduling algorithm for smart grid. In: ISGT, pp. 1\u20136. IEEE (2010)","DOI":"10.1109\/ISGT.2010.5434752"},{"issue":"3","key":"733_CR39","doi-asserted-by":"crossref","first-page":"320","DOI":"10.1109\/TSG.2010.2089069","volume":"1","author":"AH Mohsenian-Rad","year":"2010","unstructured":"Mohsenian-Rad, A.H., Wong, V.W., Jatskevich, J., Schober, R., Leon-Garcia, A.: Autonomous demand-side management based on game-theoretic energy consumption scheduling for the future smart grid. IEEE Trans. Smart Grid 1(3), 320\u2013331 (2010)","journal-title":"IEEE Trans. Smart Grid"},{"key":"733_CR40","unstructured":"REGEN Energy Inc: ENVIROGRID\u2122 SMART GRID BUNDLE. http:\/\/www.regenenergy.com\/press\/announcing-the-envirogrid-smart-grid-bundle\/"},{"key":"733_CR41","unstructured":"Saha, B.: Renting a cloud. In: FSTTCS, pp. 437\u2013448. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik (2013)"},{"issue":"1","key":"733_CR42","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1109\/TSG.2012.2214068","volume":"4","author":"S Salinas","year":"2013","unstructured":"Salinas, S., Li, M., Li, P.: Multi-objective optimal energy consumption scheduling in smart grids. IEEE Trans. Smart Grid 4(1), 341\u2013348 (2013)","journal-title":"IEEE Trans. Smart Grid"},{"key":"733_CR43","doi-asserted-by":"crossref","unstructured":"Samadi, P., Mohsenian-Rad, A.H., Schober, R., Wong, V.W., Jatskevich, J.: Optimal real-time pricing algorithm based on utility maximization for smart grid. In: SmartGridComm, pp. 415\u2013420. IEEE (2010)","DOI":"10.1109\/SMARTGRID.2010.5622077"},{"key":"733_CR44","doi-asserted-by":"crossref","unstructured":"Tang, S., Huang, Q., Li, X.Y., Wu, D.: Smoothing the energy consumption: Peak demand reduction in smart grid. In: INFOCOM, pp. 1133\u20131141. IEEE (2013)","DOI":"10.1109\/INFCOM.2013.6566904"},{"key":"733_CR45","unstructured":"Toronto Hydro Corporation: Peaksaver Program. http:\/\/www.peaksaver.com\/peaksaver_THESL.html"},{"key":"733_CR46","unstructured":"UK Department of Energy & Climate Change: Smart grid: A more energy-efficient electricity supply for the UK. https:\/\/www.gov.uk\/smart-grid-a-more-energy-efficient-electricity-supply-for-the-uk (2013)"},{"key":"733_CR47","unstructured":"US Department of Energy: The Smart Grid: An Introduction. http:\/\/www.oe.energy.gov\/SmartGridIntroduction.htm (2009)"},{"key":"733_CR48","unstructured":"Yao, F., Demers, A., Shenker, S.: A scheduling model for reduced CPU energy. In: FOCS, pp. 374\u2013382. IEEE (1995)"},{"key":"733_CR49","doi-asserted-by":"crossref","unstructured":"Yaw, S., Mumey, B.: An exact algorithm for non-preemptive peak demand job scheduling. In: COCOA, pp. 3\u201312. Springer (2014)","DOI":"10.1007\/978-3-319-12691-3_1"},{"key":"733_CR50","doi-asserted-by":"crossref","unstructured":"Yaw, S., Mumey, B., McDonald, E., Lemke, J.: Peak demand scheduling in the smart grid. In: SmartGridComm, pp. 770\u2013775. IEEE (2014)","DOI":"10.1109\/SmartGridComm.2014.7007741"},{"key":"733_CR51","unstructured":"Zpryme Research & Consulting: Power systems of the future: The case for energy storage, distributed generation, and microgrids. http:\/\/smartgrid.ieee.org\/images\/features\/smart_grid_survey.pdf (2012)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00733-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-020-00733-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00733-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,7]],"date-time":"2024-08-07T22:25:43Z","timestamp":1723069543000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-020-00733-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,18]]},"references-count":51,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["733"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00733-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2020,6,18]]},"assertion":[{"value":"5 August 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 June 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 June 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}