{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T12:04:56Z","timestamp":1775736296117,"version":"3.50.1"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2023,7,17]],"date-time":"2023-07-17T00:00:00Z","timestamp":1689552000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,7,17]],"date-time":"2023-07-17T00:00:00Z","timestamp":1689552000000},"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 Sched"],"published-print":{"date-parts":[[2024,4]]},"DOI":"10.1007\/s10951-023-00788-4","type":"journal-article","created":{"date-parts":[[2023,7,17]],"date-time":"2023-07-17T19:01:53Z","timestamp":1689620513000},"page":"119-133","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Fixed-parameter tractability of scheduling dependent typed tasks subject to release times and deadlines"],"prefix":"10.1007","volume":"27","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2482-5042","authenticated-orcid":false,"given":"Claire","family":"Hanen","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2170-6366","authenticated-orcid":false,"given":"Alix","family":"Munier Kordon","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,7,17]]},"reference":[{"issue":"2","key":"788_CR1","doi-asserted-by":"publisher","first-page":"629","DOI":"10.1016\/j.ejor.2020.09.042","volume":"291","author":"R Baart","year":"2021","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.","journal-title":"European Journal of Operational Research"},{"key":"788_CR2","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1023\/A:1018995000688","volume":"92","author":"P Baptiste","year":"1999","unstructured":"Baptiste, P., Le Pape, C., & Nuijten, W. (1999). Satisfiability tests and time-bound adjustments for cumulative scheduling problems. Annals of Operations Research, 92, 305\u2013333.","journal-title":"Annals of Operations Research"},{"issue":"3","key":"788_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. Journal of Scheduling, 22(3), 305\u2013313.","journal-title":"Journal of Scheduling"},{"key":"788_CR4","unstructured":"Bodlaender, H. L., & van\u00a0der Wegen, M. (2020). Parameterized complexity of scheduling chains of jobs with delays. arXiv preprint arXiv:2007.09023"},{"key":"788_CR5","first-page":"1","volume":"11","author":"HL Bodlaender","year":"1992","unstructured":"Bodlaender, H. L. (1992). A tourist guide through treewidth. Acta Cybernetica, 11, 1\u201321.","journal-title":"Acta Cybernetica"},{"issue":"2","key":"788_CR6","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/0167-6377(95)00031-9","volume":"18","author":"HL Bodlaender","year":"1995","unstructured":"Bodlaender, H. L., & Fellows, M. R. (1995). W[2]-hardness of precedence constrained k-processor scheduling. Operations Research Letters, 18(2), 93\u201397.","journal-title":"Operations Research Letters"},{"key":"788_CR7","doi-asserted-by":"crossref","unstructured":"Brucker, P. (2004). Scheduling algorithms (4th ed.). Springer.","DOI":"10.1007\/978-3-540-24804-0"},{"key":"788_CR8","unstructured":"Carlier, J., Peridy, L., Pinson, E., & Rivreau, D. (2004). Elimination rules for the job-shop. In: Leung, J. Y.-T. (Ed.) Handbook of Scheduling: Algorithms, Models, and Performance Analysis (pp. 1\u201319). Chapman & Hall."},{"issue":"3","key":"788_CR9","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/s10951-016-0507-8","volume":"20","author":"A Carlier","year":"2017","unstructured":"Carlier, A., Hanen, C., & Munier Kordon, A. (2017). The equivalence of two classical list scheduling algorithms for dependent typed tasks with release dates, due dates and precedence delays. Journal of Scheduling, 20(3), 303\u2013311.","journal-title":"Journal of Scheduling"},{"issue":"1","key":"788_CR10","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/j.dam.2003.09.009","volume":"145","author":"J Carlier","year":"2004","unstructured":"Carlier, J., & Pinson, E. (2004). Jackson\u2019s pseudo-preemptive schedule and cumulative scheduling problems. Discrete Applied Mathematics, 145(1), 80\u201394.","journal-title":"Discrete Applied Mathematics"},{"key":"788_CR11","doi-asserted-by":"crossref","unstructured":"Chen, B., Potts, C.N., & Woeginger, G.J. (1998). In: Du, D.-Z., & Pardalos, P.M. (Eds.) A review of machine scheduling: Complexity, algorithms and approximability (pp. 1493\u20131641). Springer","DOI":"10.1007\/978-1-4613-0303-9_25"},{"key":"788_CR12","doi-asserted-by":"crossref","unstructured":"Cygan, M., Fomin, F. V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., & Saurabh, S. (2015). Parameterized Algorithms (1st ed.). Springer.","DOI":"10.1007\/978-3-319-21275-3"},{"issue":"1","key":"788_CR13","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1016\/0196-6774(84)90039-7","volume":"5","author":"D Dolev","year":"1984","unstructured":"Dolev, D., & Warmuth, M. K. (1984). Scheduling precedence graphs of bounded height. Journal of Algorithms, 5(1), 48\u201359.","journal-title":"Journal of Algorithms"},{"key":"788_CR14","doi-asserted-by":"crossref","unstructured":"Downey, R.G., & Fellows, M.R. (1992). Fixed-parameter intractability. In Proceedings of the 7th annual structure in complexity theory conference (pp. 36\u201349).","DOI":"10.1109\/SCT.1992.215379"},{"key":"788_CR15","doi-asserted-by":"crossref","unstructured":"Downey, R. G., & Fellows, M. R. (2013). Fundamentals of parameterized complexity (1st ed.). Springer.","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"788_CR16","unstructured":"Flum, J., & Grohe, M. (2006). Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series). Springer."},{"key":"788_CR17","unstructured":"Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of NP-completeness. W. H. Freeman & Co."},{"key":"788_CR18","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1137\/0206029","volume":"6","author":"MR Garey","year":"1977","unstructured":"Garey, M. R., & Johnson, D. S. (1977). Two-processor scheduling with start-time and deadlines. SIAM Journal on Computing, 6, 416\u2013426.","journal-title":"SIAM Journal on Computing"},{"key":"788_CR19","doi-asserted-by":"crossref","unstructured":"Graham, R. L., Lawler, E. L., Lenstra, J. K., & Kan, A. H. G. R. (1979). Optimization and approximation in deterministic sequencing and scheduling: a survey. In Hammer, P. L., Johnson, E. L., Korte, B. H. (Eds.) Discrete optimization II. Annals of discrete mathematics (Vol. 5, pp. 287\u2013326). Elsevier.","DOI":"10.1016\/S0167-5060(08)70356-X"},{"issue":"12","key":"788_CR20","doi-asserted-by":"publisher","first-page":"2968","DOI":"10.1016\/j.cor.2012.02.024","volume":"39","author":"JAS Gromicho","year":"2012","unstructured":"Gromicho, J. A. S., Van Hoorn, J. J., Saldanha-da-Gama, F., & Timmer, G. T. (2012). Solving the job-shop scheduling problem optimally by dynamic programming. Computers & Operations Research, 39(12), 2968\u20132977.","journal-title":"Computers & Operations Research"},{"issue":"1","key":"788_CR21","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1007\/s10878-012-9498-3","volume":"27","author":"E G\u00fcnther","year":"2014","unstructured":"G\u00fcnther, E., K\u00f6nig, F. G., & Megow, N. (2014). Scheduling and packing malleable and parallel tasks with precedence constraints of bounded width. Journal of Combinatorial Optimization, 27(1), 164\u2013181.","journal-title":"Journal of Combinatorial Optimization"},{"issue":"4","key":"788_CR22","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/s10951-009-0101-4","volume":"12","author":"C Hanen","year":"2009","unstructured":"Hanen, C., & Zinder, Y. (2009). The worst-case analysis of the Garey\u2013Johnson algorithm. Journal of Scheduling, 12(4), 389\u2013400.","journal-title":"Journal of Scheduling"},{"issue":"3","key":"788_CR23","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/0166-218X(94)90142-2","volume":"52","author":"K Jansen","year":"1994","unstructured":"Jansen, K. (1994). Analysis of scheduling problems with typed task systems. Discrete Applied Mathematics, 52(3), 223\u2013232.","journal-title":"Discrete Applied Mathematics"},{"issue":"5","key":"788_CR24","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1007\/s10951-017-0550-0","volume":"21","author":"D Knop","year":"2018","unstructured":"Knop, D., & Kouteck\u00fd, M. (2018). Scheduling meets n-fold integer programming. Journal of Scheduling, 21(5), 493\u2013503.","journal-title":"Journal of Scheduling"},{"key":"788_CR25","doi-asserted-by":"crossref","unstructured":"Lenstra, J. K., Rinnooy Kan, A. H. G., & Brucker, P. (1977). Complexity of machine scheduling problems. In: Hammer, P. L., Johnson, E. L., Korte, B. H., Nemhauser, G. L. (Eds.) Studies in Integer Programming. Annals of Discrete Mathematics (Vol. 1, pp. 343\u2013362). Elsevier.","DOI":"10.1016\/S0167-5060(08)70743-X"},{"issue":"1","key":"788_CR26","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1287\/opre.26.1.22","volume":"26","author":"JK Lenstra","year":"1978","unstructured":"Lenstra, J. K., & Rinnooy Kan, A. H. G. (1978). Complexity of scheduling under precedence constraints. Operations Research, 26(1), 22\u201335.","journal-title":"Operations Research"},{"key":"788_CR27","unstructured":"Leung, J., Kelly, L., & Anderson, J. H. (2004). Handbook of scheduling: Algorithms, models, and performance analysis. CRC Press Inc."},{"key":"788_CR28","doi-asserted-by":"crossref","unstructured":"Leung, J., & Li, C.-L. (2008). Scheduling with processing set restrictions: A survey. International Journal of Production Economics, 116, 251\u2013262.","DOI":"10.1016\/j.ijpe.2008.09.003"},{"key":"788_CR29","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1145\/383721.383733","volume":"23","author":"A Leung","year":"2001","unstructured":"Leung, A., Palem, K. V., & Pnueli, A. (2001). Scheduling time-constrained instructions on pipelined processors. ACM Transactions on Programming Languages and Systems, 23, 73\u2013103.","journal-title":"ACM Transactions on Programming Languages and Systems"},{"issue":"1","key":"788_CR30","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/BF00260927","volume":"10","author":"JW Liu","year":"1978","unstructured":"Liu, J. W., & Liu, C. L. (1978). Performance analysis of multiprocessor systems containing functionally dedicated processors. Acta Informatica, 10(1), 95\u2013104.","journal-title":"Acta Informatica"},{"key":"788_CR31","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 and Operations Research, 100, 254\u2013261.","journal-title":"Computers and Operations Research"},{"key":"788_CR32","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1007\/s10107-014-0830-9","volume":"154","author":"M Mnich","year":"2015","unstructured":"Mnich, M., & Wiese, A. (2015). Scheduling and fixed-parameter tractability. Mathematical Programming, 154, 533\u2013562.","journal-title":"Mathematical Programming"},{"key":"788_CR33","doi-asserted-by":"crossref","unstructured":"M\u00f6hring, R. H. (1989). In Rival, I. (Ed.) Computationally tractable classes of ordered sets (pp. 105\u2013193). Springer.","DOI":"10.1007\/978-94-009-2639-4_4"},{"key":"788_CR34","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.dam.2020.11.024","volume":"290","author":"A Munier Kordon","year":"2021","unstructured":"Munier Kordon, A. (2021). A fixed-parameter algorithm for scheduling unit dependent tasks on parallel machines with time windows. Discrete Applied Mathematics, 290, 1\u20136.","journal-title":"Discrete Applied Mathematics"},{"issue":"1","key":"788_CR35","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0095-8956(83)90079-5","volume":"35","author":"N Robertson","year":"1983","unstructured":"Robertson, N., & Seymour, P. D. (1983). Graph minors. i. Excluding a forest. Journal of Combinatorial Theory, Series B, 35(1), 39\u201361.","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"788_CR36","doi-asserted-by":"crossref","unstructured":"Tang, N., & Munier Kordon, A. (2021). A fixed-parameter algorithm for scheduling unit dependent tasks with unit communication delays. In: European Conference on Parallel Processing (pp. 105\u2013119). Springer.","DOI":"10.1007\/978-3-030-85665-6_7"},{"key":"788_CR37","doi-asserted-by":"crossref","unstructured":"Van Bevern, R., Bredereck, R., Bulteau, L., Komusiewicz, C., Talmon, N., & Woeginger, G. J. (2016). Precedence-constrained scheduling problems parameterized by partial order width. In Y. Kochetov, M. Khachay, V. Beresnev, E. Nurminski, & P. Pardalos (Eds.), Discrete Optimization and Operations Research (pp. 105\u2013120). Springer.","DOI":"10.1007\/978-3-319-44914-2_9"},{"key":"788_CR38","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1016\/j.cor.2016.09.001","volume":"78","author":"JJ van Hoorn","year":"2017","unstructured":"van Hoorn, J. J., Nogueira, A., Ojea, I., & Gromicho, J. A. S. (2017). An corrigendum on the paper: Solving the job-shop scheduling problem optimally by dynamic programming. Computers and Operations Research, 78, 381.","journal-title":"Computers and Operations Research"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-023-00788-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10951-023-00788-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-023-00788-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,7]],"date-time":"2024-04-07T12:04:48Z","timestamp":1712491488000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10951-023-00788-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,17]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,4]]}},"alternative-id":["788"],"URL":"https:\/\/doi.org\/10.1007\/s10951-023-00788-4","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"value":"1094-6136","type":"print"},{"value":"1099-1425","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,7,17]]},"assertion":[{"value":"7 June 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 July 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declaration"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}