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,