Relatore : Philippe CHRÉTIENNE

Co-relazione : 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.

Pubblicazioni 2013

• 2013
  • V. Jeauneau : “Contribution à l’ordonnancement temps réel - Application aux radars multifonctions”, these, difesa 12/13/2013, relatore Chrétienne, Philippe, co-relazione : Barcaresco, Frédéric (2013)
  • V. Jeauneau, Ph. Chrétienne : “Minimizing the number of late jobs on parallel machines with alpha time windows”, 6^th Multidisciplinary International Scheduling Conference: Theory and Applications (MISTA 2013), Gent, Belgium (2013)