Ordonnancement des ateliers

L'ordonnancement des tâches , le problème de l'atelier de travail ( JSP ) ou le problème d'ordonnancement des tâches ( JSSP ) est un problème d'optimisation _en informatique et en recherche opérationnelle . C'est une variante de l'ordonnancement optimal des tâches . Dans un problème général d'ordonnancement des tâches, on nous donne n tâches J1 , J2 , ..., Jn de temps _de traitement variables, qui doivent être planifiées sur m machines avec une puissance de traitement variable, tout en essayant de minimiser le _makespan- la longueur totale de l'ordonnancement (c'est-à-dire lorsque toutes les tâches ont terminé leur traitement). Dans la variante spécifique connue sous le nom _d'ordonnancement des tâches , chaque tâche se compose d'un ensemble d' opérations O1 , O2 , ..., On _qui doivent être traitées dans un ordre spécifique (connu sous le nom de _contraintesde priorité ). Chaque opération a une machine spécifique sur laquelle elle doit être traitée et une seule opération dans une tâche peut être traitée à un moment donné. Une relaxation courante est l' atelier flexible , où chaque opération peut être traitée sur n'importe quelle machine d'un ensemble donné (les machines de chaque ensemble sont identiques).

Le nom vient à l'origine de la planification des tâches dans un atelier , mais le thème a de larges applications au-delà de ce type d'instance. Ce problème est l'un des problèmes d'optimisation combinatoire les plus connus , et fut le premier problème pour lequel une analyse concurrentielle fut présentée, par Graham en 1966. Les meilleures instances de problèmes pour un modèle de base avec un objectif de fabrication sont dues à Taillard.

Dans la notation standard à trois champs pour les problèmes d'ordonnancement optimal des tâches , la variante job-shop est désignée par J dans le premier champ. Par exemple, le problème désigné par " " est un problème job-shop à 3 machines avec des temps de traitement unitaires, où l'objectif est de minimiser le temps d'achèvement maximal. ${\displaystyle J_{3}|p_{ij}|C_{\max <semantics> <mrow> <mstyle> <msub> <mi>J</mi> <mrow> <mn>3</mn> </mrow> </msub> <mrow> <mo>|</mo> </mrow> <msub> <mi>p</mi> <mrow> <mi>je</mi> <mi>j</mi> </mrow> </msub> <mrow> <mo>|</mo> </mrow> <msub> <mi>C</mi> <mrow> <mo>max</mo> </mrow> </msub> </mstyle> </mrow> <annotation>{ displaystyle J_ {3} | p_ {ij} | C_ { max }}</annotation> </semantics> </math><img src=$

Variations du problème

Il existe de nombreuses variantes du problème, notamment les suivantes :

Les machines peuvent avoir des doublons (atelier flexible avec machines dupliquées) ou appartenir à des groupes de machines identiques (atelier flexible).
Les machines peuvent nécessiter un certain intervalle entre les tâches ou aucun temps d'inactivité.
Les machines peuvent avoir des configurations dépendantes de la séquence.
La fonction objective peut être de minimiser le temps d'exécution, la norme L _p , le retard, le retard maximal, etc. Il peut également s'agir d'un problème d'optimisation multi-objectifs.
Les tâches peuvent avoir des contraintes, par exemple une tâche i doit être terminée avant que la tâche j puisse être démarrée (voir workflow ). De plus, la fonction objective peut être multicritère.
Un ensemble de tâches peut être lié à différents ensembles de machines.
Temps de traitement déterministes (fixes) ou temps de traitement probabilistes.

Dureté NP

Étant donné que le problème du voyageur de commerce est NP-difficile , le problème de l'atelier avec une configuration dépendante de la séquence est clairement également NP-difficile puisque le TSP est un cas particulier du JSP avec un seul travail (les villes sont les machines et le vendeur est le travail).

Représentation du problème

Le graphe disjonctif est l'un des modèles populaires utilisés pour décrire les cas de problèmes de planification d'atelier.

Un énoncé mathématique du problème peut être formulé comme suit :

Soient et deux ensembles finis . En raison de l'origine industrielle du problème, les sont appelés machines et les sont appelés emplois . ${\displaystyle M=\{M_{1},M_{2},\dots ,M_{m}\ <semantics> <mrow> <mstyle> <mi>M</mi> <mo>=</mo> <mo>{</mo> <msub> <mi>M</mi> <mrow> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>M</mi> <mrow> <mn>2</mn> </mrow> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>M</mi> <mrow> <mi>m</mi> </mrow> </msub> <mo>}</mo> </mstyle> </mrow> <annotation>{\displaystyle M=\{M_{1},M_{2},\points ,M_{m}\}}</annotation> </semantics> </math><img src=$ ${\displaystyle J=\{J_{1},J_{2},\dots ,J_{n}\ <semantics> <mrow> <mstyle> <mi>J</mi> <mo>=</mo> <mo>{</mo> <msub> <mi>J</mi> <mrow> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>J</mi> <mrow> <mn>2</mn> </mrow> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>J</mi> <mrow> <mi>n</mi> </mrow> </msub> <mo>}</mo> </mstyle> </mrow> <annotation>{\displaystyle J=\{J_{1},J_{2},\dots,J_{n}\}}</annotation> </semantics> </math><img src=$ ${\displaystyle \displaystyle M_{i <semantics> <mrow> <mstyle> <mstyle> <msub> <mi>M</mi> <mrow> <mi>je</mi> </mrow> </msub> </mstyle> </mstyle> </mrow> <annotation>{ displaystyle displaystyle M_ {i}}</annotation> </semantics> </math><img src=$ ${\displaystyle \displaystyle J_{j <semantics> <mrow> <mstyle> <mstyle> <msub> <mi>J</mi> <mrow> <mi>j</mi> </mrow> </msub> </mstyle> </mstyle> </mrow> <annotation>{ displaystyle displaystyle J_ {j}}</annotation> </semantics> </math><img src=$

Soit l'ensemble de toutes les affectations séquentielles de tâches aux machines, telles que chaque tâche est effectuée par chaque machine exactement une fois ; les éléments peuvent être écrits sous forme de matrices, dans lesquelles la colonne répertorie les tâches que cette machine effectuera, dans l'ordre. Par exemple, la matrice ${\displaystyle \displaystyle \ {\mathcal {X <semantics> <mrow> <mstyle> <mstyle> <mtext> </mtext> <mrow> <mrow> <mi>X</mi> </mrow> </mrow> </mstyle> </mstyle> </mrow> <annotation>{ displaystyle displaystyle { mathcal {X}}}</annotation> </semantics> </math><img src=$ ${\displaystyle x\in {\mathcal {X <semantics> <mrow> <mstyle> <mi>x</mi> <mo>∈</mo> <mrow> <mrow> <mi>X</mi> </mrow> </mrow> </mstyle> </mrow> <annotation>{\displaystyle x\in {\mathcal {X}}}</annotation> </semantics> </math><img src=$ ${\displaystyle n imes m <semantics> <mrow> <mstyle> <mi>n</mi> <mo>×</mo> <mi>m</mi> </mstyle> </mrow> <annotation>{\displaystyle n\fois m}</annotation> </semantics> </math><img src=$ ${\displaystyle \displaystyle i <semantics> <mrow> <mstyle> <mstyle> <mi>je</mi> </mstyle> </mstyle> </mrow> <annotation>{ displaystyle displaystyle i}</annotation> </semantics> </math><img src=$ ${\displaystyle \displaystyle M_{i <semantics> <mrow> <mstyle> <mstyle> <msub> <mi>M</mi> <mrow> <mi>je</mi> </mrow> </msub> </mstyle> </mstyle> </mrow> <annotation>{ displaystyle displaystyle M_ {i}}</annotation> </semantics> </math><img src=$

{\displaystyle x={\begin{pmatrix}1&2\\2&3\\3&1\end{pmatrix <semantics> <mrow> <mstyle> <mi>x</mi> <mo>=</mo> <mrow> <mrow> <mo>(</mo> <mtable> <mtr> <mtd> <mn>1</mn> </mtd> <mtd> <mn>2</mn> </mtd> </mtr> <mtr> <mtd> <mn>2</mn> </mtd> <mtd> <mn>3</mn> </mtd> </mtr> <mtr> <mtd> <mn>3</mn> </mtd> <mtd> <mn>1</mn> </mtd> </mtr> </mtable> <mo>)</mo> </mrow> </mrow> </mstyle> </mrow> <annotation>{\displaystyle x={\begin{pmatrix}1&2\\2&3\\3&1\end{pmatrix}}}</annotation> </semantics> </math></span><img src=

signifie que la machine effectuera les trois tâches dans l'ordre , tandis que la machine effectuera les tâches dans l'ordre . ${\displaystyle \displaystyle M_{1 <semantics> <mrow> <mstyle> <mstyle> <msub> <mi>M</mi> <mrow> <mn>1</mn> </mrow> </msub> </mstyle> </mstyle> </mrow> <annotation>{ displaystyle displaystyle M_ {1}}</annotation> </semantics> </math><img src=$ ${\displaystyle \displaystyle J_{1},J_{2},J_{3 <semantics> <mrow> <mstyle> <mstyle> <msub> <mi>J</mi> <mrow> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>J</mi> <mrow> <mn>2</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>J</mi> <mrow> <mn>3</mn> </mrow> </msub> </mstyle> </mstyle> </mrow> <annotation>{ displaystyle displaystyle J_ {1}, J_ {2}, J_ {3}}</annotation> </semantics> </math><img src=$ ${\displaystyle \displaystyle J_{1},J_{2},J_{3 <semantics> <mrow> <mstyle> <mstyle> <msub> <mi>J</mi> <mrow> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>J</mi> <mrow> <mn>2</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>J</mi> <mrow> <mn>3</mn> </mrow> </msub> </mstyle> </mstyle> </mrow> <annotation>{ displaystyle displaystyle J_ {1}, J_ {2}, J_ {3}}</annotation> </semantics> </math><img src=$ ${\displaystyle \displaystyle M_{2 <semantics> <mrow> <mstyle> <mstyle> <msub> <mi>M</mi> <mrow> <mn>2</mn> </mrow> </msub> </mstyle> </mstyle> </mrow> <annotation>{ displaystyle displaystyle M_ {2}}</annotation> </semantics> </math><img src=$ ${\displaystyle \displaystyle J_{2},J_{3},J_{1 <semantics> <mrow> <mstyle> <mstyle> <msub> <mi>J</mi> <mrow> <mn>2</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>J</mi> <mrow> <mn>3</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>J</mi> <mrow> <mn>1</mn> </mrow> </msub> </mstyle> </mstyle> </mrow> <annotation>{ displaystyle displaystyle J_ {2}, J_ {3}, J_ {1}}</annotation> </semantics> </math><img src=$

Supposons également qu'il existe une fonction de coût . La fonction de coût peut être interprétée comme un « temps de traitement total » et peut avoir une expression en termes de temps , le coût/temps nécessaire à la machine pour effectuer le travail . ${\displaystyle C:{\mathcal {X}} o [0,+\infty ] <semantics> <mrow> <mstyle> <mi>C</mi> <mo>:</mo> <mrow> <mrow> <mi>X</mi> </mrow> </mrow> <mo>→</mo> <mo>[</mo> <mn>0</mn> <mo>,</mo> <mo>+</mo> <mi>∞</mi> <mo>]</mo> </mstyle> </mrow> <annotation>{\displaystyle C:{\mathcal {X}} o [0,+\infty ]}</annotation> </semantics> </math><img src=$ ${\displaystyle C_{ij}:M imes J o [0,+\infty ] <semantics> <mrow> <mstyle> <msub> <mi>C</mi> <mrow> <mi>je</mi> <mi>j</mi> </mrow> </msub> <mo>:</mo> <mi>M</mi> <mo>×</mo> <mi>J</mi> <mo>→</mo> <mo>[</mo> <mn>0</mn> <mo>,</mo> <mo>+</mo> <mi>∞</mi> <mo>]</mo> </mstyle> </mrow> <annotation>{\displaystyle C_{ij}:M\fois J\à [0,+\infty ]}</annotation> </semantics> </math><img src=$ ${\displaystyle \displaystyle M_{i <semantics> <mrow> <mstyle> <mstyle> <msub> <mi>M</mi> <mrow> <mi>je</mi> </mrow> </msub> </mstyle> </mstyle> </mrow> <annotation>{ displaystyle displaystyle M_ {i}}</annotation> </semantics> </math><img src=$ ${\displaystyle \displaystyle J_{j <semantics> <mrow> <mstyle> <mstyle> <msub> <mi>J</mi> <mrow> <mi>j</mi> </mrow> </msub> </mstyle> </mstyle> </mrow> <annotation>{ displaystyle displaystyle J_ {j}}</annotation> </semantics> </math><img src=$

Le problème de l'atelier de travail consiste à trouver une affectation de travaux telle qu'elle soit minimale, c'est-à-dire qu'il n'y en ait pas de telle que . ${\displaystyle x\in {\mathcal {X <semantics> <mrow> <mstyle> <mi>x</mi> <mo>∈</mo> <mrow> <mrow> <mi>X</mi> </mrow> </mrow> </mstyle> </mrow> <annotation>{\displaystyle x\in {\mathcal {X}}}</annotation> </semantics> </math><img src=$ ${\displaystyle \displaystyle C(x) <semantics> <mrow> <mstyle> <mstyle> <mi>C</mi> <mo>(</mo> <mi>x</mi> <mo>)</mo> </mstyle> </mstyle> </mrow> <annotation>{ displaystyle displaystyle C (x)}</annotation> </semantics> </math><img src=$ ${\displaystyle y\in {\mathcal {X <semantics> <mrow> <mstyle> <mi>et</mi> <mo>∈</mo> <mrow> <mrow> <mi>X</mi> </mrow> </mrow> </mstyle> </mrow> <annotation>{\displaystyle y\in {\mathcal {X}}}</annotation> </semantics> </math><img src=$ $C(y) C (x) > C (et)$ C(y)}" data-src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8a997b981b45d4729f605dd8800aa238460b6466">

Efficacité de la planification

L'efficacité de la planification peut être définie pour un planning par le rapport entre le temps d'inactivité total de la machine et le temps de traitement total, comme indiqué ci-dessous :

${\displaystyle C'=1+{\sum _{i}l_{i} \over \sum _{j,k}p_{jk}}={C.m \over \sum _{j,k}p_{jk <semantics> <mrow> <mstyle> <msup> <mi>C</mi> <mo>′</mo> </msup> <mo>=</mo> <mn>1</mn> <mo>+</mo> <mrow> <mfrac> <mrow> <munder> <mo>∑</mo> <mrow> <mi>je</mi> </mrow> </munder> <msub> <mi>l</mi> <mrow> <mi>je</mi> </mrow> </msub> </mrow> <mrow> <munder> <mo>∑</mo> <mrow> <mi>j</mi> <mo>,</mo> <mi>k</mi> </mrow> </munder> <msub> <mi>p</mi> <mrow> <mi>j</mi> <mi>k</mi> </mrow> </msub> </mrow> </mfrac> </mrow> <mo>=</mo> <mrow> <mfrac> <mrow> <mi>C</mi> <mo>.</mo> <mi>m</mi> </mrow> <mrow> <munder> <mo>∑</mo> <mrow> <mi>j</mi> <mo>,</mo> <mi>k</mi> </mrow> </munder> <msub> <mi>p</mi> <mrow> <mi>j</mi> <mi>k</mi> </mrow> </msub> </mrow> </mfrac> </mrow> </mstyle> </mrow> <annotation>{\displaystyle C'=1+{\sum _{i}l_{i} \over \sum _{j,k}p_{jk}}={Cm \over \sum _{j,k}p_{jk}}}</annotation> </semantics> </math><img src=$

Voici le temps d'inactivité de la machine i , C est le makespan et m est le nombre de machines. Notez qu'avec la définition ci-dessus, l'efficacité de la planification est simplement le makespan normalisé par rapport au nombre de machines et au temps de traitement total. Cela permet de comparer l'utilisation des ressources entre des instances JSP de différentes tailles. ${\displaystyle l_{i <semantics> <mrow> <mstyle> <msub> <mi>l</mi> <mrow> <mi>je</mi> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle l_{i}}</annotation> </semantics> </math><img src=$

Le problème du coût infini

L'un des premiers problèmes à traiter dans la JSP est que de nombreuses solutions proposées ont un coût infini : c'est-à-dire qu'il existe des solutions telles que . En fait, il est assez simple d'en inventer des exemples en s'assurant que deux machines vont se bloquer , de sorte que chacune attende la sortie de l'étape suivante de l'autre. ${\displaystyle x_{\infty }\in {\mathcal {X <semantics> <mrow> <mstyle> <msub> <mi>x</mi> <mrow> <mi>∞</mi> </mrow> </msub> <mo>∈</mo> <mrow> <mrow> <mi>X</mi> </mrow> </mrow> </mstyle> </mrow> <annotation>{\displaystyle x_{\infty }\in {\mathcal {X}}}</annotation> </semantics> </math><img src=$ ${\displaystyle C(x_{\infty })=+\infty <semantics> <mrow> <mstyle> <mi>C</mi> <mo>(</mo> <msub> <mi>x</mi> <mrow> <mi>∞</mi> </mrow> </msub> <mo>)</mo> <mo>=</mo> <mo>+</mo> <mi>∞</mi> </mstyle> </mrow> <annotation>{\displaystyle C(x_{\infty })=+\infty }</annotation> </semantics> </math><img src=$ ${\displaystyle x_{\infty <semantics> <mrow> <mstyle> <msub> <mi>x</mi> <mrow> <mi>∞</mi> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle x_{\infty }}</annotation> </semantics> </math><img src=$

Principaux résultats

Graham avait déjà fourni l'algorithme d'ordonnancement de liste en 1966, qui est (2 − 1/ m ) -compétitif, où m est le nombre de machines. De plus, il a été prouvé que l'ordonnancement de liste est un algorithme en ligne optimal pour 2 et 3 machines. L' algorithme de Coffman-Graham (1972) pour les tâches de longueur uniforme est également optimal pour deux machines et est (2 − 2/ m ) -compétitif. En 1992, Bartal, Fiat, Karloff et Vohra ont présenté un algorithme qui est compétitif à 1,986. Un algorithme compétitif à 1,945 a été présenté par Karger, Philips et Torng en 1994. En 1992, Albers a fourni un algorithme différent qui est compétitif à 1,923. Actuellement, le résultat le plus connu est un algorithme donné par Fleischer et Wahl, qui atteint un ratio compétitif de 1,9201.

Une limite inférieure de 1,852 a été présentée par Albers. Les instances de Taillard jouent un rôle important dans le développement de la planification des ateliers avec un objectif de fabrication.

En 1976, Garey a fourni une preuve que ce problème est NP-complet pour m>2, c'est-à-dire qu'aucune solution optimale ne peut être calculée en temps polynomial déterministe pour trois machines ou plus (à moins que P=NP ).

En 2011, Xin Chen et al. ont fourni des algorithmes optimaux pour la planification en ligne sur deux machines liées améliorant ainsi les résultats précédents.

Minimisation du temps de travail hors ligne

Emplois dans le domaine atomique

La forme la plus simple du problème de minimisation du temps de traitement hors ligne concerne les tâches atomiques, c'est-à-dire les tâches qui ne sont pas subdivisées en plusieurs opérations. Cela revient à regrouper un certain nombre d'éléments de tailles différentes dans un nombre fixe de bacs, de sorte que la taille maximale du bac nécessaire soit aussi petite que possible. (Si au contraire le nombre de bacs doit être minimisé et que la taille du bac est fixe, le problème devient un problème différent, connu sous le nom de problème de regroupement de bacs .)

Dorit S. Hochbaum et David Shmoys ont présenté en 1987 un schéma d'approximation en temps polynomial qui trouve une solution approximative au problème de minimisation du temps de réponse hors ligne avec des tâches atomiques à n'importe quel degré de précision souhaité.

Emplois composés de plusieurs opérations

La forme de base du problème de planification de tâches avec plusieurs opérations (M), sur M machines, telles que toutes les premières opérations doivent être effectuées sur la première machine, toutes les secondes opérations sur la seconde, etc., et qu'une seule tâche ne peut pas être effectuée en parallèle, est connue sous le nom de problème de planification de type flow-shop . Il existe différents algorithmes, notamment des algorithmes génétiques .

L'algorithme de Johnson

Un algorithme heuristique de SM Johnson peut être utilisé pour résoudre le cas d'un problème de N jobs sur 2 machines lorsque tous les jobs doivent être traités dans le même ordre. Les étapes de l'algorithme sont les suivantes :

Le travail P _i comporte deux opérations, de durée P _i1 , P _i2 , à effectuer sur la machine M1, M2 dans cette séquence.

Étape 1. Liste A = { 1, 2, …, N }, Liste L1 = {}, Liste L2 = {}.
Étape 2. Parmi toutes les durées d’opération disponibles, choisissez la durée minimale.

Si le minimum appartient à P _k1 ,

Supprimer K de la liste A ; ajouter K à la fin de la liste L1.

Si le minimum appartient à P _k2 ,

Supprimer K de la liste A ; ajouter K au début de la liste L2.

Étape 3. Répétez l’étape 2 jusqu’à ce que la liste A soit vide.
Étape 4. Joignez la liste L1, la liste L2. C'est la séquence optimale.

La méthode de Johnson ne fonctionne de manière optimale que pour deux machines. Cependant, comme elle est optimale et facile à calculer, certains chercheurs ont essayé de l'adopter pour M machines, ( M > 2.)

L'idée est la suivante : imaginez que chaque job nécessite m opérations en séquence, sur M1, M2… Mm. Nous combinons les m /2 premières machines dans un centre d'usinage (imaginaire), MC1, et les machines restantes dans un centre d'usinage MC2. Ensuite, le temps de traitement total pour un Job P sur MC1 = somme (temps d'opération sur les m /2 premières machines), et le temps de traitement pour le Job P sur MC2 = somme (temps d'opération sur les m /2 dernières machines).

Ce faisant, nous avons réduit le problème de la m-Machine à un problème de planification de deux centres d'usinage. Nous pouvons résoudre ce problème en utilisant la méthode de Johnson.

Prédiction de Makespan

L'apprentissage automatique a récemment été utilisé pour prédire la durée optimale d'exécution d'une instance JSP sans réellement produire le planning optimal. Les résultats préliminaires montrent une précision d'environ 80 % lorsque des méthodes d'apprentissage automatique supervisées ont été appliquées pour classer de petites instances JSP générées aléatoirement en fonction de leur efficacité de planification optimale par rapport à la moyenne.

Exemple

Voici un exemple de problème d'ordonnancement d'atelier formulé en AMPL comme un problème de programmation en nombres entiers mixtes avec contraintes d'indicateurs :

paramètre N_JOBS ; paramètre N_MACHINES ;
définir les TRAVAUX ordonnés = 1 .. N_TRAVAUX ; définir les MACHINES ordonnées = 1 .. N_TRAVAUX ;
paramètre ProcessingTime { TRAVAUX , MACHINES } > 0 ;
param CumulativeTime { i dans JOBS , j dans MACHINES } = somme { jj dans MACHINES : ord ( jj ) <= ord ( j )} ProcessingTime [ i , jj ];
param TimeOffset { i1 dans JOBS , i2 dans JOBS : i1 <> i2 } = max { j dans MACHINES } ( CumulativeTime [ i1 , j ] - CumulativeTime [ i2 , j ] + ProcessingTime [ i2 , j ]);
var fin >= 0 ; var start { TRAVAUX } >= 0 ; var précède { i1 dans JOBS , i2 dans JOBS : ord ( i1 ) < ord ( i2 )} binaire ;
minimiser makespan : fin ;
subj à makespan_def { i dans JOBS } : fin >= début [ i ] + somme { j dans MACHINES } ProcessingTime [ i , j ];
soumis à no12_conflict { i1 dans JOBS , i2 dans JOBS : ord ( i1 ) < ord ( i2 )}: précède [ i1 , i2 ] ==> début [ i2 ] >= début [ i1 ] + TimeOffset [ i1 , i2 ];
soumis à no21_conflict { i1 dans JOBS , i2 dans JOBS : ord ( i1 ) < ord ( i2 )}: ! précède [ i1 , i2 ] ==> début [ i1 ] >= début [ i2 ] + TimeOffset [ i2 , i1 ];
données ;
paramètre N_JOBS : = 4 ; paramètre N_MACHINES : = 4 ;
paramètre ProcessingTime : 1 2 3 4 : = 1 5 4 2 1 2 8 3 6 2 3 9 7 2 3 4 3 1 5 8 ;

Problèmes connexes

L'ordonnancement Flow-shop est un problème similaire mais sans la contrainte que chaque opération doit être effectuée sur une machine spécifique (seule la contrainte d'ordre est conservée).
La planification en atelier ouvert est un problème similaire mais également sans la contrainte de commande.