{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T02:11:02Z","timestamp":1740103862219,"version":"3.37.3"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2024,3,24]],"date-time":"2024-03-24T00:00:00Z","timestamp":1711238400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,3,24]],"date-time":"2024-03-24T00:00:00Z","timestamp":1711238400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003825","name":"Magyar Tudom\u00e1nyos Akad\u00e9mia","doi-asserted-by":"publisher","award":["LP2021-1\/2021"],"award-info":[{"award-number":["LP2021-1\/2021"]}],"id":[{"id":"10.13039\/501100003825","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100011019","name":"Nemzeti Kutat\u00e1si Fejleszt\u00e9si \u00e9s Innov\u00e1ci\u00f3s Hivatal","doi-asserted-by":"publisher","award":["FK128673"],"award-info":[{"award-number":["FK128673"]}],"id":[{"id":"10.13039\/501100011019","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100012550","name":"Nemzeti Kutat\u00e1si, Fejleszt\u00e9si \u00e9s Innovaci\u00f3s Alap","doi-asserted-by":"publisher","award":["2021-NKTA-62"],"award-info":[{"award-number":["2021-NKTA-62"]}],"id":[{"id":"10.13039\/501100012550","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2024,4]]},"abstract":"Abstract<\/jats:title>We consider single-machine scheduling with a non-renewable resource. In this setting, we are given a set of jobs, each characterized by a processing time, a weight, and a resource requirement. At fixed points in time, certain amounts of the resource are made available to be consumed by the jobs. The goal is to assign the jobs non-preemptively to time slots on the machine, so that each job has enough resource available at the start of its processing. The objective that we consider is the minimization of the sum of weighted completion times. The main contribution of the paper is a PTAS for the case of 0 processing times ($$1|rm=1,p_j=0|\\sum w_jC_j$$<\/jats:tex-math>\n \n \n 1<\/mml:mn>\n |<\/mml:mo>\n r<\/mml:mi>\n m<\/mml:mi>\n =<\/mml:mo>\n 1<\/mml:mn>\n ,<\/mml:mo>\n <\/mml:mrow>\n \n p<\/mml:mi>\n j<\/mml:mi>\n <\/mml:msub>\n \n =<\/mml:mo>\n 0<\/mml:mn>\n |<\/mml:mo>\n \u2211<\/mml:mo>\n <\/mml:mrow>\n \n w<\/mml:mi>\n j<\/mml:mi>\n <\/mml:msub>\n \n C<\/mml:mi>\n j<\/mml:mi>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>). In addition, we show strong NP-hardness of the case of unit resource requirements and weights ($$1|rm=1,a_j=1|\\sum C_j$$<\/jats:tex-math>\n \n \n 1<\/mml:mn>\n |<\/mml:mo>\n r<\/mml:mi>\n m<\/mml:mi>\n =<\/mml:mo>\n 1<\/mml:mn>\n ,<\/mml:mo>\n <\/mml:mrow>\n \n a<\/mml:mi>\n j<\/mml:mi>\n <\/mml:msub>\n \n =<\/mml:mo>\n 1<\/mml:mn>\n |<\/mml:mo>\n \u2211<\/mml:mo>\n <\/mml:mrow>\n \n C<\/mml:mi>\n j<\/mml:mi>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>), thus answering an open question of Gy\u00f6rgyi and Kis. We also prove that the schedule corresponding to the Shortest Processing Time First ordering provides a 3\/2-approximation for the latter problem. Finally, we investigate a variant of the problem where processing times are 0 and the resource arrival times are unknown. We present a $$(4+\\epsilon )$$<\/jats:tex-math>\n \n (<\/mml:mo>\n 4<\/mml:mn>\n +<\/mml:mo>\n \u03f5<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-approximation algorithm, together with a $$(4-\\varepsilon )$$<\/jats:tex-math>\n \n (<\/mml:mo>\n 4<\/mml:mn>\n -<\/mml:mo>\n \u03b5<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-inapproximability result, for any $$\\varepsilon >0$$<\/jats:tex-math>\n \n \u03b5<\/mml:mi>\n ><\/mml:mo>\n 0<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>","DOI":"10.1007\/s10951-024-00807-y","type":"journal-article","created":{"date-parts":[[2024,3,24]],"date-time":"2024-03-24T05:01:22Z","timestamp":1711256482000},"page":"151-164","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Scheduling with non-renewable resources: minimizing the sum of completion times"],"prefix":"10.1007","volume":"27","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0457-4573","authenticated-orcid":false,"given":"Krist\u00f3f","family":"B\u00e9rczi","sequence":"first","affiliation":[]},{"given":"Tam\u00e1s","family":"Kir\u00e1ly","sequence":"additional","affiliation":[]},{"given":"Simon","family":"Omlor","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,3,24]]},"reference":[{"key":"807_CR1","unstructured":"Carlier, J. (1984). Probl\u00e8mes d\u2019ordonnancement \u00e0 contraintes de ressources: algorithmes et complexit\u00e9. Institut de programmation: Universit\u00e9 Paris VI-Pierre et Marie Curie."},{"issue":"2","key":"807_CR2","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1016\/0167-6377(82)90045-1","volume":"1","author":"J Carlier","year":"1982","unstructured":"Carlier, J., & Kan, A. R. (1982). Scheduling subject to nonrenewable-resource constraints. Operations Research Letters, 1(2), 52\u201355.","journal-title":"Operations Research Letters"},{"issue":"1","key":"807_CR3","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. (2011). Single machine scheduling problems with financial resource constraints: Some complexity results and properties. Mathematical Social Sciences, 62(1), 7\u201313.","journal-title":"Mathematical Social Sciences"},{"key":"807_CR4","unstructured":"Garey, M. R., & Johnson, D. S. (1979). Computers and intractability. A guide to the theory of NP-completeness."},{"key":"807_CR5","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","volume":"5","author":"RL Graham","year":"1979","unstructured":"Graham, R. L., Lawler, E. L., Lenstra, J. K., & Kan, A. R. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 5, 287\u2013326.","journal-title":"Annals of Discrete Mathematics"},{"issue":"6","key":"807_CR6","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1002\/nav.20095","volume":"52","author":"A Grigoriev","year":"2005","unstructured":"Grigoriev, A., Holthuijsen, M., & Van De Klundert, J. (2005). Basic scheduling problems with raw material constraints. Naval Research Logistics (NRL), 52(6), 527\u2013535.","journal-title":"Naval Research Logistics (NRL)"},{"issue":"6","key":"807_CR7","doi-asserted-by":"publisher","first-page":"604","DOI":"10.1016\/j.orl.2017.09.007","volume":"45","author":"P Gy\u00f6rgyi","year":"2017","unstructured":"Gy\u00f6rgyi, P. (2017). A PTAS for a resource scheduling problem with arbitrary number of parallel machines. Operations Research Letters, 45(6), 604\u2013609.","journal-title":"Operations Research Letters"},{"issue":"2","key":"807_CR8","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. (2014). Approximation schemes for single machine scheduling with non-renewable resource constraints. Journal of Scheduling, 17(2), 135\u2013144.","journal-title":"Journal of Scheduling"},{"issue":"1","key":"807_CR9","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/s10479-015-1993-3","volume":"235","author":"P Gy\u00f6rgyi","year":"2015","unstructured":"Gy\u00f6rgyi, P., & Kis, T. (2015a). Approximability of scheduling problems with resource consuming jobs. Annals of Operations Research, 235(1), 319\u2013336.","journal-title":"Annals of Operations Research"},{"key":"807_CR10","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/j.tcs.2014.11.007","volume":"565","author":"P Gy\u00f6rgyi","year":"2015","unstructured":"Gy\u00f6rgyi, P., & Kis, T. (2015b). Reductions between scheduling problems with non-renewable resources and knapsack problems. Theoretical Computer Science, 565, 63\u201376.","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"807_CR11","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/j.ejor.2016.09.007","volume":"258","author":"P Gy\u00f6rgyi","year":"2017","unstructured":"Gy\u00f6rgyi, P., & Kis, T. (2017). Approximation schemes for parallel machine scheduling with non-renewable resources. European Journal of Operational Research, 258(1), 113\u2013123.","journal-title":"European Journal of Operational Research"},{"key":"807_CR12","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1016\/j.cie.2017.11.016","volume":"115","author":"P Gy\u00f6rgyi","year":"2018","unstructured":"Gy\u00f6rgyi, P., & Kis, T. (2018). Minimizing the maximum lateness on a single machine with raw material constraints by branch-and-cut. Computers & Industrial Engineering, 115, 220\u2013225.","journal-title":"Computers & Industrial Engineering"},{"issue":"6","key":"807_CR13","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1007\/s10951-019-00601-1","volume":"22","author":"P Gy\u00f6rgyi","year":"2019","unstructured":"Gy\u00f6rgyi, P., & Kis, T. (2019). Minimizing total weighted completion time on a single machine subject to non-renewable resource constraints. Journal of Scheduling, 22(6), 623\u2013634.","journal-title":"Journal of Scheduling"},{"key":"807_CR14","doi-asserted-by":"crossref","unstructured":"Gy\u00f6rgyi, P., & Kis, T. (2020). New complexity and approximability results for minimizing the total weighted completion time on a single machine subject to non-renewable resource constraints. arXiv preprint arXiv:2004.00972.","DOI":"10.1007\/s10951-019-00601-1"},{"issue":"6","key":"807_CR15","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1016\/j.orl.2015.09.004","volume":"43","author":"T Kis","year":"2015","unstructured":"Kis, T. (2015). Approximability of total weighted completion time with resource consuming jobs. Operations Research Letters, 43(6), 595\u2013598.","journal-title":"Operations Research Letters"},{"issue":"3","key":"807_CR16","doi-asserted-by":"publisher","first-page":"366","DOI":"10.1016\/0377-2217(84)90105-X","volume":"15","author":"R Slowi\u0144ski","year":"1984","unstructured":"Slowi\u0144ski, R. (1984). Preemptive scheduling of independent jobs on parallel machines subject to financial constraints. European Journal of Operational Research, 15(3), 366\u2013373.","journal-title":"European Journal of Operational Research"},{"issue":"9","key":"807_CR17","doi-asserted-by":"publisher","first-page":"811","DOI":"10.1057\/jors.1991.152","volume":"42","author":"A Toker","year":"1991","unstructured":"Toker, A., Kondakci, S., & Erkip, N. (1991). Scheduling under a non-renewable resource constraint. Journal of the Operational Research Society, 42(9), 811\u2013814.","journal-title":"Journal of the Operational Research Society"},{"issue":"1","key":"807_CR18","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/S0167-6377(97)00007-2","volume":"21","author":"J Xie","year":"1997","unstructured":"Xie, J. (1997). Polynomial algorithms for single machine scheduling problems with financial constraints. Operations Research Letters, 21(1), 39-42.","journal-title":"Operations Research Letters"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-024-00807-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10951-024-00807-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-024-00807-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,7]],"date-time":"2024-04-07T12:05:15Z","timestamp":1712491515000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10951-024-00807-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,24]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,4]]}},"alternative-id":["807"],"URL":"https:\/\/doi.org\/10.1007\/s10951-024-00807-y","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"type":"print","value":"1094-6136"},{"type":"electronic","value":"1099-1425"}],"subject":[],"published":{"date-parts":[[2024,3,24]]},"assertion":[{"value":"5 February 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 March 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}