On considère un problème d'ordonnancement d'observations d'étoiles sur télescope: des nuits sont disponibles pour observer des étoiles identifiées comme intéressante par les astronomes. Chaque étoile ne peut être observée que pendant une certaine fenêtre de temps et rapporte un gain scientifique. L'objectif est de maximiser la somme des gains des observations réalisées. En considérant les nuits comme des machines et les étoiles comme des tâches à exécuter, on reconnaît le problème très classique d'ordonnancement de tâches sur machines parallèles.

Dans le problème pratique d'observation d'étoiles, la possibilité d'observer dépend des conditions météorologiques et atmosphériques qui ne sont pas connues lorsque l'ordonnancement est calculé. Il s'agit donc de proposer un ordonnancement "de bonne qualité" sans connaître le nombre de nuits (machines) effectivement disponibles; contrairement aux modèles classiques d'ordonnancement où l'incertitude porte plutôt sur les données associées aux tâches. On s'intéresse ici à l'évaluation du pire cas dans le paradigme de l'optimisation robuste. Nous présenterons une analyse de complexité de ce problème, puis nous proposerons différents modèles pour le résoudre ainsi que des résultats numériques sur des instances réalistes.