Brevet FR2932587A1 — publié le 20091218

Procédé d'optimisation d'ordonnancement de traitement de tâches et utilisation d'un tel procédé L'invention concerne un procédé d'optimisation d'ordonnancement de traitement de tâches. L'invention concerne également une utilisation de ce procédé pour ordonnancer les tâches de fabrication de pièces en matériau composite destinées à un aéronef. De manière plus précise, l'invention a pour but de minimiser le retard maximal des opérations d'un ensemble de pièces, c'est-à-dire le plus grand retard de livraison de ces pièces. L'invention s'applique dans un très grand nombre de domaines tels que, par exemple, l'industrie aéronautique, automobile et spatial. Les pièces en matériau composite présentent des propriétés, notamment mécaniques et chimiques, excellentes. Elles peuvent ainsi combiner une résistance élevée aux contraintes mécaniques et/ou thermiques et une forte rigidité pour une masse minimale. Elles peuvent également présenter des formes complexes. On connaît de nombreux procédés permettant l'imprégnation d'une préforme avec une résine liquide pour la fabrication d'une pièce composite. On décrit ci-dessous à titre illustratif, l'un des principaux procédés de mise en oeuvre du composite qui est la mise en oeuvre par moulage de préimprégné thermodurcissable en autoclave. Le matériau de base se présente sous la forme de mèches de fibres continues de carbone, de verre, d'aramide ou de quartz, orientées suivant une seule direction (bandes ou nappes) ou deux directions (tissus) et préimprégnées de résine époxyde ou phénolique non réticulée. Ce mélange fibre/résine, dit préimprégné ne devient un véritable matériau composite résistant et rigide qu'en phase finale de fabrication par cuisson de la résine, correspondant à la phase polymérisation. De fait, la phase de polymérisation représente une partie conséquente du temps de cycle de production de la pièce composite. Le procédé de fabrication d'une pièce composite à partir du préimprégné peut être décomposé en trois tâches élémentaires : - la découpe des plis ou la découpe du tissu nécessaire à la réalisation de la pièce. A l'origine, cette opération était effectuée manuellement. Aujourd'hui, elle est pratiquement automatisée sur une table de découpe programmable au moyen d'une machine de découpe telle que par jet fluide, couteau ultrason ou outil tranchant. L'exécution du traitement de cette tâche nécessite la disponibilité de la machine de découpe ; - draper la pièce posée sur un moule soit automatiquement au moyen d'une machine à draper, soit manuellement selon le degré de courbure de la surface. L'opération de drapage consiste à déposer dans l'outillage de moulage métallique ou composite mâle ou femelle, chaque couche suivant une direction bien définie pour constituer ainsi la pièce élémentaire par un empilement successif des couches, donnant ainsi le profil interne ou externe de la pièce. Cette tâche nécessite comme outillages un moule et une machine de drapage ; - polymériser la pièce par moulage en autoclave pour l'obtention du stratifié. La cuisson se fait suivant un cycle spécifique à chaque résine et au degré de polymérisation désirée. En particulier trois paramètres interviennent : la température, la pression, et la durée de la cuisson. Chaque pièce composite comporte son propre cycle de production et une date de livraison. Chacune des tâches décrites ci-dessus comporte donc une durée déterminée et à chaque pièce est associée une date de livraison. Il existe de plus un ordre à respecter dans le traitement des différentes tâches, par exemple la tâche concernant la polymérisation ne peut pas commencer tant que l'étape de drapage n'a pas été achevée. La structure de l'atelier est modélisée par un ensemble de moyens ou de ressources. Dans l'exemple décrit ci-dessus, l'exécution des traitements des trois tâches nécessite respectivement une machine de découpe, une machine de drapage et un moule, un autoclave et un moule. Le nombre de chaque catégorie de ressources peut rester figé pendant tout le processus de fabrication des pièces ou être modifié par exemple en raison d'une panne de l'une de ces ressources. Le problème d'optimisation du procédé de fabrication de pièces composites consiste donc à optimiser l'ordonnancement d'opérations de fabrication de pièces composites de manière à minimiser le retard maximal de traitement des tâches, c'est-à-dire que l'on cherche à minimiser le plus grand retard de livraison des pièces. Le problème d'ordonnancement de traitement de tâches à résoudre dans le cadre de la mise en oeuvre du procédé de fabrication d'une pièce en matériau composite doit intégrer les contraintes suivantes : - Flexibilité : pour effectuer certaines tâches, plusieurs machines sont utilisables, il faut alors choisir les machines sur lesquelles la pièce sera réalisée ; - Multi-ressources : la réalisation d'une tâche peut nécessiter plusieurs ressources en même temps, dans l'exemple décrit ci-dessus, la découpe nécessite à la fois une machine de découpe et un moule ; - Regroupement : certaines machines peuvent regrouper plusieurs tâches de plusieurs pièces en même temps sur certaines ressources, dans l'exemple décrit ci-dessus, pendant l'opération de polymérisation, certaines pièces qui appartiennent à la même famille (même durée de cuisson, même degré de polymérisation) et qui rentrent physiquement dans l'autoclave peuvent être regroupées ensemble, - Contrainte de préséance entre les différentes tâches, à savoir un ordre de traitement des tâches à respecter ; Comme on vient de le voir, le problème d'optimisation d'ordonnancement de 15 traitement de tâches est un problème combinatoire très complexe. Il existe un certain nombre de méthodes d'optimisation d'ordonnancement dans l'art antérieur qui sont proposées pour résoudre un tel problème. Toutefois les problèmes traités par ces méthodes n'intègrent pas toutes les contraintes mentionnées ci-dessus ou seulement une partie de ces contraintes. En outre, les méthodes existantes 20 traitent ces contraintes les unes indépendamment des autres. De manière générale les objectifs considérés sont la date de fin de l'ordonnancement. Dans des travaux plus proches de la problématique de l'invention, les problèmes traités n'intègrent pas d'opérations nécessitant plusieurs ressources en même temps, de plus le but principal que ces méthodes cherchent à atteindre est 25 de réduire les temps de préparation. Enfin la durée d'un regroupement dans le problème considéré est égale à la durée maximale des opérations qu'il contient, ou constante quelque soit le type de regroupement. Ceci n'est pas envisageable dans le cadre d'une solution physique. En effet le temps nécessaire pour faire exécuter plusieurs opérations en même temps sur une même machine, désigné 30 sous le terme la durée d'un regroupement, est une fonction quelconque de multiples paramètres, par exemple le temps de processus dans l'autoclave doit être une fonction complexe qui dépend de la superficie des pièces, du positionnement des pièces dans l'autoclave, de la forme des pièces, des propriétés physiques des outillages utilisés, etc. 35 La présente invention vise donc à fournir un procédé d'optimisation d'ordonnancement des différentes tâches pour fabriquer des pièces, permettant de prendre en compte toutes les contraintes de regroupement d'opérations en même temps, en visant à minimiser le retard maximal des opérations. 10 De manière plus précise, l'invention concerne un procédé d'optimisation d'ordonnancement de traitement d'un ensemble de tâches pour fabriquer n pièces, chaque pièce étant définie par un cycle de fabrication propre à la pièce et une date d'échéance, ledit cycle comportant un nombre fixe de m tâches, l'exécution de chacune des tâches étant conditionnée par un ordre de préséance et la disponibilité des ressources nécessaires à l'exécution de ladite tâche. Selon l'invention, le procédé comprend les étapes suivantes dans lesquelles : a) on génère aléatoirement un ensemble de P solutions initiales, chacune des solutions correspondant à une liste contenant les tâches destinées à être ordonnancées pour fabriquer les n pièces ; b) on construit une première solution admissible à partir de chacune des listes au moyen d'un processus itératif dans lequel on trie les tâches selon un paramètre de priorité en tenant compte de la disponibilité des ressources et des préséances à respecter ; c) on affecte à chacune des premières solutions une valeur de qualité correspondant au plus grand retard d'une tâche dans l'ordonnancement obtenu à l'étape (b) de manière à classer les solutions selon un ordre décroissant de valeur de qualité ; d) on sélectionne P couples de solutions dont la probabilité d'être 20 sélectionnée est proportionnelle à la valeur de qualité affectée de la solution ; e) on applique un opérateur de croisement sur chacun des P couples de solutions sélectionnés pour générer une nouvelle solution fille ; f) on applique un opérateur de mutation sur chacune des P solutions filles 25 générées à l'étape (e) ; g) on remplace l'ensemble des P solutions initiales de l'étape a) par l'ensemble des P solutions générées à l'issue de l'étape f) ; h) on répète les étapes b) à f) de manière itérative, le nombre d'itérations étant fixé préalablement. 30 Le retard des tâches est défini par rapport à une date d'échéance associée à chaque pièce, qui est par exemple la date de livraison de la pièce ou tout autre date devant être respectée. Selon une caractéristique supplémentaire de l'invention, l'étape de 35 construction de première solution admissible (b) comporte : - un premier tri selon une valeur propre des tâches de sorte que les tâches soient traitées selon un ordre décroissant ou croissant de leur valeur propre, et - un deuxième tri comportant n x m itérations correspondant à n x m tâches constituant une liste, chacune des itérations consistant à - à rechercher le plus petit instant t où une tâche peut démarrer en tenant compte de la disponibilité des ressources et des préséances à respecter, - à placer à l'instant t la première tâche de la liste qui peut démarrer à t, - dans le cas où ladite tâche sélectionnée doit être exécutée sur une ressource pouvant regrouper plusieurs tâches, à regrouper ladite tâche avec d'autres tâches compatibles dans un regroupement existant qui n'est pas encore ordonnancé dans la liste ou à créer un nouveau regroupement pour placer ladite tâche. On entend par "disponibilité de la ressource", la durée d'indisponibilité de la 15 ressource la plus petite possible. On entend par "regroupement qui n'est pas encore ordonnancé dans la liste", un regroupement de tâches qui est ouvert à l'instant t pouvant accueillir la tâche. Selon une autre caractéristique supplémentaire de l'invention, afin que ces regroupements ne restent pas indéfiniment ouverts en attente d'une éventuelle 20 tâche à ajouter, un regroupement est ordonnancé dans la liste dans les deux cas suivants : - lorsque l'attente du regroupement correspondant au temps maximum nécessaire pour que l'ensemble des pièces contenues dans le regroupement soient prêtes pour l'exécution de la tâche est supérieur 25 à un seuil d'acceptabilité prédéterminé, ou - lorsque la date de fin du regroupement est antérieure à l'instant considéré. Ainsi le regroupement est fermé ou ordonnancé dans liste si cette attente est trop longue, c'est-à-dire si elle est supérieure à un seuil d'acceptabilité 30 prédéterminé. Ce seuil peut être statique ou dynamique, dépendant des tâches du regroupement. A titre d'exemple, le regroupement est fermé pour débuter l'exécution des tâches s'il existe une tâche qui attend depuis plus de a fois sa durée (a = 0,5 ou 0,7 ou 0,9). La date de début d'un regroupement est le maximum des dates de 35 disponibilités des tâches qui le constituent et la durée du regroupement est le résultat d'une fonction quelconque, dépendant des tâches du regroupement, de la ressource exécutant le regroupement ainsi que de la nature du traitement effectué. La fin du regroupement est alors définie par la date de début augmentée 10 de sa durée. Un regroupement est considéré fermé si la date de fin du regroupement est antérieure à l'instant t considéré. Selon une réalisation de l'invention, l'opérateur de croisement choisi dans l'étape (e) consiste : - à conserver aléatoirement des tâches contenues dans une des deux solutions dudit couple et compléter avec les tâches contenues dans la seconde solution dans l'ordre de la seconde solution, ou - à trier les tâches par ordre décroissant de retard cumulé dans les deux solutions dudit couple, ou - à conserver à leur place les tâches sans retard dans la première solution dudit couple et à compléter dans l'ordre de la seconde solution dudit couple pour les tâches avec retard. Selon une réalisation de l'invention, ledit opérateur de mutation de l'étape (f) consiste à : - déplacer de manière aléatoire une tâche dans la solution, ou - à échanger de manière aléatoire deux tâches dans la solution, ou - à remplacer une sous-séquence de la solution par une de ses permutations choisie de manière aléatoire, ou - à trier une sous-séquence de la solution par ordre décroissant des retards des tâches, ou - à déplacer les tâches les plus en retard d'un nombre fixe de rangs vers le début de la solution, ou - à corriger la solution selon un processus répétitif de correction qui est une heuristique de liste répétitive. Selon une réalisation de l'invention, le processus itératif de correction comprend les étapes suivantes : - (i) on ordonnance la liste de tâches selon l'étape de construction (b) ; - (ii) on corrige la liste de priorité en décalant lesdites tâches en retard dans la liste selon une fonction de décalage ; - (iii) on évalue le retard maximal Tmax des tâches ; - (iv) on répète les étapes (i) à (iii) selon un nombre fixé d'itérations prédéterminé. Dans cette étape, la fonction de décalage corrige la liste de priorité déterminée à l'issue de la première étape en avançant la tâche la plus en retard en début de liste. Mais elle peut consister également à avancer les tâches en retard en début de liste ou tout autre type de date d'échéance. Le procédé d'optimisation d'ordonnancement de traitement de tâches selon l'invention permet ainsi de minimiser les retards par rapport à la date de livraison des pièces. L'invention concerne également une utilisation dudit procédé d'optimisation 5 d'ordonnancement pour ordonnancer un ensemble de tâches pour fabriquer des pièces en matériaux composites d'un aéronef. D'autres avantages et caractéristiques de l'invention apparaîtront avec la description de certains de ses modes de réalisations particuliers, cette description étant effectuée à titre non limitatif à l'aide des figures sur lesquelles : 10 - la figure 1 montre un organigramme de procédé d'optimisation d'ordonnancement de traitement de tâches selon l'invention ; - la figure 2 montre un exemple d'ordonnancement de traitement de tâches à l'issue de l'étape de tri (b) dans le cas où le nombre de pièces est égal à 4, le nombre de tâches associé à chaque pièce est égal à 3 ; 15 - la figure 3 montre une solution améliorée de la liste à l'issue d'un exemple de mutation de l'étape (f). La présente invention est particulièrement adaptée pour le procédé de fabrication de pièces en matériaux composites dont l'exécution des tâches est 20 conditionnée par un certain nombre de contraintes, telles que l'ordre de préséance, la disponibilité des ressources nécessaires à l'exécution. Le procédé de l'invention permet d'obtenir un ordonnancement du traitement des différentes tâches du procédé de fabrication qui minimise les retards par rapport à la date de livraison des pièces. 25 Selon l'invention, on peut envisager d'utiliser le procédé de l'invention pour la fabrication de pièces structurelles pour un avion. La description qui suit décrit un exemple de réalisation de l'invention pour 4 pièces en matériaux composites P1, P2, P3 et P4. Le tableau contient les temps opératoires des tâches de découpe (01), de drapage (02) et de polymérisation 30 (03). Les temps de polymérisation indiqués correspondent au cas où chacune des opérations est placée seule dans l'autoclave. Dans le cas où plusieurs opérations sont regroupées dans l'autoclave, les temps sont calculés par une fonction complexe de multiples paramètres. Le tableau 2 résume les temps associés aux différents regroupements réalisables (les regroupements qui sont irréalisables si 35 les pièces n'ont pas le même cycle autoclave, ou si les pièces ne rentrent pas physiquement ensemble dans l'autoclave n'apparaissent pas dans le tableau). Le tableau 3 contient les besoins en ressources pour exécuter chacune des tâches. Le tableau 4 indique la quantité de ressources contenues dans l'atelier. Enfin le tableau 5 contient les dates de livraison de chacune des pièces, c'est la date d'échéance. L'objectif est donc de minimiser le retard maximal par rapport à cette date. P1 P2 P3 P4 01 (Découpe) 30 10 10 20 02 (Drapage) 20 20 10 30 03 (Polymérisation) 30 40 30 40 Tableau 1 : Temps opératoires en minutes Regroupements Temps opératoires (P1,P2) 20 (P1,P3) 30 (P2,P3) 20 (Pl ,P2,P3) 40 (P2,P4) 20 (P3,P4) 20 (Pl ,P2,P4) 30 (Pl ,P3,P4) 40 (P2,P3,P4) 20 Tableau 2 : Temps opératoires des regroupements réalisables Découpe Machine de découpe Drapage Machine à draper et moule Polymérisation Autoclave et moule Tableau 3 : Besoins en ressources Ressources Quantités Machines de découpe 2 (Dec1, Dec2) Machine à draper 1 (Drap) Autoclave 2 (Auto1, Auto2) Moule 3 (Ml, M2, M3) Tableau 4 : Quantités de ressources disponibles P1 P2 P3 P4 Date de livraison 80 90 60 100 Tableau 5 : Dates de livraison Dans cet exemple, on considère que toutes les pièces suivent le même 15 processus, ce qui n'est pas forcément le cas, en outre, on suppose que les ressources sont disponibles 24h/24h et qu'une tâche ne peut attendre dans 10 l'autoclave plus de 30 unité de temps avant le démarrage de la tâche de polymérisation. De façon générale, avant la mise en oeuvre du procédé, les informations suivantes sont connues : - l'ordre de préséance dans lequel les tâches doivent être exécutées ; - le nombre total de ressources disponibles pour le traitement des tâches ; - le nombre de ressources nécessaires au traitement de chaque tâche ; - la durée nécessaire au traitement de chaque tâche ; - le nombre de pièces à réaliser ; - la durée des regroupements. La figure 1 représente un organigramme de principe du procédé d'optimisation d'ordonnancement selon l'invention. Dans une première étape du procédé, on génère de manière aléatoire un ensemble de P solutions, chacune des solutions correspondant à une liste ordonnée de toutes les tâches. Dans une seconde étape du procédé (b), à partir de chacune des solutions initiales, on construit une première solution admissible, c'est-à-dire une liste de tâches réalisable au moyen d'un processus itératif dans lequel on trie les tâches selon un paramètre de priorité en tenant compte des contraintes de préséances et de la disponibilité des ressources. Pour cela, cette seconde étape (b) comporte un premier tri dans lequel les tâches sont triées par ordre décroissant de leur durée de traitement pour former une première liste de priorité. Dans ce cas, l'ordre de priorité ainsi défini privilégie la tâche qui demande la durée de traitement la plus longue. D'autres critères de tri peuvent être également utilisés dans le cadre de l'invention, tels que le nombre de ressources nécessaires au traitement des tâches, ou la date d'échéance. Cette étape de construction d'ordonnancement (b) comporte un deuxième tri comportant n x m itérations correspondant à n x m traitements de tâches constituant une liste. A chaque itération, on recherche le plus petit instant t où une tâche peut démarrer à l'instant t et à placer à cet instant t la première tâche de la liste qui peut démarrer. Ce tri est effectué en tenant compte des contraintes de préséances et de la disponibilité des ressources. Dans le cas où la tâche sélectionnée doit être exécutée sur une ressource qui permet de regrouper plusieurs tâches, on évalue la possibilité de regrouper la tâche ainsi sélectionnée avec d'autres tâches compatible dans un regroupement existant non ordonnancé. S'il n'existe pas de regroupement pouvant recevoir la tâche, alors on crée un nouveau regroupement pour cette tâche. On entend par regroupement non ordonnancé, un regroupement qui est ouvert et qui permet d'ajouter une tâche. Ainsi selon l'étape (b) du procédé de l'invention, on trie une liste initiale contenant l'ensemble des tâches à traiter selon leur durées de traitement, on obtient une première liste de priorité suivante : (01, P2), (O1,P3), (O2,P3), (O1,P4), (O2,P1), (O2,P2), (O1,P1), (O3,P1), (O3,P3), (O2,P4), (O3,P2), (O3,P4). A partir de cette première liste, on va calculer le plus petit instant où une tâche peut démarrer, c'est-à-dire à sélectionner pour chaque type de ressource nécessaire, la ressource disponible qui permet l'exécution de la tâche le plus tôt possible. Cette étape comporte 12 itérations, correspondant à 4 pièces x 3 tâches. Les seules tâches de la liste qui peuvent être placées pour le moment dans l'exemple considéré sont les tâches sans préséance, c'est à dire (01, P2), (O1,P3), (O1,P4), (O1,P1). La date de démarrage au plus tôt de chacune de ces tâches est 0 (car toutes les ressources ou machines sont disponibles). On ordonnance donc à l'instant t = 0 la tâche la plus prioritaire parmi ces tâches, c'est-à-dire (O1,P2). Cette tâche nécessite une machine de découpe. Cette première itération permet d'affecter (01, P2) sur Dec1 par exemple puisque les deux machines sont disponibles à la même date. La liste contient maintenant une tâche de moins à ordonnancer : (O1,P3), (02,P3), (01,P4), (02,P1), (02,P2), (O1,P1), (03,P1), (03,P3), (02,P4), (03,P2), (O3,P4). Les tâches pouvant être placées à cette étape sont toutes les tâches sans prédécesseurs, c'est-à-dire les tâches (O1,P3), (O1,P4) et (O1,P1) ainsi que les tâches dont tous les prédécesseurs sont placés, c'est-à-dire : (O2,P2) Les dates de démarrage au plus tôt de ces tâches sont t = 0 pour (O1,P3), (O1,P4) et (O1,P1) (chacune de ces tâches peut en effet être exécutée sur la ressource Dec2 qui est disponible à l'instant 0), et 10 pour la tâche (O2,P2) (date de fin de son prédécesseur (O2,P1)). Parmi les tâches pouvant démarrer le plus tôt (à la date 0), la tâche (O1,P3) est la plus prioritaire, on la place donc à l'instant 0 sur la machine Dec2. La liste contient maintenant les tâches suivantes : (O2,P3), (O1,P4), (O2,P1), (O2,P2), (O1,P1), (O3,P1), (O3,P3), (O2,P4), (O3,P2), (O3,P4) Les tâches pouvant être placées à cette étape sont (O2,P3), (O1,P4), (O2,P2) et (O1,P1). Ces tâches peuvent démarrer au plus tôt respectivement aux instants 10 (date de fin de la tâche (O1,P3)), 10 (date de disponibilité des machines de découpe), 10 (date de fin de la tâche (O1,P2)) et 10 (date de disponibilité des machines de découpe) On place donc à l'instant 10 la tâche la plus prioritaire, c'est-à-dire (O2,P3) sur la machine de drapage et en utilisant l'un des 3 moules disponibles, par exemple M1, ce moule est alors réservé pour les tâches suivantes de la pièce P3 qui nécessitent un moule (O3,P3). La liste contient maintenant les tâches suivantes : (O1,P4), (O2,P1), (O2,P2), (O1,P1), (O3,P1), (O3,P3), (O2,P4), (O3,P2), (O3,P4). Les tâches pouvant être placées à cette étape sont (O1,P4), (O2,P2), (O1,P1) et (O3,P3). Ces tâches peuvent démarrer au plus tôt respectivement aux instants 10, 20, 10 et 20. On place donc à l'instant 10 sur la machine Dec1 la tâche la plus prioritaire, c'est-à-dire (O1,P4). La liste contient maintenant les tâches suivantes : (O2,P1), (O2,P2), (O1,P1), (O3,P1), (O3,P3), (O2,P4), (O3,P2), (O3,P4). Les tâches pouvant être placées à cette étape sont (O2,P2), (O1,P1), (O3,P3) et (O2,P4). Ces tâches peuvent démarrer au plus tôt respectivement aux instants 20, 10, 20 et 30. On place donc à l'instant 10 la tâche la plus prioritaire, c'est-à-dire (O1,P1), sur la machine Dec2. La liste contient maintenant les tâches suivantes : (O2,P1), (O2,P2), (O3,P1), (O3,P3), (O2,P4), (O3,P2), (O3,P4). Les tâches pouvant être placées à cette étape sont (O2,P1), (O2,P2), (O3,P3) et (O2,P4). Ces tâches peuvent démarrer au plus tôt respectivement aux instants 40, 20, 20 et 30. La tâche libre au plus petit instant et la plus prioritaire est (O2,P2). On la place à l'instant 20 sur la machine Drap en utilisant l'un des 2 moules restant disponibles, par exemple M2, ce moule est alors réservé pour les tâches suivantes de la pièce P2 qui nécessitent un moule (O3,P2). La liste contient maintenant les tâches suivantes : (O2,P1), (O3,P1), (O3,P3), (O2,P4), (O3,P2), (O3,P4). Les tâches pouvant être placées à cette étape sont (O2,P1), (O3,P3), (O2,P4) et (O3,P2). Ces tâches peuvent démarrer au plus tôt respectivement aux instants 40, 20, 40 et 40. On place alors la tâche (O3,P3) à l'instant 20 sur la machine Autol en utilisant le moule M1 qui est déjà réservé pour la tâche (O3,P3). On suppose pour le moment qu'elle est seule dans l'autoclave et que donc son temps d'exécution est 30. La liste contient maintenant les tâches suivantes : (O2,P1), (O3,P1), (O2,P4), (O3,P2), (O3,P4). Les tâches pouvant être placées à cette étape sont (O2,P1), (O2,P4) et (O3,P2) Ces tâches peuvent démarrer au plus tôt respectivement aux instants 40, 40 et 40. On place donc à l'instant 40 la tâche la plus prioritaire, c'est-à-dire (02,P1), sur la machine Drap en utilisant le dernier moule non réservé, M3. La liste contient maintenant les tâches suivantes : (O3,P1), (O2,P4), (O3,P2), (O3,P4). Les tâches pouvant être placées à cette étape sont (O3,P1), (O2,P4) et (O3,P2). Ces tâches peuvent démarrer au plus tôt respectivement aux instants 60, 60 et 40. On place donc à l'instant 40 la tâche (O3,P2) dans un autoclave. On regarde d'abord si cette tâche peut être ajoutée dans l'autoclave Autol avec la tâche (O3,P3). Dans ce cas, le regroupement ((O3,P3),(O3,P2)) démarre à l'instant 40 et dure 20 d'après le tableau 3. La tâche (O3,P3) attend alors 20 unités de temps, ce qui est inférieur au seuil d'acceptabilité prédéterminé, à savoir qu'une tâche ne peut attendre dans l'autoclave plus de 30 unités de temps avant le démarrage de la tâche de polymérisation. La tâche est donc ajoutée dans l'autoclave Autol avec le moule réservé à cette tâche M2. La liste contient maintenant les tâches suivantes : (O3,P1), (O2,P4), (O3,P4). Les tâches pouvant être placées à cette étape sont (O3,P1) et (O2,P4). Ces tâches peuvent démarrer au plus tôt respectivement aux instants 60 et 60 On place donc à l'instant 60 dans un autoclave la tâche la plus prioritaire, c'est-à-dire (03,P1). Si la tâche est ajoutée dans l'autoclave Autol avec les tâches (O3,P3) et (O3,P2), le regroupement démarre à l'instant 60 et dure 40 d'après le tableau 3, dans ce cas la tâche (O3,P3) doit alors attendre 40 unités de temps, ce qui est supérieur à la durée d'attente maximale qui a été fixée à 30. La tâche est donc ajoutée dans l'autoclave Auto2, et puisque qu'elle est seule pour le moment dans l'autoclave, elle dure 30. On utilise pour cette tâche le moule M3. La liste contient maintenant les tâches suivantes : (O2,P4), (O3,P4). La seule tâche pouvant être placée à cette étape est (O2,P4). Elle peut démarrer au plus tôt à l'instant 60. On la place donc à l'instant 60 sur la machine Drap en utilisant le moule M2 par exemple. De plus, la tâche de Autol regroupant les pièces P3 et P2 se termine à l'instant 60, ce qui est inférieur ou égal à l'instant courant qui vaut 60. On peut donc � fermer � ce regroupement, c'est-à-dire considérer qu'aucune tâche ne pourra y être ajoutée. Les pièces P3 et P2 étant terminées, les moules M1 et M2 sont � libérés � et peuvent à nouveau servir pour des tâches d'autres pièces. La liste ne contient plus que la tâche (O3,P4), dont la date de démarrage au plus tôt est 90. Cette tâche ne peut pas être ajoutée dans l'autoclave Autol avec les tâches (O3,P3) et (O3,P2) puisque le regroupement vient d'être � fermé �. Elle ne peut pas non plus être regroupée avec la tâche (O3,P1) car sinon cette dernière doit attendre trop longtemps (plus de 30 unités de temps). On place (03, P4) donc sur Autol (par exemple). Elle démarre alors à l'instant 90 et dure 40 unités de temps. La figure 2 représente un graphe dont l'axe X représente l'unité de temps, et l'axe Y les différentes ressources. Ce graphe résume un premier ordonnancement obtenu à l'issue de cette première étape de tri décrit ci-dessus. Les étapes (a) et (b) telles que décrites ci-dessus constituent une phase d'initialisation, au cours de laquelle on construit un ensemble de solutions initiales admissibles à l'aide d'une heuristique de liste. Dans une seconde phase qui est une phase itérative, on génère à l'aide d'une méthode recherche de solutions optimales de type algorithme génétique à partir des solutions admissibles. A une itération donnée, on dispose donc d'une population P de solutions, ou individus représentés par une permutation des tâches dont l'ordonnancement correspondant est obtenu par l'heuristique de liste. A chaque individu est associé une valeur de qualité déterminée selon le principe de l'adaptation linéaire, (c) : les individus sont triés selon le retard maximum de l'ordonnancement qu'ils induisent et dans un ordre décroissant. Ce classement des individus selon leur performance permet de bien différencier les individus ayant des valeurs proches, et ainsi de concentrer sur ceux qui sont les meilleurs. Dans le cas où deux individus ont le même retard maximum, on privilégie l'individu qui minimise la somme des retards induits. On sélectionne P couples de solutions ou parents de manière aléatoire et dont la probabilité d'être sélectionné est proportionnelle à sa valeur de qualité affectée (étape (d)). Ces couples de solutions sont utilisés pour être croisés (étape (e)) et mutés (étape (f)) pour obtenir une nouvelle génération de P solutions. On passe à l'itération suivante dans laquelle on recommence avec la nouvelle génération de P solutions qui remplace les solutions initiales de l'étape (a). Le processus itératif des étapes (b) à (f) s'achève lorsqu'un nombre maximal d'itérations est atteint. De cette façon, cette optimisation successive améliore progressivement la qualité de la solution initiale de sorte que la solution finale soit de très bonne qualité. De manière générale, la taille de la population (P), le nombre maximal d'itérations sont des paramètres à régler expérimentalement. Leurs valeurs ne doivent pas être trop élevées afin que le problème puisse être résolu dans un temps d'exécution relativement raisonnable, ni trop petite pour l'obtention d'une solution finale de bonne qualité. De même, seuls les résultats expérimentaux permettent de déterminer les opérateurs à privilégier, ainsi que les taux de mutation et/ou croisement à appliquer. Afin d'illustrer les opérateurs de croisement et les opérateurs de mutations, on considère ici un exemple de couple de solutions sélectionnées présentées sous la forme suivante (entre [ ] indique le retard de la tâche) : - L1 : Ti [0], T2[0], T3[1 ],T4[0],T5[2],T6[1 ],T7[3],T8[4],T9[4],T10[3],T11 [7],T12[8] - L2 : T3[0], T6[0], T12[1 ],T10[0],T2[2],T1 [1 ],T8[3],T9[4],T4[4],T11 [4],T7[5],T5[7] On décrit ci-dessus les différents opérateurs de croisement sur le couple de solutions : - on conserve par exemple aléatoirement des tâches dans L1 et on complète avec les tâches manquantes contenues dans L2 dans l'ordre de L2 ; - on trie par retard cumulé décroissant, la nouvelle solution ainsi générée est de la forme suivantes : T11, T5, T12, T7, T9, T8, T4, T10, T2, Ti, T3, T6 ; - on conserve à leur place les tâches sans retard dans L1 et on complète avec les tâches de L2 dans l'ordre de L2, pour les tâches avec retard. On décrit ci-dessus les différents opérateurs de mutations appliqués sur L1 : - déplacement aléatoire d'une tâche dans la liste, par exemple en déplaçant T5 après Tl0; - échange aléatoire de deux tâches dans la liste, par exemple en 30 échangeant T2 et T7 ; - remplacement d'une sous-séquence de la liste par une de ses permutations, par exemple en permutant le sous-séquence T4, T5, T6, T7 et T8 en T7, T4, T6, T5, T8 ; - tri d'une sous-séquence de la liste par ordre décroisssant des retards des 35 tâches ; par exemple en triant la sous-séquence T5, T6, T7, T8, T9 qui donne T8, T9, T7, T10, T5, T6 ; - déplacement d'un nombre fixe de k rangs vers le début de la liste des n tâches les plus en retard ; on obtient par exemple, pour n = 4 et k = 2, une nouvelle liste : Ti, T2, T3, T4, T5, T8, T9, T6, T11, T12, T7, T10 ; - optimisation locale par application d'une heuristique de liste répétitive qui est un processus itératif de correction. Ce processus itératif de correction comporte les étapes suivantes : : - (i) on ordonnance la liste de tâches de nouveau selon l'étape de construction (b) - (ii) on corrige la liste de priorité en décalant lesdites tâches en retard dans la liste selon une fonction de décalage ; - (iii) on évalue le retard maximal Tmax des tâches ; - (iv) on répète les étapes (i) à (iii) selon un nombre fixé d'itérations prédéterminé. Dans cette étape, la fonction de décalage corrige la liste de priorité déterminée à l'issue de la première étape en avançant la tâche la plus en retard en début de liste. Mais elle peut consister également à avancer les tâches en retard en début de liste. On décrit ci-dessus une solution améliorée après avoir appliqué le processus de correction. Les tâches en retard de la solution obtenue à l'issue de l'étape (b) décrit ci- dessus sont : (O1,P1), (O2,P1), (O3,P1), (O2,P4) et (O3,P4). Le processus de correction selon l'invention consiste à corriger cette première solution, c'est-à-dire à améliorer cette solution. Les tâches en retard sont avancées toutes au début de la liste, en conservant leur ordre relatif, une nouvelle liste corrigée est ainsi obtenue : (O1,P1), (O2,P1), (O3,P1), (O2,P4), (O3,P4), (O1,P2), (O1,P3), (O2,P3), (O1,P4), (O2,P2), (O3,P3), (O3,P2). En exécutant de nouveau l'étape (b) à partir de cette liste corrigée, nous obtenons la solution suivante construite en ordonnançant les tâches dans cet ordre de priorité : (O1,P1), (O1,P2), (O1,P3), (O2,P3), (O1,P4), (O2,P1), (O3,P3), (O3,P1), (O2,P4), (O3,P4), (O2,P2) et (O3,P2). Cette nouvelle liste corrigée est représentée sur la figure 3. Nous pouvons alors de nouveau rechercher toutes les tâches en retard qui sont maintenant (01,P2), (02, P2), (03, P2), (01, P3), (02, P3) et (03, P3).et les placer en début de liste. Ainsi le processus est répété tant que l'on trouve une solution améliorante, c'est-à-dire tant que la valeur du retard maximal Tmax des tâches dans la solution trouvée est supérieure à une valeur Tmax* prédéterminée. Lorsque la valeur Tmax trouvée est égale à la valeur Tmax* prédéterminée, le processus itératif est arrêté. REVENDICATIONS1. Procédé d'optimisation d'ordonnancement de traitement d'un ensemble de tâches pour fabriquer n pièces, chaque pièce étant définie par un cycle de fabrication propre à la pièce et une date d'échéance, ledit cycle comportant un nombre fixe de m tâches, l'exécution de chacune des tâches étant conditionnée par un ordre de préséance et la disponibilité des ressources nécessaires à l'exécution de ladite tâche, caractérisé en ce que ledit procédé comprend les étapes suivantes dans lesquelles : a) on génère aléatoirement un ensemble de P solutions initiales, chacune des solutions correspondant à une liste contenant les tâches destinées à être ordonnancées pour fabriquer les n pièces ; b) on construit une première solution admissible à partir de chacune des listes au moyen d'un processus itératif dans lequel on trie les tâches selon un paramètre de priorité en tenant compte de la disponibilité des ressources et des préséances à respecter ; c) on affecte à chacune des premières solutions une valeur de qualité correspondant au plus grand retard d'une tâche dans l'ordonnancement obtenu à l'étape (b) de manière à classer les solutions selon un ordre décroissant de valeur de qualité ; d) on sélectionne P couples de solutions dont la probabilité d'être sélectionnée est proportionnelle à la qualité de la solution ; e) on applique un opérateur de croisement sur chacun des P couples de solutions sélectionnés pour générer une nouvelle solution fille ; f) on applique un opérateur de mutation sur chacune des P solutions filles générées à l'étape (e) ; g) on remplace l'ensemble des P solutions initiales de l'étape a) par l'ensemble des P solutions générées à l'issue de l'étape f) ; h) on répète les étapes b) à f) de manière itérative, le nombre d'itérations étant fixé préalablement. 2. Procédé d'optimisation d'ordonnancement de traitement de tâches selon la revendication 1, caractérisé en ce que l'étape de construction de première solution admissible (b) comporte : - un premier tri selon une valeur propre des tâches de sorte que les tâches soient traitées selon un ordre décroissant ou croissant de leur valeur propre, et- un deuxième tri comportant n x m itérations correspondant à n x m traitements de tâches constituant la liste, chacune des itérations consistant : - à rechercher le plus petit instant t où une tâche peut démarrer en tenant compte de la disponibilité des ressources et des préséances à respecter, - à placer à cet instant t la première tâche de la liste qui peut démarrer à t, - dans le cas où ladite tâche sélectionnée doit être exécutée sur une ressource pouvant regrouper plusieurs tâches, à regrouper ladite tâche avec d'autres tâches compatibles dans un regroupement existant qui n'est pas encore ordonnancé dans la liste ou à créer un nouveau regroupement pour placer ladite tâche. 15 3. Procédé d'optimisation d'ordonnancement de traitement de tâches selon la revendication 2, caractérisé en ce qu'un regroupement est ordonnancé dans la liste lorsque la durée de l'attente du regroupement est supérieur à un seuil d'acceptabilité prédéterminé, ladite durée correspondant au temps maximum nécessaire pour que l'ensemble des pièces contenues dans le regroupement 20 soient prêtes pour l'exécution de la tâche 4. Procédé d'optimisation d'ordonnancement de traitement de tâches selon la revendication 2, caractérisé en ce qu'un regroupement est ordonnancé dans la liste lorsque la date de fin du regroupement est antérieure à l'instant t considéré. 5. Procédé d'optimisation d'ordonnancement de traitement de tâches selon l'une des revendications 2 à 4, caractérisé en ce que ladite valeur propre des tâches est la durée d'exécution des tâches, ou le nombre de ressources nécessaires au traitement des tâches, ou la date d'échéance. 6. Procédé d'optimisation d'ordonnancement de traitement de tâches selon l'une des revendications 1 à 5, caractérisé en ce que ledit opérateur de croisement consiste : - à conserver aléatoirement des tâches contenues dans une des deux solutions dudit couple et compléter avec les tâches contenues dans la seconde solution dans l'ordre de la seconde solution, ou - à trier les tâches par ordre décroissant de retard cumulé dans les deux solutions dudit couple, ou 10 25 30 35- à conserver à leur place les tâches sans retard dans la première solution dudit couple et à compléter dans l'ordre de la seconde solution dudit couple pour les tâches avec retard. 7. Procédé d'optimisation d'ordonnancement de traitement de tâches selon l'une des revendications 1 à 5, caractérisé en ce que ledit opérateur de mutation consiste à : - déplacer de manière aléatoire une tâche dans la solution, ou - à échanger de manière aléatoire deux tâches dans la solution, ou - à remplacer une sous-séquence de la solution par une de ses permutations choisie de manière aléatoire, ou - à trier une sous-séquence de la solution par ordre décroissant des retards des tâches, ou - à déplacer les tâches les plus en retard d'un nombre fixe de rangs vers le début de la solution, ou - à corriger la solution selon un processus répétitif de correction. 8. Procédé d'optimisation d'ordonnancement de traitement de tâches selon la revendication 7, caractérisé en ce que ledit processus répétitif de correction 20 comprend les étapes suivantes : - (i) on ordonnance la liste de tâches selon l'étape de tri (b) ; - (ii) on corrige la liste de tâches en décalant les tâches en retard dans la liste selon une fonction de décalage ; - (iii) on évalue le retard maximal Tmax des tâches ; 25 - (iv) on répète les étapes (i) à (iii) selon un nombre fixe prédéterminé. 9. Procédé d'optimisation d'ordonnancement de traitement de tâches selon la revendication 8, caractérisé en ce que ladite fonction de décalage consiste à placer la tâche ayant le retard maximal parmi les tâches en retard en début de 30 liste, ou d'avancer toutes les tâches en retard en début de liste. 10. Utilisation dudit procédé d'optimisation selon l'une quelconque des revendications 1 à 9 pour ordonnancer un ensemble de tâches pour fabriquer des pièces en matériaux composites d'un aéronef. 35