{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T05:38:24Z","timestamp":1776749904088,"version":"3.51.2"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,2,11]],"date-time":"2026-02-11T00:00:00Z","timestamp":1770768000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,2,11]],"date-time":"2026-02-11T00:00:00Z","timestamp":1770768000000},"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":["J Sched"],"published-print":{"date-parts":[[2026,4]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    We consider a one-machine scheduling problem where the temperature of a job rises during processing and cools down when not being processed according to given linear heating and cooling rates. No job\u2019s temperature is allowed to rise above a given threshold, and no job\u2019s temperature can cool below 0. Another crucial property of our problem is that jobs can be preempted an arbitrary number of times, and even more, we allow that a job is processed for an infinitely small amount of time. We consider two objectives: minimize the makespan and minimize the sum of completion times. Our results are as follows. We show how to compactly represent a solution. Further, we prove that the problem of minimizing the sum of completion times can be solved in polynomial time by formulating it as a linear program and deriving a structural property. This result can be extended to hold for any number of machines. Further, we show that a minimum makespan can be found in\u00a0\n                    <jats:italic>O<\/jats:italic>\n                    (\n                    <jats:italic>n<\/jats:italic>\n                    ) time, even when heating and cooling rates are job-dependent.\n                  <\/jats:p>","DOI":"10.1007\/s10951-025-00870-z","type":"journal-article","created":{"date-parts":[[2026,2,11]],"date-time":"2026-02-11T11:32:57Z","timestamp":1770809577000},"page":"173-184","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Scheduling cool jobs when processing heats them"],"prefix":"10.1007","volume":"29","author":[{"given":"Roel","family":"Lambers","sequence":"first","affiliation":[]},{"given":"Rudi","family":"Pendavingh","sequence":"additional","affiliation":[]},{"given":"Frits C. R.","family":"Spieksma","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9654-8094","authenticated-orcid":false,"given":"C\u00e9line M. F.","family":"Swennenhuis","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2026,2,11]]},"reference":[{"key":"870_CR1","doi-asserted-by":"publisher","first-page":"761","DOI":"10.1287\/mnsc.1030.0207","volume":"50","author":"C Audet","year":"2004","unstructured":"Audet, C., Brimberg, J., Hansen, P., Le Digabel, S., & Mladenovi\u0107, N. (2004). Pooling Problem: Alternate Formulations and Solution Methods. Management Science, 50, 761\u2013776.","journal-title":"Management Science"},{"key":"870_CR2","doi-asserted-by":"publisher","unstructured":"Bai, D., Tang, L., & Su, M. (2008). A New Machine Scheduling Problem with Temperature Loss, International Workshop on Knowledge Discovery and Data Mining, pp. 662-666, https:\/\/doi.org\/10.1109\/WKDD.2008.36","DOI":"10.1109\/WKDD.2008.36"},{"key":"870_CR3","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1007\/s10951-013-0319-z","volume":"16","author":"E Bampis","year":"2013","unstructured":"Bampis, E., Letsios, D., Lucarelli, G., Markakis, E., & Milis, I. (2013). On multiprocessor temperature-aware scheduling problems. Journal of Scheduling, 16, 529\u2013538.","journal-title":"Journal of Scheduling"},{"key":"870_CR4","unstructured":"Bertsimas, D., & Kim, C.W. (2023). Optimal Control of Multiclass Fluid Queueing Networks: A Machine Learning Approach, https:\/\/arxiv.org\/abs\/2307.12405."},{"key":"870_CR5","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1016\/j.tcs.2012.02.003","volume":"508","author":"M Birks","year":"2013","unstructured":"Birks, M., & Fung, S. P. Y. (2013). Temperature aware online algorithms for scheduling equal length jobs. Theoretical Computer Science, 508, 54\u201365.","journal-title":"Theoretical Computer Science"},{"key":"870_CR6","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1016\/j.tcs.2016.10.022","volume":"661","author":"M Birks","year":"2017","unstructured":"Birks, M., & Fung, S. P. Y. (2017). Temperature aware online algorithms for minimizing flow time. Theoretical Computer Science, 661, 18\u201334.","journal-title":"Theoretical Computer Science"},{"key":"870_CR7","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/j.sorms.2011.01.001","volume":"16","author":"M Boon","year":"2011","unstructured":"Boon, M., van der Mei, R., & Winands, E. (2011). Applications of polling systems. Surveys in Operations Research and Management Science, 16, 67\u201382.","journal-title":"Surveys in Operations Research and Management Science"},{"key":"870_CR8","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1007\/s11750-018-0484-5","volume":"26","author":"S Borst","year":"2018","unstructured":"Borst, S., & Boxma, O. (2018). Polling: past, present, and perspective. TOP, 26, 335\u2013369.","journal-title":"TOP"},{"key":"870_CR9","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/j.suscom.2011.05.009","volume":"1","author":"M Chrobak","year":"2011","unstructured":"Chrobak, M., D\u00fcrr, C., Hurand, M., & Robert, J. (2011). Algorithms for temperature-aware task scheduling in microprocessor systems. Sustainable Computing-Informatics & Systems, 1, 241\u2013247.","journal-title":"Sustainable Computing-Informatics & Systems"},{"key":"870_CR10","doi-asserted-by":"publisher","first-page":"631","DOI":"10.1007\/s10898-016-0434-4","volume":"67","author":"A Gupte","year":"2017","unstructured":"Gupte, A., Ahmed, S., Dey, S., & Seok Cheon, M. (2017). Relaxations and discretizations for the pooling problem. Journal of Global Optimization, 67, 631\u2013669.","journal-title":"Journal of Global Optimization"},{"key":"870_CR11","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/s00291-002-0101-7","volume":"24","author":"J Kallrath","year":"2002","unstructured":"Kallrath, J. (2002). Planning and scheduling in the process industry. OR Spectrum, 24, 219\u2013250.","journal-title":"OR Spectrum"},{"key":"870_CR12","unstructured":"Kilic, O. (2011), Planning and scheduling in process industries considering industry-specific characteristics, PhD thesis of the University of Groningen, available at https:\/\/pure.rug.nl\/ws\/portalfiles\/portal\/2538168\/9complete.pdf."},{"key":"870_CR13","doi-asserted-by":"publisher","first-page":"2963","DOI":"10.1002\/j.1538-7305.1969.tb01200.x","volume":"48","author":"JB Kruskal","year":"1968","unstructured":"Kruskal, J. B. (1968). Work-Scheduling Algorithms: A Nonprobabilistic Queuing Study (with Possible Application to No. 1 ESS). The Bell System Technical Journal, 48, 2963\u20132974.","journal-title":"The Bell System Technical Journal"},{"key":"870_CR14","doi-asserted-by":"publisher","first-page":"524","DOI":"10.1016\/j.sysconle.2011.04.010","volume":"60","author":"E Lefeber","year":"2011","unstructured":"Lefeber, E., L\u00e4mmer, S., & Rooda, J. E. (2011). Optimal control of a deterministic multiclass queuing system for which several queues can be served simultaneously. Systems & Control Letters, 60, 524\u2013529.","journal-title":"Systems & Control Letters"},{"key":"870_CR15","doi-asserted-by":"crossref","unstructured":"Martinelli, F., & Valigi, P. (2002). The A scheduling problem for a finite buffer capacity pull-manufacturing system, In: Proceedings of the 37th IEEE Conference on Decision and Control, pp. 2171-2172.","DOI":"10.1109\/CDC.1998.758661"},{"key":"870_CR16","doi-asserted-by":"publisher","first-page":"1705","DOI":"10.1109\/TAC.2002.803540","volume":"47","author":"F Martinelli","year":"2002","unstructured":"Martinelli, F., & Valigi, P. (2002). The Impact of Finite Buffers on the Optimal Scheduling of a Single-Machine Two-Part-Type Manufacturing System. IEEE Transactions on Automatic Control, 47, 1705\u20131710.","journal-title":"IEEE Transactions on Automatic Control"},{"key":"870_CR17","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1111\/j.1934-6093.2004.tb00201.x","volume":"6","author":"F Martinelli","year":"2004","unstructured":"Martinelli, F., & Valigi, P. (2004). Dynamic scheduling for a single machine system under different setup and buffer capacity scenarios. Asian Journal on Control, 6, 229\u2013241.","journal-title":"Asian Journal on Control"},{"key":"870_CR18","doi-asserted-by":"publisher","first-page":"1055","DOI":"10.1007\/s10957-016-0923-0","volume":"171","author":"A Matveev","year":"2016","unstructured":"Matveev, A., Feoktistova, V., & Bolshakova, K. (2016). On Global Near Optimality of Special Periodic Protocols for Fluid Polling Systems with Setups. Journal on Optimization Theory and Applications, 171, 1055\u20131070.","journal-title":"Journal on Optimization Theory and Applications"},{"key":"870_CR19","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1111\/itor.12609","volume":"27","author":"T Pham","year":"2020","unstructured":"Pham, T., Leyman, P., & de Causmaecker, P. (2020). The intermittent travelling salesman problem. International Transactions in Operations Research, 27, 525\u2013548.","journal-title":"International Transactions in Operations Research"},{"key":"870_CR20","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1007\/3-540-46506-5_18","volume-title":"Performance Evaluation: Origins and Directions, LNCS 1769","author":"H Takagi","year":"2000","unstructured":"Takagi, H. (2000). Analysis and application of polling models. Performance Evaluation: Origins and Directions, LNCS 1769 (pp. 423\u2013442). Berlin: Springer."},{"key":"870_CR21","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1134\/S0005117906020019","volume":"67","author":"V Vishnevskii","year":"2006","unstructured":"Vishnevskii, V., & Semenova, O. (2006). Mathematical methods to study the polling systems. Automation and Remote Control, 67, 173\u2013220.","journal-title":"Automation and Remote Control"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-025-00870-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10951-025-00870-z","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-025-00870-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T04:51:16Z","timestamp":1776747076000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10951-025-00870-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,2,11]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,4]]}},"alternative-id":["870"],"URL":"https:\/\/doi.org\/10.1007\/s10951-025-00870-z","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"value":"1094-6136","type":"print"},{"value":"1099-1425","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,2,11]]},"assertion":[{"value":"14 December 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 December 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 February 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}