Team : RO

Departure date : 01/31/2014

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.

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.)

- 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) - V. Jeauneau : “Contribution à l’ordonnancement temps réel - Application aux radars multifonctions”, these, defence 12/13/2013, supervision Chrétienne, Philippe, co-supervision BARCARESCO Frédéric (2013)

- V. Jeauneau, Ph. Chrétienne : “Minimizing the number of late jobs on parallel machines with alpha time windows”, 6