Voir la notice de l'article provenant de la source Numdam
The coupled tasks scheduling problem is a class of scheduling problems introduced for beam steering software of sophisticated radar devices, called phased arrays. Due to increasing popularity of such radars, the importance of coupled tasks scheduling is constantly growing. Unfortunately, most of the coupled tasks problems are NP-hard, and only a few practically usable algorithms for such problems were found. This paper provides a survey of already known complexity results of various variants of coupled tasks problems. Then, it complements previous results by providing experimental results of two new polynomial algorithms for coupled tasks scheduling, which are: an exact algorithm for 1|(1,4,1),strictchains|Cmax problem, and a fast heuristic algorithm for more general 1|(1,2k, 1), strictchains|Cmax problem, where k ∈ ℕ.
@article{RO_2012__46_4_335_0,
author = {Blazewicz, Jacek and Pawlak, Grzegorz and Tanas, Michal and Wojciechowicz, Wojciech},
title = {New algorithms for coupled tasks scheduling - a survey},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {335--353},
publisher = {EDP-Sciences},
volume = {46},
number = {4},
year = {2012},
doi = {10.1051/ro/2012020},
mrnumber = {3029894},
zbl = {1262.90060},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ro/2012020/}
}
TY - JOUR AU - Blazewicz, Jacek AU - Pawlak, Grzegorz AU - Tanas, Michal AU - Wojciechowicz, Wojciech TI - New algorithms for coupled tasks scheduling - a survey JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2012 SP - 335 EP - 353 VL - 46 IS - 4 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ro/2012020/ DO - 10.1051/ro/2012020 LA - en ID - RO_2012__46_4_335_0 ER -
%0 Journal Article %A Blazewicz, Jacek %A Pawlak, Grzegorz %A Tanas, Michal %A Wojciechowicz, Wojciech %T New algorithms for coupled tasks scheduling - a survey %J RAIRO - Operations Research - Recherche Opérationnelle %D 2012 %P 335-353 %V 46 %N 4 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ro/2012020/ %R 10.1051/ro/2012020 %G en %F RO_2012__46_4_335_0
Blazewicz, Jacek; Pawlak, Grzegorz; Tanas, Michal; Wojciechowicz, Wojciech. New algorithms for coupled tasks scheduling - a survey. RAIRO - Operations Research - Recherche Opérationnelle, Tome 46 (2012) no. 4, pp. 335-353. doi: 10.1051/ro/2012020
Cité par Sources :