Abstract (FR)

Le problème considéré est une généralisation du problème d'affectation classique pour prendre en compte des contraintes de mutuelle exclusion qui viennent restreindre les possibilités d'affectation des tâches aux processeurs en raison de familles de tâches incompatibles. Ces familles sont définies relativement à chaque processeur, celui-ci ne pouvant traiter qu'une tâche au plus de la famille considérée. Chaque processeur peut normalement traiter un certain nombre de tâches pour un coût nul, sa capacité pouvant être accrue moyennant des coûts marginaux non décroissants. Chaque tâche doit être affectée à un processeur et un seul avec certaines “préférences”. Celles-ci sont formalisées par des valeurs de “dis-satisfaction”. La qualité d'une affectation est évaluée à l'aide de trois critères: G1 – la dis-satisfaction maximum des tâches, G2 – la dis-satisfaction totale des tâches, G3 – le coût total de traitement par les processeurs. Lorsqu'il n'existe pas d'affectation réalisable, les tâches et processeurs qui constituent la “configuration bloquante” sont identifiés et toutes les actions de déblocage sont mises en évidence. Plusieurs résultats relatifs aux configurations bloquantes et actions de déblocage sont démontrés. Une procédure interactive d'exploration des solutions non dominées est décrite et illustrée sur deux exemples résolus avec un logiciel spécialement conçu.