Proposition d'un algorithme génétique pour résoudre un problème particulier d'ordonnancement.

je n'arrive pas à insérer une figureInternational audienceOn se propose d'ordonnancer n processus entre lesquels existent des contraintes temporelles et de ressouces telles que : avant, commence-comme, finit-comme, commence-quand-finit, inclut et disjoint-de. Chaque processus a sa propre durée et est muni d'une fenêtre de temps dans laquelle il est censé être exécuté. Notre objectif est d'ordonnancer ces processus avec le moindre retard à l'aide d'un algorithme génétique. Ce problème se pose quotidiennement dans les ateliers du complexe sidérurgique ARCELOR (Annaba-Algerie). L'espace des solutions possibles étant infiniment grand, il est donc impossible d'utiliser une méthode "exhaustive" de recherche des positions optimales en énumérant toutes les possibilités d'ordonnancement et en les comparant pour trouver la meilleure. Nous définissons un mode de sélection, de croisement et de mutation qui amoindrit la violation des contraintes. Notre fonction d'évaluation est constituée d'un amalgame de la mesure de violations des contraintes et de notre objectif principal, à savoir, la minimisation du retard global. Afin de visualiser l'évolution des performances de notre algorithme, nous calculons, à chaque génération, la valeur de la fonction d'adaptation de la meilleure solution trouvée ainsi que la moyenne des valeurs d'adaptation de tous les individus. Les évolutions de ces deux valeurs sont représentées par les deux courbes de la figure suivante. Dans ce graphe, nous remarquons que la fonction d'adaptation des meilleurs individus cesse de diminuer à partir de la génération 400, et la courbe relative à l'évolution des valeurs moyennes de la fonction d'adaptation a tendance à se rapprocher de celle représentant l'évolution de la fonction d'adaptation de l'individu le plus adapté. Ceci correspond à une uniformisation croissante de la population c'est à dire à une convergence de notre algorithme. Celui-ci converge au détriment d'un temps qui, même s'il est élevé, reste dans la limite de l'acceptable.