{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T15:22:33Z","timestamp":1772119353209,"version":"3.50.1"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2025,7,10]],"date-time":"2025-07-10T00:00:00Z","timestamp":1752105600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,7,10]],"date-time":"2025-07-10T00:00:00Z","timestamp":1752105600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2025,10]]},"abstract":"Abstract<\/jats:title>\n \n Motivated by batteryless IoT devices, we consider the following scheduling problem. The input includes\n n<\/jats:italic>\n unit time jobs\n \n $$\\mathcal{J}= \\left\\{ J_1, \\ldots, J_n \\right\\} $$<\/jats:tex-math>\n <\/jats:inline-formula>\n , where each job\n \n $$J_i$$<\/jats:tex-math>\n <\/jats:inline-formula>\n has a release time\n \n $$r_i$$<\/jats:tex-math>\n <\/jats:inline-formula>\n , due date\n \n $$d_i$$<\/jats:tex-math>\n <\/jats:inline-formula>\n , energy requirement\n \n $$e_i$$<\/jats:tex-math>\n <\/jats:inline-formula>\n , and weight\n \n $$w_i$$<\/jats:tex-math>\n <\/jats:inline-formula>\n . We consider time to be slotted; hence, all time related job values refer to slots. Let\n \n $$T=\\max _i\\left\\{ d_i \\right\\} $$<\/jats:tex-math>\n <\/jats:inline-formula>\n . The input also includes an\n h<\/jats:italic>\n (\n t<\/jats:italic>\n ) value for every time slot\n t<\/jats:italic>\n \n $$\\left( 1 \\le t \\le T \\right) $$<\/jats:tex-math>\n <\/jats:inline-formula>\n , which is the energy harvestable on that slot. Energy is harvested at time slots when no job is executed. The objective is to find a feasible schedule that maximizes the weight of the scheduled jobs. A schedule is feasible if for every job\n \n $$J_j$$<\/jats:tex-math>\n <\/jats:inline-formula>\n in the schedule and its corresponding slot\n \n $$t_j$$<\/jats:tex-math>\n <\/jats:inline-formula>\n ,\n \n $$t_{j} \\ne t_{j'}$$<\/jats:tex-math>\n <\/jats:inline-formula>\n if\n \n $${j} \\ne {j'}$$<\/jats:tex-math>\n <\/jats:inline-formula>\n ,\n \n $$r_j \\le t_j \\le d_j$$<\/jats:tex-math>\n <\/jats:inline-formula>\n , and the available energy before\n \n $$t_j$$<\/jats:tex-math>\n <\/jats:inline-formula>\n is at least\n \n $$e_j$$<\/jats:tex-math>\n <\/jats:inline-formula>\n . To the best of our knowledge, we are the first to consider the theoretical aspects of this problem. In this work we show the following. (1) A polynomial time algorithm when all jobs have identical\n \n $$r_i, d_i$$<\/jats:tex-math>\n <\/jats:inline-formula>\n and\n \n $$w_i$$<\/jats:tex-math>\n <\/jats:inline-formula>\n . (2) A\n \n $$\\frac{1}{2}$$<\/jats:tex-math>\n <\/jats:inline-formula>\n -approximation algorithm when all jobs have identical\n \n $$w_i$$<\/jats:tex-math>\n <\/jats:inline-formula>\n but arbitrary\n \n $$r_i$$<\/jats:tex-math>\n <\/jats:inline-formula>\n and\n \n $$d_i$$<\/jats:tex-math>\n <\/jats:inline-formula>\n . (3) An FPTAS when all jobs have identical\n \n $$r_i$$<\/jats:tex-math>\n <\/jats:inline-formula>\n and\n \n $$d_i$$<\/jats:tex-math>\n <\/jats:inline-formula>\n but arbitrary\n \n $$w_i$$<\/jats:tex-math>\n <\/jats:inline-formula>\n . (4) Reductions showing that all the variants of the problem in which at least one of the attributes\n \n $$r_i$$<\/jats:tex-math>\n <\/jats:inline-formula>\n ,\n \n $$d_i$$<\/jats:tex-math>\n <\/jats:inline-formula>\n , or\n \n $$w_i$$<\/jats:tex-math>\n <\/jats:inline-formula>\n are not identical for all jobs are\n \n $$\\textsf{NP-Hard}$$<\/jats:tex-math>\n <\/jats:inline-formula>\n .\n <\/jats:p>","DOI":"10.1007\/s00453-025-01331-x","type":"journal-article","created":{"date-parts":[[2025,7,10]],"date-time":"2025-07-10T09:58:40Z","timestamp":1752141520000},"page":"1453-1473","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Interweaving Real-Time Jobs with Energy Harvesting to Maximize Throughput"],"prefix":"10.1007","volume":"87","author":[{"given":"Baruch","family":"Schieber","sequence":"first","affiliation":[]},{"given":"Bhargav","family":"Samineni","sequence":"additional","affiliation":[]},{"given":"Soroush","family":"Vahidi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,7,10]]},"reference":[{"key":"1331_CR1","doi-asserted-by":"crossref","unstructured":"Islam, B., Nirjon, S.: Scheduling computational and energy harvesting tasks in deadline-aware intermittent systems. In: 2020 IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), pp. 95\u2013109. IEEE (2020)","DOI":"10.1109\/RTAS48715.2020.00-14"},{"key":"1331_CR2","unstructured":"Boyer, S.A.: SCADA: Supervisory Control and Data Acquisition, 4th edn. International Society of Automation, Research Triangle Park (2010)"},{"key":"1331_CR3","doi-asserted-by":"publisher","DOI":"10.1088\/1742-6596\/1052\/1\/012005","volume":"1052","author":"E Bumker","year":"2018","unstructured":"Bumker, E., Schle, F., Woias, P.: Development of a batteryless VHF-beacon and tracker for mammals. J. Phys. Conf. Ser. 1052, 012005 (2018)","journal-title":"J. Phys. Conf. Ser."},{"issue":"3","key":"1331_CR4","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1109\/SURV.2011.060710.00094","volume":"13","author":"S Sudevalayam","year":"2010","unstructured":"Sudevalayam, S., Kulkarni, P.: Energy harvesting sensor nodes: survey and implications. IEEE Commun. Surv. Tutor. 13(3), 443\u2013461 (2010)","journal-title":"IEEE Commun. Surv. Tutor."},{"key":"1331_CR5","doi-asserted-by":"crossref","unstructured":"Merrett, G.V.: Invited: energy harvesting and transient computing: a paradigm shift for embedded systems? In: 53rd ACM\/EDAC\/IEEE Design Automation Conference (DAC), pp. 1\u20132 (2016)","DOI":"10.1145\/2897937.2905011"},{"key":"1331_CR6","doi-asserted-by":"publisher","unstructured":"Lucia, B., Balaji, V., Colin, A., Maeng, K., Ruppel, E.: Intermittent computing: challenges and opportunities. In: 2nd Summit on Advances in Programming Languages (SNAPL 2017), vol. 71, pp. 1\u201314 (2017). https:\/\/doi.org\/10.4230\/LIPIcs.SNAPL.2017.8","DOI":"10.4230\/LIPIcs.SNAPL.2017.8"},{"key":"1331_CR7","doi-asserted-by":"publisher","first-page":"1041","DOI":"10.1016\/j.rser.2015.11.010","volume":"55","author":"FK Shaikh","year":"2016","unstructured":"Shaikh, F.K., Zeadally, S.: Energy harvesting in wireless sensor networks: a comprehensive review. Renew. Sustain. Energy Rev. 55, 1041\u20131054 (2016)","journal-title":"Renew. Sustain. Energy Rev."},{"key":"1331_CR8","doi-asserted-by":"publisher","first-page":"772","DOI":"10.1016\/j.rser.2013.08.055","volume":"33","author":"A Yadav","year":"2014","unstructured":"Yadav, A., Chandel, S.: Solar radiation prediction using artificial neural network techniques: a review. Renew. Sustain. Energy Rev. 33, 772\u2013781 (2014). https:\/\/doi.org\/10.1016\/j.rser.2013.08.055","journal-title":"Renew. Sustain. Energy Rev."},{"key":"1331_CR9","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/s10951-013-0346-9","volume":"17","author":"P Gy\u00f6rgyi","year":"2014","unstructured":"Gy\u00f6rgyi, P., Kis, T.: Approximation schemes for single machine scheduling with non-renewable resource constraints. J. Sched. 17, 135\u2013144 (2014)","journal-title":"J. Sched."},{"issue":"1","key":"1331_CR10","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1016\/j.mathsocsci.2011.04.004","volume":"62","author":"ER Gafarov","year":"2011","unstructured":"Gafarov, E.R., Lazarev, A.A., Werner, F.: Single machine scheduling problems with financial resource constraints: some complexity results and properties. Math. Soc. Sci. 62(1), 7\u201313 (2011). https:\/\/doi.org\/10.1016\/j.mathsocsci.2011.04.004","journal-title":"Math. Soc. Sci."},{"issue":"6","key":"1331_CR11","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1002\/nav.20095","volume":"52","author":"A Grigoriev","year":"2005","unstructured":"Grigoriev, A., Holthuijsen, M., Klundert, J.: Basic scheduling problems with raw material constraints. Nav. Res. Logist. 52(6), 527\u2013535 (2005). https:\/\/doi.org\/10.1002\/nav.20095","journal-title":"Nav. Res. Logist."},{"issue":"3","key":"1331_CR12","doi-asserted-by":"publisher","first-page":"2234","DOI":"10.1109\/JIOT.2018.2828943","volume":"5","author":"A Caruso","year":"2018","unstructured":"Caruso, A., Chessa, S., Escolar, S., Toro, X., Lpez, J.C.: A dynamic programming algorithm for high-level task scheduling in energy harvesting IoT. IEEE Internet Things J. 5(3), 2234\u20132248 (2018)","journal-title":"IEEE Internet Things J."},{"key":"1331_CR13","unstructured":"Briskorn, D., Choi, B.-C., Lee, K., Leung, J., Pinedo, M.: Inventory constrained scheduling on a single machine. Manuskripte aus den Instituten fr Betriebswirtschaftslehre der Universitt Kiel 640, Christian-Albrechts-Universitt zu Kiel, Institut fr Betriebswirtschaftslehre (2008)"},{"issue":"2","key":"1331_CR14","doi-asserted-by":"publisher","first-page":"605","DOI":"10.1016\/j.ejor.2010.05.036","volume":"207","author":"D Briskorn","year":"2010","unstructured":"Briskorn, D., Choi, B.-C., Lee, K., Leung, J., Pinedo, M.: Complexity of single machine scheduling subject to nonnegative inventory constraints. Eur. J. Oper. Res. 207(2), 605\u2013619 (2010)","journal-title":"Eur. J. Oper. Res."},{"issue":"1","key":"1331_CR15","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/j.ejor.2020.03.029","volume":"286","author":"M Davari","year":"2020","unstructured":"Davari, M., Ranjbar, M., De Causmaecker, P., Leus, R.: Minimizing makespan on a single machine with release dates and inventory constraints. Eur. J. Oper. Res. 286(1), 115\u2013128 (2020). https:\/\/doi.org\/10.1016\/j.ejor.2020.03.029","journal-title":"Eur. J. Oper. Res."},{"issue":"6","key":"1331_CR16","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1002\/(SICI)1099-1425(199911\/12)2:6<245::AID-JOS28>3.0.CO;2-5","volume":"2","author":"P Baptiste","year":"1999","unstructured":"Baptiste, P.: Polynomial time algorithms for minimizing the weighted number of late jobs on a single machine with equal processing times. J. Sched. 2(6), 245\u2013252 (1999)","journal-title":"J. Sched."},{"key":"1331_CR17","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/j.tcs.2012.08.031","volume":"465","author":"N Vakhania","year":"2012","unstructured":"Vakhania, N.: Branch less, cut more and minimize the number of late equal-length jobs on identical machines. Theor. Comput. Sci. 465, 49\u201360 (2012)","journal-title":"Theor. Comput. Sci."},{"key":"1331_CR18","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1007\/s10951-010-0181-1","volume":"13","author":"JM Akker","year":"2010","unstructured":"Akker, J.M., Diepen, G., Hoogeveen, J.A.H.: Minimizing total weighted tardiness on a single machine with release dates and equal-length jobs. J. Sched. 13, 561\u2013576 (2010)","journal-title":"J. Sched."},{"key":"1331_CR19","doi-asserted-by":"publisher","DOI":"10.1016\/j.cie.2021.107209","volume":"159","author":"I Modos","year":"2021","unstructured":"Modos, I., Vcha, P., Hanzalek, Z.: On parallel dedicated machines scheduling under energy consumption limit. Comput. Ind. Eng. 159, 107209 (2021)","journal-title":"Comput. Ind. Eng."},{"key":"1331_CR20","doi-asserted-by":"publisher","DOI":"10.1016\/j.sysarc.2023.102938","volume":"142","author":"J Chen","year":"2023","unstructured":"Chen, J., Han, P., Zhang, Y., You, T., Zheng, P.: Scheduling energy consumption-constrained workflows in heterogeneous multi-processor embedded systems. J. Syst. Architect. 142, 102938 (2023). https:\/\/doi.org\/10.1016\/j.sysarc.2023.102938","journal-title":"J. Syst. Architect."},{"key":"1331_CR21","doi-asserted-by":"publisher","unstructured":"Di, M., Cui, J., Liu, L., Wang, Y.: Greedy sensor scheduling with energy constraint. In: 2023 8th International Conference on Communication, Image and Signal Processing (CCISP), pp. 48\u201352 (2023). https:\/\/doi.org\/10.1109\/CCISP59915.2023.10355867","DOI":"10.1109\/CCISP59915.2023.10355867"},{"key":"1331_CR22","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1145\/358841.358852","volume":"23","author":"J Vuillemin","year":"1980","unstructured":"Vuillemin, J.: A unifying look at data structures. Commun. ACM 23, 229\u2013239 (1980)","journal-title":"Commun. ACM"},{"key":"1331_CR23","doi-asserted-by":"crossref","unstructured":"P\u0103tra\u015fcu, M., Williams, R.: On the possibility of faster SAT algorithms. In: Proceedings of the Twenty-first Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1065\u20131075 (2010)","DOI":"10.1137\/1.9781611973075.86"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01331-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-025-01331-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01331-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,4]],"date-time":"2025-09-04T23:02:31Z","timestamp":1757026951000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-025-01331-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,10]]},"references-count":23,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2025,10]]}},"alternative-id":["1331"],"URL":"https:\/\/doi.org\/10.1007\/s00453-025-01331-x","relation":{"has-preprint":[{"id-type":"doi","id":"10.21203\/rs.3.rs-3054888\/v1","asserted-by":"object"}]},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,7,10]]},"assertion":[{"value":"12 June 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 June 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 July 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors attest that the research described in this paper followed the accepted principles of ethical and professional conduct.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical Approval"}}]}}