Séparation et Evaluation pour le problème d’ordonnancement avec blocage

En général, les problèmes d’ordonnancement modélisent des problèmes d’ateliers de fabrication; ces ateliers sont composés principalement de ressources (machines, ouvriers et matière première) utiles à la fabrication de plusieurs types de produits. La résolution de ces problèmes revient, dans les méthodes classiques, à déterminer les dates de début et de fin de chaque opération composant les gammes opératoire des produits. Les nouvelles méthodes de résolution, s’orientent vers la recherche de l’ordre des séquences de passage sur chaque machine. Cette technique est plus pratique et rapide pour trouver l’ordonnancement nécessaire. Ces nouvelles techniques, ne change pas la complexité du problème d’ordonnancement classé NPdifficile. Les méthodes de résolution des problèmes d’ordonnancement d’ateliers se divisent en deux principales classes : Les méthodes exactes ont l’avantage de garantir l’optimum en parcourant toutes les combinaisons possibles d’une manière intelligente. Comme inconvénient majeur, ces méthodes sont caractérisées par un temps de réponse non raisonnable pour des instances de moyenne et grande tailles, la pratique montre que l’utilisation d’un ordinateur (machine de calcul) est insuffisant (espace mémoire, vitesse de calcul) devant une complexité de plus en plus grande.

Position du problème

L’ordonnancement d’atelier à cheminements multiples (Job Shop) est généralement formulé comme suit : Soit un ensemble de travaux de cardinalité n noté J={J1,…,Jn}, à traiter par un ensemble de machines de cardinalité m noté M={M1,…,Mm}; chaque travail j a un sous ensemble ordonné d’opérations noté Oj={oj1,……,ojpj}. Pour cela des contraintes de précédences sont définis :  S’il y a une contrainte de précédence entre deux opérations oi et oj (oi  oj) alors oj ne peut commencer avant que oi se termine. Donc l’ordre de la gamme opératoire est obligatoire.  Chaque machine ne peut traiter qu’une seule opération à la fois et un travail ne peut occuper plus qu’une machine en même temps.  Les séquences de passage des opérations sur une même machine sont inconnues et à déterminer dans le but de minimiser la durée total de production Cmax tout en respectant les contraintes du problème.

Les contraintes

L’atelier de fabrication est soumis à des contraintes technologiques. Ces contraintes touchent à la fois les possibilités d’utilisation des machines et les liens (contraintes) qui peuvent exister entre les opérations. Ces contraintes sont les suivantes : a) Les machines sont indépendantes les unes des autres (pas d’utilisation d’outil commun par exemple). 216 b) Une machine ne peut exécuter qu’une seule opération à un instant donné. c) Chaque machine est disponible pendant toute la durée de l’ordonnancement, en particulier, les pannes ne sont pas prises en compte dans ce modèle. d) Une opération en cours d’exécution ne peut pas être interrompue (la préemption des opérations n’est pas permise). e) Les travaux sont indépendants les uns des autres. En particulier, il n’existe aucun ordre de priorité attaché aux travaux. D’autres types de contraintes peuvent êtres prises en considérations, ceci dépendra du problème posé et du cas à étudier, pour notre cas nous avons choisi les contraintes ci-dessus. En plus de la relation de précédence on trouve encore d’autres contraintes; celles ci dépendent de l’environnement de production, dans certains ateliers de production, deux opérations peuvent se réalisées en séquentielle ou en parallèle, ceci dépend du fait de partager la même ressource; dans ce cas, une règle de priorité doit être définie entre ces opérations. Le passage séquentiel des opérations sur les machines risque d’être bloqué si celles-ci n’admettent pas d’espace de stockage pour les opérations traitées, ainsi l’opération suivante ne peut commencer que si la première quitte cette ressource partagée, cette contrainte est appelée « contrainte de blocage ».

La contrainte de blocage

Soient i et j deux opérations concurrentes sur la même machine M(i)=M(j) et σ(i), σ(j) leurs successeurs directs, respectivement. Dans le cas où la machine M n’admet pas un espace de stockage, alors le passage séquentiel de j sur M dépend de la fin de traitement de i sur la même machine, pendant ce temps, j restera bloquée jusqu’à ce que i quitte M; cette situation est représentée en reliant σ(i) avec j, σ(j) avec i par une paire d’arcs alternatifs u1 et u2 tels que : u1=(σ(i),j) et u2=(σ(j),i). Chaque arc alternatif ul représente le fait que l’opération terminale ne peut commencer avant le début de l’opération initiale, ainsi, tσ(i)<= tj et tσ(j)<= ti . La pondération des arcs alternatifs est souvent nulle, l’exception est faite avec la dernière opération k de chaque travail qui n’admet pas de successeur, donc σ(k) n’existe pas, dans ce cas là on relie directement ces sommets (opérations) avec leurs concurrents sur la même machine en utilisant des arcs alternatifs pondérés, cette pondérations est strictement positif, dont la valeur est égale à la durée de traitement pk du sommet initial de chaque arc alternatif.