{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,8]],"date-time":"2026-07-08T10:22:44Z","timestamp":1783506164275,"version":"3.55.0"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"1-3","license":[{"start":{"date-parts":[[2026,5,21]],"date-time":"2026-05-21T00:00:00Z","timestamp":1779321600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,5,21]],"date-time":"2026-05-21T00:00:00Z","timestamp":1779321600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100015763","name":"University of Szeged","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100015763","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[2026,7]]},"abstract":"Abstract<\/jats:title>\n \n In the considered coupled task problem (CTP) we have to schedule\n n<\/jats:italic>\n jobs on a single machine, each consisting of two tasks with exact time delay between them, while the objective is to minimize the total completion time of the jobs. We analyze a greedy type algorithm \u2013 called\n SDF<\/jats:italic>\n (Shortest Delay First) \u2013 from worst case point of view, and we give bounds for the asymptotic behavior of SDF for the special case where each task has equal length processing time\n p<\/jats:italic>\n . For this case, the best-known upper bound on the asymptotic performance ratio of algorithm SDF is\n \n \n $$\\frac{5}{3}\\approx 1.666\\ldots .$$<\/jats:tex-math>\n \n \n \n 5<\/mml:mn>\n 3<\/mml:mn>\n <\/mml:mfrac>\n \u2248<\/mml:mo>\n 1.666<\/mml:mn>\n \u2026<\/mml:mo>\n .<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n We improve this bound to a general upper bound\n \n \n $$\\frac{21p-\\sqrt{3(43p^2-28p+4)}-6}{6p}$$<\/jats:tex-math>\n \n \n \n 21<\/mml:mn>\n p<\/mml:mi>\n -<\/mml:mo>\n \n \n 3<\/mml:mn>\n (<\/mml:mo>\n 43<\/mml:mn>\n \n p<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n -<\/mml:mo>\n 28<\/mml:mn>\n p<\/mml:mi>\n +<\/mml:mo>\n 4<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msqrt>\n -<\/mml:mo>\n 6<\/mml:mn>\n <\/mml:mrow>\n \n 6<\/mml:mn>\n p<\/mml:mi>\n <\/mml:mrow>\n <\/mml:mfrac>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n that holds for all\n \n \n $$p\\ge 2.$$<\/jats:tex-math>\n \n \n p<\/mml:mi>\n \u2265<\/mml:mo>\n 2<\/mml:mn>\n .<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n Using constructions to compute lower bounds, we give narrow intervals for the asymptotic behavior of algorithm SDF as a function of the parameter\n p<\/jats:italic>\n .\n <\/jats:p>","DOI":"10.1007\/s10479-026-07261-3","type":"journal-article","created":{"date-parts":[[2026,5,21]],"date-time":"2026-05-21T02:56:51Z","timestamp":1779332211000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A coupled task scheduling approximation algorithm for minimizing the sum of completion times"],"prefix":"10.1007","volume":"362","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3820-9777","authenticated-orcid":false,"given":"J\u00f3zsef","family":"B\u00e9k\u00e9si","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gy\u00f6rgy","family":"D\u00f3sa","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"G\u00e1bor","family":"Galambos","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,5,21]]},"reference":[{"issue":"4","key":"7261_CR1","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1016\/j.orl.2006.09.006","volume":"35","author":"AA Ageev","year":"2007","unstructured":"Ageev, A. A., & Baburin, A. E. (2007). Approximation algorithms for UET scheduling problems with exact delays. Operations Research Letters, 35(4), 533\u2013540. https:\/\/doi.org\/10.1016\/j.orl.2006.09.006","journal-title":"Operations Research Letters"},{"key":"7261_CR2","doi-asserted-by":"publisher","unstructured":"Ageev, A.A., & Ivanov, M. (2016). Approximating coupled-task scheduling problems with equal exact delays. Kochetov, Y., Khachay, M., Beresnev, V., Nurminski, E., Pardalos, P. (eds.) DOOR 2016. LNCS, vol. 9869, (pp 259\u2013271), Springer, Cham. https:\/\/doi.org\/10.1007\/978-3-319-44914-2 21.","DOI":"10.1007\/978-3-319-44914-2"},{"key":"7261_CR3","doi-asserted-by":"publisher","unstructured":"Ageev, A.A. & Kononov, A.V. (2007). Approximation algorithms for scheduling problems with exact delays. Erlebach, T., Kaklamanis, C. (eds.) WAOA 2006. LNCS, vol. 4368, (pp 1\u201314), Springer, Heidelberg. https:\/\/doi.org\/10.1007\/11970125 1.","DOI":"10.1007\/11970125"},{"issue":"2","key":"7261_CR4","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/s00186-014-0469-6","volume":"59","author":"D Ahr","year":"2004","unstructured":"Ahr, D., B\u00e9k\u00e9si, J., Galambos, G., Oswald, M., & Reinelt, G. (2004). An exact algorithm for scheduling identical coupled tasks. Mathematical Methods of Operations Research, 59(2), 193\u2013203. https:\/\/doi.org\/10.1007\/s00186-014-0469-6","journal-title":"Mathematical Methods of Operations Research"},{"issue":"5","key":"7261_CR5","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1016\/j.dam.2009.10.012","volume":"158","author":"P Baptiste","year":"2010","unstructured":"Baptiste, P. (2010). A note on scheduling identical coupled tasks in logarithmic time. Discrete Applied Mathematics, 158(5), 583\u2013587. https:\/\/doi.org\/10.1016\/j.dam.2009.10.012","journal-title":"Discrete Applied Mathematics"},{"key":"7261_CR6","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/j.orl.2008.11.002","volume":"37","author":"J Bekesi","year":"2009","unstructured":"Bekesi, J., Galambos, G., Oswald, M., & Reinelt, G. (2009). Improved analysis of an algorithm for the coupled of task problem with UET jobs. Operations Research Letters, 37, 93\u201396. https:\/\/doi.org\/10.1016\/j.orl.2008.11.002","journal-title":"Operations Research Letters"},{"key":"7261_CR7","doi-asserted-by":"publisher","unstructured":"Bekesi, J., Dosa, G. & Galambos, G.(2022). A first fit type algorithm for tha coupled of task scheduling problem with unit execution time and two exact delays EJOR297(3) 844-852. https:\/\/doi.org\/10.1016\/j.ejor.2021.06.002","DOI":"10.1016\/j.ejor.2021.06.002"},{"key":"7261_CR8","unstructured":"Bekesi, J., Dosa, G. & Galambos, G.(2023). Improvements on some CFP approximation results, Journal of Scheduling submitted for publication."},{"key":"7261_CR9","unstructured":"Bekesi, J., Dosa, G. & Galambos, G.(2023). Tight Approximation Ratio of a Greedy-type Algorithm for Coupled Task Scheduling Problem with Unit Length Jobs, European Journal of Operations Research submitted for publication."},{"issue":"3","key":"7261_CR10","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1590\/S0104-65002001000200004","volume":"7","author":"J Blazewicz","year":"2001","unstructured":"Blazewicz, J., Ecker, K., Kis, T., & Tanas, M. (2001). A Note on the Complexity of Scheduling Coupled Task on a Single Processor. Journal of the Brazilian Computer Society, 7(3), 23\u201326. https:\/\/doi.org\/10.1590\/S0104-65002001000200004","journal-title":"Journal of the Brazilian Computer Society"},{"issue":"2","key":"7261_CR11","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/j.orl.2006.09.006","volume":"24","author":"B Chen","year":"2021","unstructured":"Chen, B., & Zhang, X. (2021). Scheduling of Coupled Tasks with Exact Delays for Minimum Total Job Completion Time. Journal of Scheduling, 24(2), 209\u2013221. https:\/\/doi.org\/10.1016\/j.orl.2006.09.006","journal-title":"Journal of Scheduling"},{"issue":"1","key":"7261_CR12","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1002\/nav.10103","volume":"51","author":"M Elshafei","year":"2004","unstructured":"Elshafei, M., Sherali, M., & Smith, J. C. (2004). Radar pulse interleaving for multi-target tracking. Naval Research Logistic, 51(1), 72\u201394. https:\/\/doi.org\/10.1002\/nav.10103","journal-title":"Naval Research Logistic"},{"issue":"4","key":"7261_CR13","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1049\/ip-f-1.1980.0046","volume":"127","author":"A Farina","year":"1980","unstructured":"Farina, A., & Neri, P. (1980). Multitarget interleaved tracking for phased-array radar, IEE Proceedings F (Communications. Radar and Signal Processing, 127(4), 312\u2013318. https:\/\/doi.org\/10.1049\/ip-f-1.1980.0046","journal-title":"Radar and Signal Processing"},{"key":"7261_CR14","doi-asserted-by":"publisher","unstructured":"Fischer, D., & Gyorgyi, P. (2023). Approximation algorithms for coupled task scheduling minimizing the sum of completion times. Annals of Operations Research,1\u201322,. https:\/\/doi.org\/10.1007\/s10479-023-05322-5","DOI":"10.1007\/s10479-023-05322-5"},{"key":"7261_CR15","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., & Rinnooy Kan, A. H. G. (1979). Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey. Annals of Discrete Mathematics, 5, 287\u2013326. https:\/\/doi.org\/10.1016\/S0167-5060(08)70356-X","journal-title":"Annals of Discrete Mathematics"},{"key":"7261_CR16","doi-asserted-by":"publisher","unstructured":"Izquierdo-Fuente, A. & Casar-Corredera, J.R. (1994), Optimal radar pulse scheduling using a neural network, Proceedings of 1994 IEEE International Conference on Neural Networks (ICNN\u201994), Orlando, FL, USA, 1994, pp. 4588-4591 vol.7, https:\/\/doi.org\/10.1109\/ICNN.1994.375014.","DOI":"10.1109\/ICNN.1994.375014."},{"issue":"1","key":"7261_CR17","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/j.ejor.2019.08.045","volume":"283","author":"M Khatami","year":"2020","unstructured":"Khatami, M., Salehipour, A., & Cheng, T. C. E. (2020). Coupled task scheduling with exact delays: Literature review and models. European Journal of Operational Research, 283(1), 19\u201339. https:\/\/doi.org\/10.1016\/j.ejor.2019.08.045","journal-title":"European Journal of Operational Research"},{"key":"7261_CR18","doi-asserted-by":"publisher","unstructured":"Kubiak, W. (2023). A note on scheduling coupled tasks for minimum total completion time. Ann Oper Res 320, 541\u2013544 . https:\/\/doi.org\/10.1007\/s10479-022-04706-3","DOI":"10.1007\/s10479-022-04706-3"},{"issue":"1\u20132","key":"7261_CR19","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/S0166-218X(96)00041-8","volume":"72","author":"AJ Orman","year":"1997","unstructured":"Orman, A. J., & Potts, C. N. (1997). On the complexity of coupled-task scheduling. Discrete Applied Mathematics, 72(1\u20132), 141\u2013154. https:\/\/doi.org\/10.1016\/S0166-218X(96)00041-8","journal-title":"Discrete Applied Mathematics"},{"key":"7261_CR20","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1002\/nav.3800270312","volume":"28","author":"RD Shapiro","year":"1980","unstructured":"Shapiro, R. D. (1980). Scheduling coupled-tasks. Naval Research Logistics Quarterly, 28, 489\u2013497. https:\/\/doi.org\/10.1002\/nav.3800270312","journal-title":"Naval Research Logistics Quarterly"},{"issue":"2","key":"7261_CR21","doi-asserted-by":"publisher","first-page":"352","DOI":"10.1016\/j.cie.2011.01.015","volume":"61","author":"G Simonin","year":"2011","unstructured":"Simonin, G., Giroudeau, R., & K\u00f6nig, J. (2011). Complexity and approximation for scheduling problem for a torpedo. Computers and Industrial Engineering, 61(2), 352\u2013356. https:\/\/doi.org\/10.1016\/j.cie.2011.01.015","journal-title":"Computers and Industrial Engineering"},{"key":"7261_CR22","unstructured":"Tanas, M., Blazewicz, J. & Ecker, K. (2007). Polynomial Time Algorithm for Coupled Tasks Scheduling Problem, In: J. Blazewicz, K. Ecker and B. Hammer (Eds), ICOLE 2007, Lessach, Austria, Report IfI-07-03 (pp 76\u201379). TU Clausthal. http:\/\/www.in.tu-clausthal.de\/forschung\/technical-reports\/"},{"issue":"3","key":"7261_CR23","doi-asserted-by":"publisher","first-page":"868","DOI":"10.1016\/j.ejor.2018.07.012","volume":"272","author":"Z Haowei","year":"2019","unstructured":"Haowei, Z., Junwei, X., Jiaang, G., Zhaojian, Z., & Binfeng, Z. (2019). A hybrid adaptively genetic algorithm for task scheduling problem in the phased array radar. European Journal of Operational Research, 272(3), 868\u2013878. https:\/\/doi.org\/10.1016\/j.ejor.2018.07.012","journal-title":"European Journal of Operational Research"}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-026-07261-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10479-026-07261-3","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-026-07261-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,8]],"date-time":"2026-07-08T10:12:45Z","timestamp":1783505565000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10479-026-07261-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,21]]},"references-count":23,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[2026,7]]}},"alternative-id":["7261"],"URL":"https:\/\/doi.org\/10.1007\/s10479-026-07261-3","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"value":"0254-5330","type":"print"},{"value":"1572-9338","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,21]]},"assertion":[{"value":"9 February 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 April 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 May 2026","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 declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of Interest"}},{"value":"This article does not contain any studies with human participants or animals performed by any of the authors.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical approval"}}]}}