{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T13:28:56Z","timestamp":1740144536062,"version":"3.37.3"},"reference-count":26,"publisher":"EDP Sciences","issue":"5","license":[{"start":{"date-parts":[[2022,11,1]],"date-time":"2022-11-01T00:00:00Z","timestamp":1667260800000},"content-version":"vor","delay-in-days":61,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2022,10,4]]},"published-print":{"date-parts":[[2022,9]]},"abstract":"<jats:p>This paper considers the minimization of the maximum lateness for a set of dependent tasks with unit duration, unit communication delays release times and due dates. The number of processors is limited, and each task requires one processor for its execution. A time window built from an upper bound of the minimum maximum lateness is associated to each task. The parameter considered is the pathwidth of the associated interval graph. A fixed-parameter algorithm based on a dynamic programming approach is developed to solve this optimization problem. This is, as far as we know, the first fixed-parameter algorithm for a scheduling problem with communication delays and a limited number of processors.<\/jats:p>","DOI":"10.1051\/ro\/2022174","type":"journal-article","created":{"date-parts":[[2022,10,5]],"date-time":"2022-10-05T08:05:57Z","timestamp":1664957157000},"page":"3777-3788","source":"Crossref","is-referenced-by-count":0,"title":["A fixed-parameter algorithm for a unit-execution-time unit-communication-time tasks scheduling problem with a limited number of identical processors"],"prefix":"10.1051","volume":"56","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2170-6366","authenticated-orcid":false,"given":"Alix Munier","family":"Kordon","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ning","family":"Tang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2022,11,1]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","first-page":"1091","DOI":"10.1007\/s11590-014-0802-2","volume":"11","author":"Ait El Cadi","year":"2017","journal-title":"Optim. Lett."},{"key":"R2","first-page":"1","volume":"11","author":"Bodlaender","year":"1992","journal-title":"Acta Cybern."},{"key":"R3","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/0167-6377(95)00031-9","volume":"18","author":"Bodlaender","year":"1995","journal-title":"Oper. Res. Lett."},{"key":"R4","unstructured":"Chr\u00e9tienne P. and Picouleau C., Scheduling with communication delays: a survey, in Scheduling Theory and its Applications. John Wiley & Sons, New York (1995) 65\u201390."},{"key":"R5","doi-asserted-by":"crossref","unstructured":"Cygan M., Fomin F.V., Kowalik \u0141., Lokshtanov D., Marx D., Pilipczuk M., Pilipczuk M. and Saurabh S., Parameterized Algorithms, 1st edition. Springer Publishing Company, Incorporated (2015).","DOI":"10.1007\/978-3-319-21275-3"},{"key":"R6","unstructured":"Davidovi\u0107 T., Liberti L., Maculan N. and Mladenovic N., Towards the Optimal Solution of the Multiprocessor Scheduling Problem with Communication Delays. MISTA Conference (2007)."},{"key":"R7","doi-asserted-by":"crossref","first-page":"629","DOI":"10.1016\/j.ejor.2020.09.042","volume":"291","author":"de Weerdt","year":"2021","journal-title":"Eur. J. Oper. Res."},{"key":"R8","doi-asserted-by":"crossref","unstructured":"Downey R.G. and Fellows M.R., Fundamentals of Parameterized Complexity. Springer, London (2013).","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"Drozdowski M., Scheduling for Parallel Processing. Springer (2009).","DOI":"10.1007\/978-1-84882-310-5"},{"key":"R10","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/0890-5401(91)90009-Q","volume":"92","author":"Du","year":"1991","journal-title":"Inf. Comput."},{"key":"R11","doi-asserted-by":"crossref","unstructured":"Giroudeau R. and Koenig J.-C., Scheduling with communication delays, in Multiprocessor Scheduling, edited by Levner E.. IntechOpen, Rijeka (2007).","DOI":"10.5772\/5215"},{"key":"R12","doi-asserted-by":"crossref","first-page":"1563","DOI":"10.1002\/j.1538-7305.1966.tb01709.x","volume":"45","author":"Graham","year":"1966","journal-title":"Bell Syst. Tech. J."},{"key":"R13","doi-asserted-by":"crossref","unstructured":"Graham R.L., Lawler E.L., Lenstra J.K. and Rinnooy Kan A.H.G., Optimization and approximation in deterministic sequencing and scheduling: a survey, in Discrete Optimization II. Annals of Discrete Mathematics, edited by Hammer P.L., Johnson E.L. and Korte B.H.. Vol. 5, Elsevier (1979) 287\u2013326.","DOI":"10.1016\/S0167-5060(08)70356-X"},{"key":"R14","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1007\/s10878-012-9498-3","volume":"27","author":"G\u00fcnther","year":"2014","journal-title":"J. Comb. Optim."},{"key":"R15","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/0167-6377(94)90024-8","volume":"16","author":"Hoogeveen","year":"1994","journal-title":"Oper. Res. Lett."},{"key":"R16","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1016\/j.cor.2018.07.020","volume":"100","author":"Mnich","year":"2018","journal-title":"Comput. Oper. Res."},{"key":"R17","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.dam.2020.11.024","volume":"290","author":"Munier Kordon","year":"2021","journal-title":"Discrete Appl. Math."},{"key":"R18","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/0166-218X(87)90042-4","volume":"18","author":"Rayward-Smith","year":"1987","journal-title":"Discrete Appl. Math."},{"key":"R19","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1287\/opre.18.2.263","volume":"18","author":"Schrage","year":"1970","journal-title":"Oper. Res."},{"key":"R20","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1007\/BF01586059","volume":"54","author":"Sousa","year":"1992","journal-title":"Math. Program."},{"key":"R21","doi-asserted-by":"crossref","unstructured":"Tang N. and Kordon A.M., A fixed-parameter algorithm for scheduling unit dependent tasks with unit communication delays, in European Conference on Parallel Processing. Lecture Notes in Computer Science. Vol. 12820. Springer (2021) 105\u2013119.","DOI":"10.1007\/978-3-030-85665-6_7"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"van Bevern R., Bredereck R., Bulteau L., Komusiewicz C., Talmon N. and Woeginger G.J., Precedence-constrained scheduling problems parameterized by partial order width, in International Conference on Discrete Optimization and Operations Research. Springer International Publishing (2016) 105\u2013120.","DOI":"10.1007\/978-3-319-44914-2_9"},{"key":"R23","unstructured":"Veltman B., Multiprocessor scheduling with communication delays. Ph.D. thesis. Eindhoven University of Technology (1993)."},{"key":"R24","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/0167-8191(90)90056-F","volume":"16","author":"Veltman","year":"1990","journal-title":"Parallel Comput."},{"key":"R25","doi-asserted-by":"crossref","first-page":"142","DOI":"10.1109\/TPDS.2014.2308175","volume":"26","author":"Venugopalan","year":"2015","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"R26","doi-asserted-by":"crossref","first-page":"627","DOI":"10.1007\/s11081-009-9080-8","volume":"11","author":"Zinder","year":"2010","journal-title":"Optim. Eng."}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2022174\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,1]],"date-time":"2022-11-01T09:13:36Z","timestamp":1667294016000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2022174"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9]]},"references-count":26,"journal-issue":{"issue":"5"},"alternative-id":["ro210547"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2022174","relation":{},"ISSN":["0399-0559","2804-7303"],"issn-type":[{"type":"print","value":"0399-0559"},{"type":"electronic","value":"2804-7303"}],"subject":[],"published":{"date-parts":[[2022,9]]}}}