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.
Keywords: Scheduling, communication delays, minimization of the maximum lateness, fixed-parameter algorithm
@article{RO_2022__56_5_3777_0,
author = {Kordon, Alix Munier and Tang, Ning},
title = {A fixed-parameter algorithm for a unit-execution-time unit-communication-time tasks scheduling problem with a limited number of identical processors},
journal = {RAIRO. Operations Research},
pages = {3777--3788},
year = {2022},
publisher = {EDP-Sciences},
volume = {56},
number = {5},
doi = {10.1051/ro/2022174},
mrnumber = {4503329},
zbl = {1502.90076},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2022174/}
}
TY - JOUR AU - Kordon, Alix Munier AU - Tang, Ning TI - A fixed-parameter algorithm for a unit-execution-time unit-communication-time tasks scheduling problem with a limited number of identical processors JO - RAIRO. Operations Research PY - 2022 SP - 3777 EP - 3788 VL - 56 IS - 5 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ro/2022174/ DO - 10.1051/ro/2022174 LA - en ID - RO_2022__56_5_3777_0 ER -
%0 Journal Article %A Kordon, Alix Munier %A Tang, Ning %T A fixed-parameter algorithm for a unit-execution-time unit-communication-time tasks scheduling problem with a limited number of identical processors %J RAIRO. Operations Research %D 2022 %P 3777-3788 %V 56 %N 5 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ro/2022174/ %R 10.1051/ro/2022174 %G en %F RO_2022__56_5_3777_0
Kordon, Alix Munier; Tang, Ning. A fixed-parameter algorithm for a unit-execution-time unit-communication-time tasks scheduling problem with a limited number of identical processors. RAIRO. Operations Research, Tome 56 (2022) no. 5, pp. 3777-3788. doi: 10.1051/ro/2022174
[1] , , , and , New MIP model for multiprocessor scheduling problem with communication delays. Optim. Lett. 11 (2017) 1091–1107. | MR | Zbl | DOI
[2] , A tourist guide through treewidth. Acta Cybern. 11 (1992) 1–21. | MR | Zbl
[3] and ,-hardness of precedence constrained -processor scheduling. Oper. Res. Lett. 18 (1995) 93–97. | MR | Zbl | DOI
[4] and , Scheduling with communication delays: a survey, in Scheduling Theory and its Applications. John Wiley & Sons, New York (1995) 65–90. | MR
[5] , , , , , , and , Parameterized Algorithms, 1st edition. Springer Publishing Company, Incorporated (2015). | MR | Zbl
[6] , , and , Towards the Optimal Solution of the Multiprocessor Scheduling Problem with Communication Delays. MISTA Conference (2007).
[7] , and , Single-machine scheduling with release times, deadlines, setup times, and rejection. Eur. J. Oper. Res. 291 (2021) 629–639. | MR | Zbl | DOI
[8] and , Fundamentals of Parameterized Complexity. Springer, London (2013). | MR | Zbl | DOI
[9] , Scheduling for Parallel Processing. Springer (2009). | MR | Zbl | DOI
[10] , and , Scheduling chain-structured tasks to minimize makespan and mean flow time. Inf. Comput. 92 (1991) 219–236. | MR | Zbl | DOI
[11] and , Scheduling with communication delays, in Multiprocessor Scheduling, edited by . IntechOpen, Rijeka (2007). | DOI
[12] , Bounds for certain multiprocessing anomalies. Bell Syst. Tech. J. 45 (1966) 1563–1581. | Zbl | DOI
[13] , , and , Optimization and approximation in deterministic sequencing and scheduling: a survey, in Discrete Optimization II. Annals of Discrete Mathematics, edited by , and . Vol. 5, Elsevier (1979) 287–326. | MR | Zbl
[14] , and , Scheduling and packing malleable and parallel tasks with precedence constraints of bounded width. J. Comb. Optim. 27 (2014) 164–181. | MR | Zbl | DOI
[15] , and , Three, four, five, six, or the complexity of scheduling with communication delays. Oper. Res. Lett. 16 (1994) 129–137. | MR | Zbl | DOI
[16] and , Parameterized complexity of machine scheduling: 15 open problems. Comput. Oper. Res. 100 (2018) 254–261. | MR | Zbl | DOI
[17] , A fixed-parameter algorithm for scheduling unit dependent tasks on parallel machines with time windows. Discrete Appl. Math. 290 (2021) 1–6. | MR | Zbl | DOI
[18] , Uet scheduling with unit interprocessor communication delays. Discrete Appl. Math. 18 (1987) 55–71. | MR | Zbl | DOI
[19] , Solving resource-constrained network problems by implicit enumeration – nonpreemptive case. Oper. Res. 18 (1970) 263–278. | Zbl | DOI
[20] and , A time indexed formulation of non-preemptive single machine scheduling problems. Math. Program. 54 (1992) 353–367. | MR | Zbl | DOI
[21] and , 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–119. | Zbl
[22] , , , , and , Precedence-constrained scheduling problems parameterized by partial order width, in International Conference on Discrete Optimization and Operations Research. Springer International Publishing (2016) 105–120. | MR | Zbl | DOI
[23] , Multiprocessor scheduling with communication delays. Ph.D. thesis. Eindhoven University of Technology (1993). | MR
[24] , and , Multiprocessor scheduling with communication delays. Parallel Comput. 16 (1990) 173–182. | Zbl | DOI
[25] and , Ilp formulations for optimal task scheduling with communication delays on parallel systems. IEEE Trans. Parallel Distrib. Syst. 26 (2015) 142–151. | DOI
[26] , , and , Scheduling uet-uct tasks: Branch-and-bound search in the priority space. Optim. Eng. 11 (2010) 627–646. | MR | Zbl | DOI
Cité par Sources :
