{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,7]],"date-time":"2026-06-07T08:48:17Z","timestamp":1780822097217,"version":"3.54.1"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2026,3,22]],"date-time":"2026-03-22T00:00:00Z","timestamp":1774137600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,3,22]],"date-time":"2026-03-22T00:00:00Z","timestamp":1774137600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2026,4]]},"DOI":"10.1007\/s10878-026-01411-w","type":"journal-article","created":{"date-parts":[[2026,3,22]],"date-time":"2026-03-22T09:51:49Z","timestamp":1774173109000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Single Machine Scheduling with Precedence Constraints and Bounded Maximum Delay Value"],"prefix":"10.1007","volume":"51","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5654-1090","authenticated-orcid":false,"given":"Maher","family":"Mallem","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2482-5042","authenticated-orcid":false,"given":"Claire","family":"Hanen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2170-6366","authenticated-orcid":false,"given":"Alix","family":"Munier-Kordon","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,3,22]]},"reference":[{"key":"1411_CR1","doi-asserted-by":"crossref","unstructured":"Baart R, de Weerdt M, He L (2021) Single-machine scheduling with release times, deadlines, setup times, and rejection. European Journal of Operational Research 291(2), 629\u2013639, number: 2 Publisher: Elsevier","DOI":"10.1016\/j.ejor.2020.09.042"},{"issue":"5","key":"1411_CR2","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. Discret Appl Math 158(5):583\u2013587","journal-title":"Discret Appl Math"},{"issue":"3","key":"1411_CR3","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1007\/s10951-018-0581-1","volume":"22","author":"S Bessy","year":"2019","unstructured":"Bessy S, Giroudeau R (2019) Parameterized complexity of a coupled-task scheduling problem. J Sched 22(3):305\u2013313","journal-title":"J Sched"},{"key":"1411_CR4","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/s10951-016-0478-9","volume":"20","author":"R van Bevern","year":"2017","unstructured":"van Bevern R, Niedermeier R, Such\u1ef3 O (2017) A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack. J Sched 20:255\u2013265","journal-title":"J Sched"},{"key":"1411_CR5","doi-asserted-by":"crossref","unstructured":"Bodlaender HL (2021) Parameterized complexity of bandwidth of caterpillars and weighted path emulation. In: Graph-Theoretic concepts in computer science: 47th international workshop, WG 2021, Warsaw, Poland, June 23\u201325, 2021, Revised Selected Papers 47, Springer, pp 15\u201327","DOI":"10.1007\/978-3-030-86838-3_2"},{"key":"1411_CR6","unstructured":"Bodlaender HL, van der Wegen M (2020) Parameterized complexity of scheduling chains of jobs with delays. In: 15th international symposium on parameterized and exact computation (IPEC)"},{"key":"1411_CR7","doi-asserted-by":"crossref","unstructured":"Bodlaender HL, Groenland C, Nederlof J, Swennenhuis CM (2022) Parameterized problems complete for nondeterministic FPT time and logarithmic space. In: 2021 IEEE 62nd annual symposium on foundations of computer science (FOCS), IEEE, pp 193\u2013204","DOI":"10.1109\/FOCS52979.2021.00027"},{"issue":"1\u20133","key":"1411_CR8","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/S0166-218X(99)00015-3","volume":"94","author":"P Brucker","year":"1999","unstructured":"Brucker P, Hilbig T, Hurink J (1999) A branch and bound algorithm for a single-machine scheduling problem with positive and negative time-lags. Discret Appl Math 94(1\u20133):77\u201399","journal-title":"Discret Appl Math"},{"issue":"4","key":"1411_CR9","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1109\/TC.1980.1675569","volume":"C\u201329","author":"J Bruno","year":"1980","unstructured":"Bruno J, So K (1980) Deterministic scheduling with pipelined processors. IEEE Trans Comput C\u201329(4):308\u2013316","journal-title":"IEEE Trans Comput"},{"issue":"2","key":"1411_CR10","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/s10951-020-00668-1","volume":"24","author":"B Chen","year":"2021","unstructured":"Chen B, Zhang X (2021) Scheduling coupled tasks with exact delays for minimum total job completion time. J Sched 24(2):209\u2013221","journal-title":"J Sched"},{"issue":"1","key":"1411_CR11","doi-asserted-by":"publisher","first-page":"161","DOI":"10.2307\/1969503","volume":"51","author":"RP Dilworth","year":"1950","unstructured":"Dilworth RP (1950) A decomposition theorem for partially ordered sets. Ann Math 51(1):161\u2013166","journal-title":"Ann Math"},{"key":"1411_CR12","doi-asserted-by":"publisher","first-page":"661","DOI":"10.1007\/s00453-014-9944-y","volume":"71","author":"M Elberfeld","year":"2015","unstructured":"Elberfeld M, Stockhusen C, Tantau T (2015) On the space and circuit complexity of parameterized problems: classes and completeness. Algorithmica 71:661\u2013701","journal-title":"Algorithmica"},{"key":"1411_CR13","volume-title":"Scheduling for Hardware\/Software partitioning in embedded system design","author":"DW Engels","year":"2000","unstructured":"Engels DW (2000) Scheduling for Hardware\/Software partitioning in embedded system design. Massachusetts Institute of Technology, Cambridge"},{"issue":"3","key":"1411_CR14","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1016\/0166-218X(96)00110-2","volume":"70","author":"L Finta","year":"1996","unstructured":"Finta L, Liu Z (1996) Single machine scheduling subject to precedence delays. Discret Appl Math 70(3):247\u2013266","journal-title":"Discret Appl Math"},{"key":"1411_CR15","volume-title":"Parameterized Complexity Theory","author":"J Flum","year":"1998","unstructured":"Flum J, Grohe M (1998) Parameterized Complexity Theory. Springer"},{"issue":"3","key":"1411_CR16","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1137\/0134037","volume":"34","author":"MR Garey","year":"1978","unstructured":"Garey MR, Graham RL, Johnson DS, Knuth DE (1978) Complexity results for bandwidth minimization. SIAM J Appl Math 34(3):477\u2013495","journal-title":"SIAM J Appl Math"},{"key":"1411_CR17","doi-asserted-by":"crossref","unstructured":"Graham RL, Lawler EL, Lenstra JK, Kan AR (1979) Optimization and approximation in deterministic sequencing and scheduling: a survey. In: Annals of discrete mathematics, vol 5, Elsevier, pp 287\u2013326","DOI":"10.1016\/S0167-5060(08)70356-X"},{"key":"1411_CR18","unstructured":"Hanen C, Mallem M, Munier-Kordon A (2022) Parameterized complexity of single-machine scheduling with precedence, release dates and deadlines. In: 15th workshop on models and algorithms for planning and scheduling problems (MAPSP)"},{"issue":"1","key":"1411_CR19","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/j.jcss.2012.04.004","volume":"79","author":"K Jansen","year":"2013","unstructured":"Jansen K, Kratsch S, Marx D, Schlotter I (2013) Bin packing with fixed number of bins revisited. J Comput Syst Sci 79(1):39\u201349","journal-title":"J Comput Syst Sci"},{"issue":"1","key":"1411_CR20","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 (2020) Coupled task scheduling with exact delays: literature review and models. Eur J Oper Res 282(1):19\u201339","journal-title":"Eur J Oper Res"},{"key":"1411_CR21","doi-asserted-by":"crossref","unstructured":"Khatami M, Oron D, Salehipour A (2023) Scheduling coupled tasks on parallel identical machines. Optimization Letters pp 1\u201313","DOI":"10.1007\/s11590-023-02014-8"},{"issue":"3","key":"1411_CR22","doi-asserted-by":"publisher","first-page":"650","DOI":"10.1137\/0213040","volume":"13","author":"JT Leung","year":"1984","unstructured":"Leung JT, Vornberger O, Witthoff J (1984) On some variants of the bandwidth minimization problem. SIAM J Comput 13(3):650\u2013667","journal-title":"SIAM J Comput"},{"key":"1411_CR23","unstructured":"Mallem M, Hanen C, Munier-Kordon A (2022) Parameterized complexity of a parallel machine scheduling problem. In: 17th international symposium on parameterized and exact computation (IPEC)"},{"key":"1411_CR24","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1016\/j.cor.2018.07.020","volume":"100","author":"M Mnich","year":"2018","unstructured":"Mnich M, van Bevern R (2018) Parameterized complexity of machine scheduling: 15 open problems. Computers & Operations Research 100:254\u2013261","journal-title":"Computers & Operations Research"},{"issue":"8","key":"1411_CR25","doi-asserted-by":"publisher","first-page":"2309","DOI":"10.1007\/s00453-022-00970-8","volume":"84","author":"J Nederlof","year":"2022","unstructured":"Nederlof J, Swennenhuis CMF (2022) On the fine-grained parameterized complexity of partial scheduling to minimize the makespan. Algorithmica 84(8):2309\u20132334","journal-title":"Algorithmica"},{"issue":"2","key":"1411_CR26","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","volume":"4","author":"WJ Savitch","year":"1970","unstructured":"Savitch WJ (1970) Relationships between nondeterministic and deterministic tape complexities. J Comput Syst Sci 4(2):177\u2013192","journal-title":"J Comput Syst Sci"},{"key":"1411_CR27","volume-title":"Fine-grained parameterized complexity of scheduling and sequencing problems","author":"CMF Swennenhuis","year":"2022","unstructured":"Swennenhuis CMF (2022) Fine-grained parameterized complexity of scheduling and sequencing problems. Eindhoven University of Technology, Netherlands"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-026-01411-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-026-01411-w","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-026-01411-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T08:20:50Z","timestamp":1778055650000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-026-01411-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,22]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,4]]}},"alternative-id":["1411"],"URL":"https:\/\/doi.org\/10.1007\/s10878-026-01411-w","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3,22]]},"assertion":[{"value":"12 August 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 February 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 March 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 have no competing interests to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of Interest"}}],"article-number":"33"}}