Nous considérons un problème d'optimisation chez Renault lorsqu'un nouveau modèle de véhicule vient d'être créé et doit subir une série de tests de validation avant d'être commercialisé.
Ces tests peuvent être liés à la sécurité, à l'endurance, etc. Cette phase est coûteuse, car des véhicules spécifiques, appelés prototypes, sont construits exclusivement pour faire les tests. Plusieurs prototypes sont nécessaires, car de nombreux tests sont réalisés en parallèle, et certains tests peuvent endommager le véhicule, et différentes configuration et options d'un même prototype sont nécessaires pour différents tests. Les tests de validation effectués dans les différents sites d'essais sont nombreux et variés.
Pour les véhicules, un prototype peut avoir plusieurs options différentes selon les tests qu'on va lui affecter. Lorsqu'un prototype est configuré pour un test donné, il ne peut pas être utilisé pour d'autres tests qui nécessitent un jeu d'options différent.
Du point de vue de la recherche opérationnelle, le problème peut être vu comme un problème d'optimisation bi-niveaux. Dans une première étape, une configuration et des options sont choisis pour chaque prototype de véhicule fabriqué. Dans une deuxième étape, une séquence de tâches est assignée à chaque véhicule afin de minimiser les retards des tâches par rapport à leurs dates d'échéance.
Une tâche ne peut être attribuée à une machine/un véhicule que si la configuration et les options du véhicule sont compatibles avec la tâche. Comme les véhicules sont produits et testés dans différents sites, le problème d'affectation des tâches peut être considéré comme un problème d'ordonnancement avec time-lags. Il y a également plusieurs fonctions objectifs à minimiser en plus des retards des tâches. Le problème global peut être vu comme un problème combiné de configuration des machines et d'ordonnancement multicritère à machines dédiées parallèles (les véhicules), avec fenêtres de temps et avec time-lags.