La planification opérationnelle (ordonnancement)

Ordonnancement de la production

L'ordonnancement est la phase de planification la plus proche de l'atelier. Ordonnancer consiste à organiser dans le temps de manière plus ou moins précise la réalisation des travaux prévus dans la phase de planification tactique, en utilisant les ressources mises à disposition.

La représentation d'un ordonnancement

L'ordonnancement de la production est une planification détaillée de la succession des tâches des différents ordres de fabrication sur les machines (ou autres ressources).Pour communiquer cette planification, il faut la représenter.
Le diagramme Gantt, en anglais GANTT CHART est l'outil le plus utilisé. On le trouve aussi sous les noms de tableau mural ou diagramme à gouttière. On trouve plus rarement un diagramme de type "line balance chart".

Diagramme Gantt


Ce diagramme représente généralement :
  • Le temps en abscisse
  • Les différentes ressources en ordonnée
  • chaque Ordre de fabrication est décomposé en autant de "barres" de la même couleur que de tâche, de longueur proportionnelle à la durée de la tâche,
  • Chaque ligne (ressource) contient la succession des tâches devant être faites sur cette ressource,
  • Une symbolique particulière représente les zones durant lesquelles les ressources sont "inactives",
  • Une ligne verticale permet de visualiser la date courante.

Dans l'exemple suivant, les zones non travaillées sont en rose, il y a 4 ordres de fabrication (un par couleur) et ils ont chacun 4 opérations distinctes.

Le diagramme de Gantt a beaucoup d'avantage, mais:
  • Il ne permet pas de visualiser les travaux en attente d'une machine.
  • Il ne permet pas de voir l'encours de production.

En effet, pour visualiser les travaux en attente, il faudrait sélectionner une date et extraire du diagramme les ordres de fabrication en attente de chacune des machines.
Ce qui est assez facile, c'est d'extraire un ordre de fabrication et de ne représenter que celui ci. On met ainsi en évidence les attentes de cet ordre.

  • Il ne permet pas facilement de visualiser la situation actuelle

Il est facile de tracer une ligne verticale pour modéliser la date actuelle (dans l'univers de la planification) , mais il faut compléter avec une visualisation de la situation réelle à cette date. Dans la réalité, certaines tâches sont commencées mais non finies, certaines tâches ont été inversées, etc.

Dans cet exemple simple, la seconde machine est un peu en avance, la troisième un peu en retard.
De fait, le diagramme Gantt dans sa partie visuelle met l'accent sur un taux de charge important de chacune des ressource. Ce qui saute aux yeux, c'est la densité sur chaque ligne. Il favorise donc l'engagement des ressources au détriment de l'encours et des attentes.

Line Balance Chart


Au départ, ce type de diagramme est principalement utilisé en génie civil, pour montrer l'avancement de projets répétitifs, comme l'aménagement d'un ensemble d'appartement, la construction d'un ensemble de maisons, etc. Il est composé de :
  • En abscisse, le temps,
  • En ordonné, les projets (ou produits, ou étages, ou lieux) sur lesquels doivent se faire une succession d'opérations (ici 4 produits par exemple)
  • Chaque ligne bleu représente une opération (ou une étape) devant être faite sur chaque projets ou produits. Cette droite donne la période prévue pour chaque du projet,
  • Chaque opération est aussi associée à une courbe représentant le réalisé pour chaque projet (lignes rouges sur le schéma).

Ce type de diagramme peut cependant très bien être utilisé sur des productions par projet avec des projets de même nature (fabrication d'un ensemble de bateaux, fabrication de plusieurs bus, etc.) ou pour des lignes d'assemblage complexes.
Le diagramme suivant représente exactement le déroulement des 4 ordres de fabrication en utilisant un line balance chart. Les lignes en bleu sont le prévu, celle en rouge le réalisé.

Chacune des 4 machines, correspondant ici à une étape de la production des Ordres de fabrication est représenté par une ligne bleu épaisse. La ligne rouge représente le suivi de la production. Pour suivre un ordre de fabrication, il suffit de lire une ligne horizontale.
On voit que la machine 3 (le procédé correspondant) est en retard parce qu'elle a commencé avec du retard. On voit aussi que la machine 1 avait pris du retard, mais le rattrape.
Dans le cadre du génie civil, les courbes bleues (prévisions) sont généralement des droites, car une étapes prend le même temps quelque soit le projet.

L'avantage de cette représentation est de représenter visuellement le planifié et le réalisé pour chaque projet et chaque étape.

Les données manipulées en ordonnancement

Le niveau de planification supérieur a défini des ordres de fabrication ( OF) à réaliser durant certaines périodes de temps (soit les OF). Ces OF correspondent à certaines informations :

  • Le produit à fabriquer,
  • la quantité de produit devant être fabriqué,
  • quelques fois une périodes de temps à l'intérieur de laquelle il doit être fabriqué,
  • quelques fois une date de début au plus tôt et ou des dates de fin au plus tard,
  • Quelques fois une priorité.

Cet OF pointant sur un produit, à partir de la référence du produit (et de la quantité à fabriquer), de sa gamme de fabrication et de la description des opérations de la gamme, on peut créer la gamme de l'ordre de fabrication.
La gamme de l'OF est composée

  • de la liste des tâches à effectuer (une par opération)
  • Chaque tâche est décrite par la machine ou le type de machine nécessaire, sa durée opératoire, et quelques fois des dates de début au plus tôt et de fin au plus tard
  • de l'ordre des tâches.

De fait, dans beaucoup de systèmes informatiques, lors de la création d'un ordre de fabrication, on duplique la gamme du produit afin de pouvoir modifier localement cette gamme sans toucher à la gamme mère.

Typologie des modèles théoriques

On peut dater les débuts de l'ordonnancement théorique dans les années 60, avec entre autre le remarquable ouvrage de Conway qui synthétise la connaissance de l'époque (Conway 67). Les ouvrages se sont ensuite multipliés, ainsi que les articles et autres communications. En ordonnancement d'atelier, il est d'usage (depuis Graham et al. 79) de classer les outils et méthodes utilisées en fonction:
  • De l'organisation de l'atelier,
  • Des contraintes spécifiques,
  • Du (ou des) critères étudiés.

Ces trois champs permettent de caractériser la difficulté du problème, le type de méthode à utiliser ainsi qu'à retrouver les travaux antérieurs.

Notations


Les notations sont pour la plupart issues des termes anglais. Elles sont pourtant unanimement utilisées:
  • [math]i[/math] Indice des jobs
    [math]j[/math] Indice des machines,
  • [math]p_{i,j}[/math] Durée de l'opération faite pour le job [math]i[/math] sur la machine [math]j[/math],
  • [math]s_{i,j}[/math] Date de début (Starting date)de la tâche [math](i,j)[/math],
  • [math]c_{i,j}[/math] Date de fin (Completion date) de la tâche [math](i,j)[/math],
  • [math]r_{i,j}[/math] Date de début au plus tôt (Release date) de la tâche [math](i,j)[/math],
  • [math]d_{i,j}[/math] Date de fin au plus tard (Due date) de la tâche [math](i,j)[/math]

      Type d'organisation de l'atelier

      On distingue les familles de problèmes suivant :

      • Mono machine (une seule machine)
      • Machines parallèles,
        • identiques (durées des opérations indépendantes de la machine),
        • proportionnelles (durées d'une machine à l'autre proportionnelles)
        • quelconques (durées variant d'une machine à l'autre

      • Flow Shop (machine en ligne)
        • Normal, une machine par étage,
        • hybride, avec plusieurs machines par étage

      • Job Shop (chaque ordre a son propre cheminement
      • Open Shop (chaque Job doit faire n travaux sur n machines, mais dans n'importe quel ordre

      La majeure partie de travaux de recherche dans le domaine porte sur le problème Flow-Shop ou le problème de machines parallèles. En gestion de la fabrication, on retrouve des types d'atelier dans lesquels chacun de ces modèles peut se retrouver :
      atelier Exemple d'atelier
      mono machine une entreprise qui opère une ligne de production en flux peut être assimilée à une machine unique : cas d'une ligne de fabrication de bouteilles de verre.
      Machines parallèles Atelier d'injection avec 10 presses à injecter en parallèle,
      Flow shop beaucoup de procédés mécaniques, des lignes de machines (indépendantes)
      Job Shop Atelier mécanique, avec des machines très différentes
      open shop Ensemble de tests, procédés de vérification ou de diagnostique demandant de multiples analyses

      Les problèmes de flow-shop se divisent encore en deux cas, selon que l'on impose un ordre de passage identique sur chaque machine (on parle de Flow-shop de permutation, car une solution se ramène à une permutation des Jobs) ou que l'on accepte que les produits se doublent. Lorsque les produits se doublent, les problèmes sont plus difficiles à résoudre (et surtout beaucoup moins étudiés).

      On utilise souvent le modèle du Flow shop, même si les jobs n'ont pas autant de tâches (donc d'opérations) qu'il n'y a de machines. On introduit alors des tâches de durées nulles. Ce modèle est évidement correct, mais il est alors pénalisant de se limiter aux flow shops de permutation, car un Job n'ayant pas de tâche sur une machine reste bloqué en attente de cette machine, pour une tâche de durée nulle.

      En dehors de cette typologie de base, on parle aussi de re-circulation lorsqu'un job peut passer plusieurs fois sur la même machine

      Contraintes spécifiques

      Les contraintes principales portent sur


      • les contraintes d'antécédence entre tâches
        • Graphe des d'antécédence ayant une structure d'arbre ou de chaînes
        • Contrainte de délais minimum ou maximum entre tâches
        • Contrainte sur les attentes entre tâches

      • Contraintes de dates:
        • Due date (date d'échéance)
        • Release date (date de disponibilité)

      • Les contraintes de ressources:
        • Ressources disjonctives (ressources utilisées exclusivement par un job),
        • Ressources cumulatives (consommées en quantité, comme l'argent par exemple).

      Il peut aussi y avoir des contraintes de temps de réglages, uniforme ou dépendant de la séquence. Il peut y avoir des contraintes d'outillage, d'outil, etc...

      Critères étudiés


      Ordonnancer, c'est choisir une planification détaillée des tâches sur les ressources. Le choix se fait en fonction de certains critères d'évaluation.
      Notation :

      • [math]c_{i,j}[/math] Date de fin (Completion date) de la tâche [math](i,j)[/math],
      • [math]L_{i}=C_i - d_i[/math] Écart (Lateness) du job [math]i[/math],
      • [math]T_{i}=max(0,C_i - d_i)[/math] retard (Tardiness) du job [math]i[/math],

      On distingue généralement deux types de critère:

      • liés à la date de fin du travail
        • Cmax = date de fin de la dernière tâche sur la dernière ressource
        • Cbarre (pour [math]\overline C[/math]) somme (ou moyenne, ce qui est donne le même résultat) des dates de fin des jobs

      • Liés au retard (lorsqu'il y a des dates d'échéances)
        • Lmax, soit l'écart maximum au date de fin
        • Tmax, soit le retard maximum,
        • Tbarre (pour[math]\overline T[/math]) Somme des retards,
        • Nombre de retards

      Il n'y a pas grand écart entre une contrainte et un critère. Souvent, les dates d'échéance sont plus des critères que des contraintes. Cela signifie qu'elles ont été définies dans cet objectif.

      Références


      Blazewicz, J., Lenstra, J.K. and Rinnooy Kan, A.H.G., 1983. Scheduling subject to resource constraints: Classification and complexity. Discrete Applied Mathematics 5 1, pp. 11–24.
      Brucker, P., 1995. Scheduling Algorithms, Springer, Berlin.
      Conway R., Maxwell, W., Miller, L. (1967), Theory of Scheduling, Addison-Wesley, Reading, MA.,
      Graham et al., 1979. R.L. Graham, E.L. Lawler, J.K. Lenstra and A.H.G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: A survey. Ann. Discrete Mathematics 5 (1979), pp. 287–326.
      Pinedo, M., Chao, X. (1999), Operations Scheduling with Applications in Manufacturing and Services, McGraw-Hill, New York, NY,

Les différentes approches de résolution en ordonnancement

En ordonnancement d'atelier, on peut soit utiliser un logiciel du marché, soit développer un outil logiciel, soit utiliser des règles manuelles simple. Quel que soit l'outil utilisé, il y a quelques grandes familles d'approches :

L'approche "échéancier/ordres de fabrication"

Cette approche est basée sur la notion "d'ordres de fabrication" quelques fois appelés Jobs ou travaux. Chaque ordre de fabrication est composé de plusieurs tâches élémentaires, chacune devant être faite sur une machine donnée.
L'idée de base est de gérer dynamiquement un échéancier (ou planning, ou diagramme Gantt). Les Ordres de fabrications sont classés avec une règle de priorité donnée, puis ils sont pris l'un après l'autre et placés dans l'échéancier. Les décisions à prendre dans cette approche sont :
  • Comment classer les ordres de fabrication initialement,
  • Comment placer un nouvel ordre de fabrication dans l'échéancier

Le plus souvent, lorsque cette méthode est utilisée, on ne dispose pas de l'ensemble des ordres de fabrication, et on place les ordres de fabrication dans l'échéancier au fur et à mesure qu'on en a connaissance. On peut utiliser cette approche dans une PME pour donner une date à un client faisant une demande spéciale (mais dans ce cas, il n'y a pas de planification stratégique). Si l'ensemble des ordres de fabrication est connu, on peut choisir de classer les ordres de fabrication par dates de disponibilité ou par dates d'échéance croissantes.
Pour ce qui est de placer les ordres dans l'échéancier dynamique, on peut soit les placer au plus tôt, soit les placer au plus tard.

Inconvénient de cette approche :
La solution résultante est souvent de mauvaise qualité. À chaque étape on prend des décisions sans tenir compte des ordres de fabrication qui suivent et on génère des "trous" dans l'échéancier de tailles trop faibles pour être utilisés et ce sont des plages de temps perdues.
Avantage de cette approche
Il y en a peu. Les seuls que l'on peut voir, c'est que cette méthode s'adapte bien à un traitement manuel (on rajoute sur un tableau mural les ordres de fabrication les uns après les autres) et qu'elle est la seule à s'adapter au cas d'une PME qui reçoit les ordres de fabrication "au fil de l'eau" et doit donner des dates de livraison en temps réel.
Améliorations possibles de cette approche
La première amélioration consiste à mixer les approches placement au plus tôt et au plus tard. Si le placement des tâches se fait au plus tôt, en partant de la date de disponibilité [math]r_i [/math]de l'ordre de fabrication [math]i [/math], le placement de l'ordre permet de déterminer sa date de fin planifiée [math]d_i [/math] . On peut alors retirer l'ordre de l'échéancier et le replacer au plus tard, à partir de cette date de fin [math]d_i [/math]. En faisant cela, on obtient une date nouvelle date de début [math]r^'_i [/math] qui est telle que [math]r_i<=r^'_i [/math]. Cette solution diminue donc l'encours moyen. Évidement, on peut inverser et commencer par un placement au plus tard suivi d'un placement au plus tôt.
La seconde amélioration consiste à appliquer périodiquement un algorithme de type "ramasse miette" qui va légèrement décaler les tâches afin de fusionner plusieurs "petits trous" de l'échéancier, inutilisables (car de durée inférieure à la durée d'une tâche) pour en faire des trous exploitables.

L'approche par simulation en utilisant des règles de priorité

Cette approche est basée sur une simulation à évènement discret. Le principe consiste à remplir l'échéancier en suivant l'évolution du temps. À chaque étape de la simulation, on regarde la première machine qui se libère. Pour cette machine, on cherche la liste de toutes les tâches qu'elle peut faire, on classe ces tâches avec une règle de priorité, on place la première tâche et on passe à l'évènement suivants.
Les principales règles utilisées sont:
FIFO : First In First Out
Les tâches sont classées dans leur ordre d'arrivée, soit par ordre de fin de la tâche précédente croissante. Cette règle se traduit simplement par la gestion de file d'attente.

EDD : Earliest due date
Les tâches sont classées par ordre de date d'échéance croissante. Autrement dit, on donne priorité aux travaux les plus pressés. Cette règle de bon sens va souvent donner de bons résultats lorsque l'on cherche à diminuer les retards. Elle peut cependant s'avérer pénalisante dans plusieurs circonstances:

  • plusieurs tâches sont en retard. Dans ce cas, on risque de donner priorité à des tâches déjà en retard, et ce faisant créer encore plus de retard.
  • les durées opératoires sont très variables. Dans ce cas, donner priorité en utilisant EDD à une tâche longue peut entrainer un retard de plusieurs tâches plus courtes, qui auraient pu être faites rapidement.

En fait, la perception du retard n'est pas forcément linéaire et il peut être plus pénalisant de retarder de deux heures une tâche de 10 minutes que de retarder de 4 heures une tâche de 20 heures.
D'autre part, les dates d'échéance sont liées aux ordres de fabrication, pas aux tâches. Dans un problème mono-machine, c'est équivalent. Dans un problème où les ordres de fabrication ont plusieurs tâches, il faut calculer les dates d'échéance par tâche. Notation : pour l'ordre [math]i [/math], il y a [math] k [/math]opérations, chacune de durée [math]p_{i,j}[/math] et la date d'échéance est [math]d_i[/math]. Il faut donc calculer une date d'échéance par tâche, soit [math]d_{i,j}[/math]
Pour cela, il faut définir l'intervalle de travail [math][t, d_i] [/math]. Soit on dispose de la date de disponibilité (release date [math]r_i[/math] de l'ordre) et [math]t=r_i[/math], soit on prend [math]t=[/math]la date courante.
On peut alors soit :
  • prendre des plages constantes [math]d_{i,j}=t_0+j \times \displaystyle \frac {(d_i - t)}{k}[/math]
  • prendre des plages proportionnelles [math]d_{i,j}=d_{i,j-1}+(d_i - t) \times \displaystyle \frac {p_{i,j}}{\sum _{i=1}^{i=k}{p_{i,k}}}[/math]

SPT : Shortest processing time
L'idée de cette règle est de faire au plus tôt les tâches les plus courtes pour "vider" l'atelier d'un maximum de travaux. Cette règle a pour but de diminuer l'encours moyen.
Comme la précédente, cette règle a ses limites. Si l'horizon est glissant, une tâche longue va toujours être "doublée" par les tâches plus courtes qui arrivent après elle. Si l'horizon est fixe (on fait périodiquement l'ordonnancement) les tâches longues seront faites en fin de période et les courtes en début.
Généralement, cette règle est "couplée" avec des principes de bon sens évitant ces problèmes. C'est le cas par exemple de la séparation en deux flux "caisses rapides" "caisses normales" dans les épiceries. Les caisses rapides sont une manière de prioriser les tâches courtes, mais on s'assure (aux caisses normales) que tout le monde sera servi.
Dans certains cas, on peut aussi utiliser LPT (longest processing time) bien que l'intérêt en planification soit souvent faible. C'est un peu le cas aux urgences d'un hôpital ou plus le cas est grave (traitement souvent plus long) plus le patient est prioritaire.
Finalement, il y a le même problème qu'avec EDD lorsque les ordres ont plusieurs tâches. Si les durées opératoires sont très variables, alors un ordre pourra avoir une grande priorité sur une machine et une faible sur une autre. On minimise alors la taille moyenne des files d'attente sur chaque machine, mais on n'améliore pas l'encours global.
MTS : minimum slack time
Il s'agit de calculer pour chaque ordre de fabrication sa marge, comme [math] \left(d_i-r_i- \displaystyle \sum _{i=1}^{i=k}{p_{i,k}}\right)[/math]. Si il n'y a pas de date de disponibilité, on remplace [math] r_i[/math] par la date courante. Donc c'est le temps mort restant pour exécuter toutes les opérations.
L'avantage de cette règle, c'est qu'elle permet de tenir compte des opérations futures dans une décision locale. Souvent, on va modifier cette règle pour pondérer la marge, soit par le nombre d'opérations restantes (ce n'est pas la même chose d'avoir 8 heures de marge s'il reste 1 ou 4 opérations à effectuer) ou par la somme des durées opératoires (ce n'est pas la même chose d'avoir 4 heures de marges quand il reste 1 heure de travail ou quand il reste 40 heures de travail).
Beaucoup de logiciels commerciaux utilisent ce type d'approche et proposent une panoplie de règles basées sur les dates d'échéances, les durées opératoires, les marges ou des règles de priorité externe, avec toutes les variantes imaginables de pondération.

Exemple

Soit un ensemble de 5 jobs ayant chacun 3 opérations décrites par les triplets (Job, opération, machine, durée) suivants:
Job 1 (1,1,M3,4), (1,2,M1,4), (1,3,M2,4)rouge
Job 2 (2,1,M3,4), (2,2,M2,4), (2,3,M1,4)bleu
Job 3 (3,1,M1,6), (3,2,M2,2), (3,3,M3,4)vert
Job 4 (4,1,M2,4), (4,2,M1,4), (4,3,M3,2)rose
Job 5 (5,1,M1,1), (5,2,M2,6), (5,3,M3,4)jaune

Ordonnancement par Job


En prenant les jobs dans l'ordre chronologique, l'ordonnancement au plus tôt donne le résultat suivant :


Les dates de débuts, fin et encours sont :
job 1, 0, 12, 12
Job 2, 4, 20, 16
job 3, 8, 22, 14
job 4. 0, 26, 26
job 5, 0, 30, 30
L'encours moyen est donc de 98/5= 19.5
On peut essayer d'améliorer ce résultats en enchainant une approche au plus tard après le premier ordre (on conserve l'ordonnancement existant, mais on décale les jobs en conservant leur date de fin). l'ordre obtenu est le suivant :

L'encours moyen est passé à 79/5=15.8.
En prenant les jobs dans le même ordre, mais en les classant au plus tard, à partir de la date de fin(Cmax=30, calculé précédemment), l'ordonnancement résultant est le suivant :

job 1, 18, 30, 12
Job 2, 14, 30, 16
job 3, 14, 30, 16
job 4. 6, 26, 20
job 5, -1, 14, 15
L'encours moyen est donc de 79/5=15.8
On peut essayer d'améliorer ce résultats en enchainant une approche au plus tôt après le premier ordre (on conserve l'ordonnancement existant, mais on décale les jobs en conservant leur date de début). l'ordre obtenu est le suivant :

Ordonnancement par simulation


En utilisant comme règle de priorité extrêmement simple l'ordre lexicographique, et en débutant l'ordonnancement à la date t=0, l'ordonnancement par simulation permet d'obtenir une solution en 22 unités de temps au lieu de 30.

job 1, 0, 22, 22
Job 2, 4, 19, 15
job 3, 0, 12, 12
job 4. 6, 22, 16
job 5, 0, 18, 18
L'encours moyen est donc de 83/5=16.6
En terme de Cmax, le gain est considérable, puisqu'en passant de 30 à 20, on gagne 33%. En revanche, le gain est moins important pour l'encours moyen.

Optimisation


Si on cherche à obtenir le Cmax optimum, on peut arriver à la solution suivante:

Cette solution est optimale puisque le Cmax est égal à la somme des travaux sur M2, on ne peut donc pas faire mieux.

Utilisation de méthodes dédiées

Depuis des décennies, les chercheurs ont identifié des problèmes caractéristiques, spéciaux, bien définis. Pour ces problèmes, et pour un critère donné, ils ont trouvé des algorithmes dédiés, soit donnant la solution optimale, soit une solution approchée. Dans ce dernier cas, les chercheurs ont généralement prouvé la distance de la solution trouvée à la solution optimale.

Dans certains cas simples, les règles de priorité donnent des solutions optimales pour certains critères. Dans la majeure partie des cas, on recherche des solutions plus complexes. Parmi les algorithmes les plus connus, on trouve:


Utilisation de métaheuristiques

Utilisation de métaheuristiques


Les métaheuristiques sont avant tout des heuristiques. Leur objectif n'est pas de produire une solution "optimale", mais de produire une solution "de bonne qualité" en un temps raisonable.
Parmi l'ensemble des heuristiques, les métaheuristiques sont des heuristiques "génériques" qui peuvent s'appliquer à un grand nombre de problèmes.
Principalement apparues dans les années 80, ces méthodes permettent d'aborder les problèmes très complexes en adaptant l'algorithme générique au problème particulier.
Les principales méta-heuristiques se regroupent en 3 grandes familles :
  • les méthodes itérative ou l'on part d'une solution que l'on améliore
  • Les algorithmes à base d'une population de solution (algorithmes génétiques)
  • Les algorithmes de type fourmis

    Algorithme génétiques

    Principe


    Le principe consiste à maintenir une population de solutions. D'une génération à l'autre, cette population va évoluer
    • Certains individus vont passer directement d'une génération à l'autre
    • de nouveaux individus vont être générés par mutation d'un individu de la population précédente,
    • Certains individus vont être créés par croisement de deux individus de la génération précédente.

    Ainsi, la population va évoluer, et à toutes les nouvelles générations on va observer les meilleurs individus pour connaitre la meilleure solution courante.
    Les principaux paramètre d'un algorithme génétique sont :
    • le codage d'une solution
    • Le mécanisme de choix des individus qui mutent ou qui vont être croisés
    • Le mécanisme de mutation
    • Le mécanisme de croisement
    • la politique relativement aux doublons
    • la politique relativement à la conservation ou non des individus ayant mutés ou s'étant croisés.

    Codage


    Le codage est fondamental car il devra supporter les opérations de croisement et de mutation. On cherche le plus souvent à modéliser une solution par un vecteur de booléens, qui est la forme la plus facile à manipuler. On peut être amené à avoir des vecteurs de réels, des matrices, etc. Mais plus le codage est complexe, plus les opérateurs seront difficiles à mettre en place.

    Choix des candidats


    On souhaite favoriser les meilleurs solutions. On essaye donc de tirer aléatoirement le fait que tel ou tel individu va être sélectionné, mais avec une probabilité proportionnelle à sa performance.
    Soit [math] Min[/math] la meilleur solution possible, et[math] Max[/math] la pire. Il peut paraitre naturel pour une solution de valeur[math] V[/math] d'utiliser la probabilité : [math]P(V)=\displaystyle \frac{max-V}{Max-Min}[/math]. Malheureusement, il faudrait connaitre les valeurs respectives de [math] Min[/math] et [math] Max[/math] ce qui n'est pas le cas. On peut utiliser les extrêmes connues, mais cela peut induire un biais.
    Exemple :
    Min=100, max = 200, pour V = 150, P= 0.5 et pour v=160 p=0.4
    Si la meilleure solution connue est 145, la pire 180, les probabilités deviennent P(150)=0.85 et P(160)=0.44.
    Si la meilleure solution connue est 145, la pire 200, les probabilités deviennent P(150)=0.9 et P(160)=0.72.
    Autrement dit, cette méthode est très sensible à l'estimation des bornes.

    Mutation


    Il y a un très grand nombre de méthodes de mutation, dépendant étroitement de la nature du problème et du codage. Dans les algorithmes d'ordonnancement, si la solution est une séquence, il est fréquent de permuter deux jobs. Si on travaille sur une tournée de véhicules, on peut permuter deux villes sur le cycle. Si on travaille sur l'implantation d'un atelier, on peut permuter deux machines dans l'agencement spatial.

    Croisement


    Là encore, il y a une infinité de méthodes de croisement. L'idée est souvent d'essayer de faire deux enfants avec deux parents. Pour cela, il faut arriver à extraire deux sous ensembles cohérents des deux parents.

    Les doublons


    Fréquemment, un individu créé peut avoir son clone déjà présent dans la population. Qu'en faire. Si on cherche à améliorer globalement le niveau moyen de la population, il est évident que les meilleurs individus vont apparaitre plusieurs fois, et les conserver, c'est augmenter les chances que ces bons individus se reproduisent. En revanche, il y a un risque de consanguinité, et il ne faut pas avoir une population trop homogène. Plusieurs auteurs proposent des solutions contradictoires sur ce point.

    Le sort des parents


    Lorsque deux individus performants ont été choisis pour un croisement, on créé deux enfants mais que faire des parents. Si on les conserve, on va vers une augmentation irrémédiable du cardinal de la population, mais si on les élimine, on risque de se priver de nos meilleurs reproducteurs.
    Parmi les solutions, il y a la possibilité de conserver les parents, mais d'éliminer à chaque génération les plus mauvais individus, afin de conserver une population plus ou moins constante.

    références


    les sites de Wikipedia sont corrects
    http://en.wikipedia.org/wiki/Genetic_algorithm
    http://fr.wikipedia.org/wiki/Algorithme_g%C3%A9n%C3%A9tique
    http://en.wikipedia.org/wiki/Genetic_algorithm

    Algorithmes itératifs

    Principe


    Le principe des métha-heuristiques itératives consiste à prendre une solution initiale (aléatoirement ou en utilisant une heuristique spécialisée) et à améliorer cette solution en cherchant dans son voisinage une solution meilleure.
    La notion de voisinage est complexe. Le voisinage d'une solution dépend étroitement de la nature d'une solution.
    Si la solution est une séquence, le voisinage d'une solution peut consister en toutes les solutions obtenues par permutation de deux éléments consécutifs (soit [math] (n-1) [/math] permutations si [math]n[/math] est le nombre d'objets de la séquence). Si on cherche un voisinage plus vaste, on peut considérer toutes les permutations de 2 éléments quelconques de la séquence (soit [math] \frac{n \times (n-1)}{2} [/math] permutations).
    Si la solution est une partition, le voisinage peut consister en l'ensemble des partitions obtenues en déplaçant un élément.

    Descente stochastique


    Consiste à appliquer l'algorithme suivant :
    • 1) Choisir une solution initiale,
    • 2) Tant qu'un critère d'arrêt n'est pas atteint faire
    • 3) Choisir aléatoirement une solution voisine
    • 4) Si elle améliore la solution courante, la prendre,
    • 5) Retourner en 2
    Le critère d'arrêt est souvent le fait que l'on a testé [math] K [/math] solutions voisines sans une seule amélioration. L'algorithme devient :
    • 1) choisir une solution initiale, n=0
    • 2) tant que [math] n < K [/math]
    • 3) choisir aléatoirement une solution voisine
    • 4) si elle améliore la solution courante, la prendre, et n=0, sinon n=n+1
    • 5) retourner en 2

    Cet algorithme élémentaire peut être utilisé pour tester la qualité d'algorithmes spécialisés. Il suffit d'enchaîner des descentes stochastiques successives en choisissant des solutions initiales différentes, durant le temps d'exécution de l'algorithme spécialisé à tester.
    Cet algorithme ne garanti évidement pas une solution optimale, mais il ne garanti pas non plus un optimum locale dans le voisinage.

    Méthode du gradient


    Contrairement à la descente stochastique, la méthode du gradient explore tout le voisinage. L'algorithme simplifié est le suivant :
    • 1) choisir une solution initiale,
    • 2) évaluer toutes les solutions du voisinage
    • 3) choisir la meilleure
    • 4) si elle améliore la solution courante, la prendre, et retourner en 2)
    • 5) fin

    Cet algorithme garanti un optimum local, puisqu'aucune solution du voisinage n'améliore la solution. En revanche, cet optimum n'est pas forcément un optimum global. Les méthodes suivantes ont pour but de se sortir des optima locaux.

    Méthode Tabou


    La méthode Tabou a pour but de permettre de sortir d'un optimum local. Sur le même principe que le gradient, cette méthode va parcourir tout le voisinage, mais elle va accepter d'aller vers une solution moins bonne que la solution courante.
    Évidement, si on se contente de cette règle, on va vers un problème, car si la solution [math]S[/math] est un optimum local, et qu'on la quitte pour [math]S'[/math], moins bonne que [math]S[/math], mais la meilleure dans le voisinage, comme par réciprocité [math]S[/math] est dans le voisinage de [math]S'[/math], en quittant [math]S'[/math]on risque fort de revenir sur [math]S[/math] et de boucler. Pour éviter cela, on utilise la liste Tabou: C'est une liste des dernières solutions visitées que l'on s'interdit de reprendre à court terme. C'est en quelque sorte l'historique de la recherche. À chaque itération, une nouvelle solution rentre dans la liste Tabou et la plus ancienne en sort.
    Malgré tout, il peut se trouver que la meilleure solution autorisée (donc dans le voisinage de la solution [math]S[/math] moins la liste Tabou) soit de bien moins bonne qualité que la solution courante. On peut alors relaxer la contrainte de la liste Tabou en changeant la solution courante par une solution de la liste tabou (cela revient à revenir en arrière, tout en refusant de refaire les mêmes erreurs (grâce à la liste Tabou).
    L'algorithme est donc :
    [math]V(S)[/math] = voisinage de la solution [math]S[/math]
    [math]T(t)[/math]= Liste Tabou à l'itération [math]t[/math]
    • 1) choisir une solution initiale [math]S(0), t=0, T(0)= \varnothing , best=S[/math]
    • 2) [math]t=t+1[/math]
    • 3) S(t)= la meilleure des solutions dans [math]V(S(t))-T(t)[/math]
    • 4) Si elle détériore trop la solution S(t-1) utiliser la fonction d'aspiration pour déterminer S(t)
    • 5) Mettre à jour [math]T(t),Best [/math] si nécessaire
    • 5) Si le critère de fin est atteint, finir, sinon retourner en 2)

    Le critère d'arrêt peut être de ne pas avoir amélioré la solution durant les [math]K[/math] dernières itérations.

    Recuit simulé


    Cette méthode s'apparente plus à la descente stochastique qu'au recuit simulé puisque l'ensemble du voisinage de la solution courante ne sera pas visité.En revanche, pour ne pas rester dans un optimum local, l'algorithme va accepter de sélectionner un voisin qui détériore la solution courante, avec une probabilité donnée, décroissante au cours du temps.
    Algorithme:
    initialiser S, Sopt=S, Meilleur=Val(S),k←0
    Tant que [math]k <= kmax [/math]

    Choisir S' dans V(S), calculer Val(S')
    si Val< Meilleur alors Sopt ← S', Meilleur ← Val(S')
    si [math] P \left( S', S, k \right)> alea())[/math] alors S←S'
    k ← k + 1

    retourner Sopt

    Cet algorithme utilise comme critère d'acceptation le critère dit de Metropolis qui consiste à accepter la nouvelle solution avec une probabilité P(S', S, T)égale à:

    • 1 si Val(S') < Val(S)
    • [math] exp{\left( \displaystyle \frac {Val(S)-Val(S')}{T} \right)} [/math] sinon.

    T est un paramètre qui mesure une température et qui fait qu'à haute température, si T est grand, [math] \displaystyle \frac {Val(S)-Val(S')}{T} [/math] est proche de 1 et donc on aura tendance à accepter de choisir des solutions qui dégradent la solution courante, alors que si la température se rapproche de 0, alors l'algorithme se comportera comme une descente stochastique.
    Dans l'algorithme proposé, la température est calculée comme [math]k/kmax[/math]. Elle décroit donc quand k augmente, pour atteindre 1.
    Dans d'autre version de cet algorithme, la température décroit par pallier.
    Il a été montré que l'algorithme du recuit simulé converge vers la solution optimale, mais la preuve de convergence utilise le fait que l'ensemble des réels est fini lorsque l'on utilise un ordinateur, et que le temps peut être poursuivi à l'infini. Autrement dit, dans la pratique, ce résultat est inutilisable et cette méta-heuristique ne converge pas plus que les autres vers l'optimum global.

    Références


    http://en.wikipedia.org/wiki/Reactive_search_optimization
    Un excellent document sur la recherche Tabou :
    http://www.ifi.uio.no/infheur/Bakgrunn/Intro_to_TS_Gendreau.htm
    Pour le recuit simulé, attention au site wikipedia français, il contient des erreurs. Voir plutôt; http://en.wikipedia.org/wiki/Simulated_anealing
    Kirkpatrick, S.; C. D. Gelatt, M. P. Vecchi (1983-05-13). "Optimization by Simulated Annealing". Science. New Series 220 (4598): 671-680
    Granville V., M. Krivánek, J. P. Rasson "Simulated annealing: A proof of convergence". IEEE Transactions on Pattern Analysis and Machine Intelligence 16 (6): 652-656. June 1994