Supervision : Philippe CHRÉTIENNE
Co-supervision : BARCARESCO Frédéric
Apport to the real time scheduling problems - Application to multifunction radars
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.
Defence : 12/13/2013 - 14h - Site Jussieu 55-65/211
Jury members :
M. Christian Artigues (recherche aux LAAS-CNRS) [Rapporteur]
M. Jean-Charles Billaut (Professeur à l'école polytechique de l'Université de Tours) [Rapporteur]
M. Philipe Baptiste (Directeur, service de stratégie de la recherche et l'innovation, DGRI)
Mme. Safia Kedad-Sidhoum (Maître de conférence à l'Université Pierre et Marie Curie)
M. Philippe Chrétienne (Professeur à l'Université Pierre et Marie Curie)
M. Frédéric Barbaresco (Expert & Chef de Section Etudes Amont à Thales Air Systems S.A.)
- V. Jeauneau : “Contribution à l’ordonnancement temps réel - Application aux radars multifonctions”, thesis, defence 12/13/2013, supervision Chrétienne, Philippe, rapporteurs : BARCARESCO Frédéric (2013)
- V. Jeauneau, Ph. Chrétienne : “Minimizing the number of late jobs on parallel machines with alpha time windows”, 6th Multidisciplinary International Scheduling Conference: Theory and Applications (MISTA 2013), Gent, Belgium (2013)