Contribution à l'ordonnancement temps réel : Application aux radars multifonctions
Institution:
Paris 6Disciplines:
Directors:
Abstract EN:
L'objectif général de cette thèse, suggéré par le développement de nouveaux types de radar multifonctions, consiste à élaborer de nouveaux algorithmes d'ordonnancement des tâches radars répondant aux performances exigées. Dans un radar multifonctions, il existe différent types de tâches dont certaines sont fortement contraintes. Ces dernières tâches impactent considérable les performances du radar et ne peuvent pas retarder leur exécution de plus qu'une constant positive alpha. Dans cette thèse, nous étudions les problèmes d'ordonnancement liés à ce type de tâches. Dans un premier temps, nous définissons le modèle de base à partir duquel seront définis les différents problèmes d'ordonnancement et nous présentons les travaux antérieurs sur ce modèle. Dans un second temps, nous nous intéressons au problème d'ordonnancement à une machine de notre modèle de base pour lequel nous cherchons à minimiser le nombre de tâche en retard. Pour ce problème, nous développons des règles de dominance et nous proposons un algorithme polynomial pour le résoudre. Dans un troisième temps, nous étudions la version pondérée du problème d'ordonnancement à une machine de notre modèle de base et nous cherchons à minimiser la somme des priorités des tâches en retard. Nous commençons par montrer que le problème est NP-Difficile, puis nous proposons deux algorithmes de programmation dynamique pour le résoudre. Dans un quatrième temps, nous considérons le problème d'ordonnancement sur machines parallèles du modèle de base. Pour ce problème nous cherchons à minimiser le nombre de tâches en retard, nous montrons que le problème est NP-Difficile, nous développons un panel d'heuristiques, nous proposons une borne inférieure et nous présentons des résultats de simulation. Dans un cinquième temps, nous traitons du problème d'ordonnancement des tâches radars pour un radar multifonctions à un panneau fixe et celui pour un radar multifonctions à 4 panneaux fixes
Abstract FR:
The goal of this thesis, inspired by the development of new kinds of multifunction radar, is to think out of new radar tasks scheduling algorithms according to the radar performance required. In a multifunction radar system, there are several types of tasks and some of them are hard time constraint. These last one impact consequently the radar performances and cannot delay their execution more than a positive constant alpha. In this thesis, we study the scheduling of such tasks. Firstly, we define a generic model for scheduling problems and we present some previous works on this model. Secondly, we investigate the one machine scheduling problem of minimizing the number of late jobs for the generic model. We develop dominance rules and we propose a polynomial time algorithm to solve it. Thirdly, we study the weighted case of the one machine scheduling problem where the goal is to minimize the weighted numbers of late jobs. For this problem, we start by prove the NP-completeness, then we present two dynamic programming algorithms to solve it. Fourthly, we consider the parallel machines scheduling problem of the generic model where the goal is to minimize the number of late jobs. For this problem, we prove the NP-completeness, we develop a set of heuristics, we propose a lower bound and we present some experimental results. Fifthly, we consider the radar tasks scheduling problem for a fixed antenna radar and for a multi-panel antenna radar.