{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,16]],"date-time":"2026-05-16T03:58:15Z","timestamp":1778903895983,"version":"3.51.4"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2023,7,10]],"date-time":"2023-07-10T00:00:00Z","timestamp":1688947200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,7,10]],"date-time":"2023-07-10T00:00:00Z","timestamp":1688947200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000923","name":"Australian Research Council","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001774","name":"University of Sydney","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001774","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2024,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In many applications in the context of patient appointment scheduling there are recurring tasks with fixed delays between them. These tasks are commonly referred to as coupled-task jobs. In the coupled-task settings, each job consists of two tasks whereby the second task must start processing after an exact time lag following the completion of the first task. In this paper, we introduce the problem of scheduling a set of coupled-task jobs on parallel identical machines with the objective function of minimizing the makespan. We study the computational complexity of the general problem, as well as its special cases. We prove that the majority of these problems are (strongly) NP-hard. Nonetheless, we provide the optimal scheduling policy for two settings consisting of identical jobs. An important result of our work includes showing that the existence of a <jats:inline-formula><jats:alternatives><jats:tex-math>$$(2-\\varepsilon )$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mn>2<\/mml:mn>\n                    <mml:mo>-<\/mml:mo>\n                    <mml:mi>\u03b5<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-approximation algorithm for the problem implies <jats:inline-formula><jats:alternatives><jats:tex-math>$$P=NP$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>P<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mi>N<\/mml:mi>\n                    <mml:mi>P<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. The latter result improves a recently proposed bound for the open-shop counterpart as well.<\/jats:p>","DOI":"10.1007\/s11590-023-02014-8","type":"journal-article","created":{"date-parts":[[2023,7,10]],"date-time":"2023-07-10T16:04:20Z","timestamp":1689005060000},"page":"991-1003","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Scheduling coupled tasks on parallel identical machines"],"prefix":"10.1007","volume":"18","author":[{"given":"Mostafa","family":"Khatami","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Oron","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4866-1396","authenticated-orcid":false,"given":"Amir","family":"Salehipour","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,7,10]]},"reference":[{"key":"2014_CR1","first-page":"45","volume-title":"Inapproximately lower bounds for open shop problems with exact delays. Approximation and Online Algorithms","author":"AA Ageev","year":"2018","unstructured":"Ageev, A.A.: Inapproximately lower bounds for open shop problems with exact delays. Approximation and Online Algorithms, pp. 45\u201355. Springer International Publishing AG, Cham (2018)"},{"issue":"2","key":"2014_CR2","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/j.cmpb.2014.08.006","volume":"117","author":"A Azadeh","year":"2014","unstructured":"Azadeh, A., Farahani, M.H., Torabzadeh, S., Baghersad, M.: Scheduling prioritized patients in emergency department laboratories. Comput. Methods Programs Biomed. 117(2), 61\u201370 (2014)","journal-title":"Comput. Methods Programs Biomed."},{"issue":"5","key":"2014_CR3","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.: A note on scheduling identical coupled tasks in logarithmic time. Discret. Appl. Math. 158(5), 583\u2013587 (2010)","journal-title":"Discret. Appl. Math."},{"issue":"16","key":"2014_CR4","doi-asserted-by":"publisher","first-page":"2370","DOI":"10.1016\/j.dam.2012.05.026","volume":"160","author":"A Condotta","year":"2012","unstructured":"Condotta, A., Shakhlevich, N.: Scheduling coupled-operation jobs with exact time-lags. Discret. Appl. Math. 160(16), 2370\u20132388 (2012)","journal-title":"Discret. Appl. Math."},{"issue":"3","key":"2014_CR5","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/j.orhc.2014.02.002","volume":"3","author":"A Condotta","year":"2014","unstructured":"Condotta, A., Shakhlevich, N.: Scheduling patient appointments via multilevel template: a case study in chemotherapy. Oper. Res. Health Care 3(3), 129\u2013144 (2014)","journal-title":"Oper. Res. Health Care"},{"key":"2014_CR6","volume-title":"Computers and intractability","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability. Freeman San Francisco, USA (1979)"},{"key":"2014_CR7","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","volume":"5","author":"R Graham","year":"1979","unstructured":"Graham, R., Lawler, E., Lenstra, J., Kan, A.R.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discret Math. 5, 287\u2013326 (1979)","journal-title":"Ann. Discret Math."},{"issue":"4","key":"2014_CR8","doi-asserted-by":"publisher","first-page":"593","DOI":"10.1007\/s10288-020-00463-w","volume":"19","author":"M Khatami","year":"2021","unstructured":"Khatami, M., Salehipour, A.: A binary search algorithm for the general coupled task scheduling problem. 4OR. 19(4), 593\u2013611 (2021)","journal-title":"4OR."},{"issue":"2","key":"2014_CR9","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/s10951-020-00675-2","volume":"24","author":"M Khatami","year":"2021","unstructured":"Khatami, M., Salehipour, A.: Coupled task scheduling with time-dependent processing times. J. Sched. 24(2), 223\u2013236 (2021)","journal-title":"J. Sched."},{"issue":"1","key":"2014_CR10","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/j.ejor.2019.08.045","volume":"282","author":"M Khatami","year":"2020","unstructured":"Khatami, M., Salehipour, A., Cheng, T.C.E.: Coupled task scheduling with exact delays: Literature review and models. Eur. J. Oper. Res. 282(1), 19\u201339 (2020)","journal-title":"Eur. J. Oper. Res."},{"issue":"1","key":"2014_CR11","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/s10878-017-0232-z","volume":"37","author":"Z Liu","year":"2019","unstructured":"Liu, Z., Lu, J., Liu, Z., Liao, G., Zhang, H.H., Dong, J.: Patient scheduling in hemodialysis service. J. Comb. Optim. 37(1), 337\u2013362 (2019)","journal-title":"J. Comb. Optim."},{"issue":"2","key":"2014_CR12","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/S0933-3657(00)00061-0","volume":"20","author":"CC Marinagi","year":"2000","unstructured":"Marinagi, C.C., Spyropoulos, C.D., Papatheodorou, C., Kokkotos, S.: Continual planning and scheduling for managing patient tests in hospital laboratories. Artif. Intell. Med. 20(2), 139\u2013154 (2000)","journal-title":"Artif. Intell. Med."},{"key":"2014_CR13","unstructured":"Mosheiov, G., Oron, D., Salehipour, A.: Minimizing total completion time with coupled-task jobs. Available at SSRN 3951871 (2020)"},{"issue":"1","key":"2014_CR14","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/S0166-218X(96)00041-8","volume":"72","author":"A Orman","year":"1997","unstructured":"Orman, A., Potts, C.: On the complexity of coupled-task scheduling. Discret. Appl. Math. 72(1), 141\u2013154 (1997)","journal-title":"Discret. Appl. Math."},{"issue":"4","key":"2014_CR15","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/s10729-013-9224-4","volume":"16","author":"E P\u00e9rez","year":"2013","unstructured":"P\u00e9rez, E., Ntaimo, L., Malav\u00e9, C.O., Bailey, C., McCormack, P.: Stochastic online appointment scheduling of multi-step sequential procedures in nuclear medicine. Health Care Manag. Sci. 16(4), 281\u2013299 (2013)","journal-title":"Health Care Manag. Sci."},{"issue":"3","key":"2014_CR16","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1080\/19488300.2011.617718","volume":"1","author":"E P\u00e9rez","year":"2011","unstructured":"P\u00e9rez, E., Ntaimo, L., Wilhelm, W.E., Bailey, C., McCormack, P.: Patient and resource scheduling of multi-step medical procedures in nuclear medicine. IIE Trans. Healthcare Syst. Eng. 1(3), 168\u2013184 (2011)","journal-title":"IIE Trans. Healthcare Syst. Eng."},{"issue":"3","key":"2014_CR17","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1002\/nav.3800270312","volume":"27","author":"RD Shapiro","year":"1980","unstructured":"Shapiro, R.D.: Scheduling coupled tasks. Naval Res. Logist. Quart 27(3), 489\u2013498 (1980)","journal-title":"Naval Res. Logist. Quart"},{"issue":"2","key":"2014_CR18","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.-C.: Complexity and approximation for scheduling problem for a torpedo. Comput. Ind. Eng. 61(2), 352\u2013356 (2011)","journal-title":"Comput. Ind. Eng."}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-023-02014-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11590-023-02014-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-023-02014-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,12]],"date-time":"2024-04-12T03:31:48Z","timestamp":1712892708000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11590-023-02014-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,10]]},"references-count":18,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,5]]}},"alternative-id":["2014"],"URL":"https:\/\/doi.org\/10.1007\/s11590-023-02014-8","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"value":"1862-4472","type":"print"},{"value":"1862-4480","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,7,10]]},"assertion":[{"value":"4 November 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 April 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 July 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}