# AMÉLIORATIONS CONCERNANT LA PROGRAMMATION TEMPORELLE DE LA FABRICATION EN SÉRIE

par

L. NÉMETI

(Cluj)

## 1. Introduction

Dans cet ouvrage, on présentera quelques considérations constituant certaines améliorations des résultats obtenus par l'auteur dans les ouvrages [9], [10] (voir aussi [8]).

Une première notion à analyser sera celle de la période de la fabrication. Nous entendons par fabrication en série une fabrication périodique où des ensembles de diverses tâches technologiques, tâches de fabrication, vont être réalisés. Les ensembles sont identiques entre eux, ils forment une suite (temporelle). La distance temporelle entre les commencements (ou bien entre les achèvements) de deux ensembles de tâches conséutifs de la suite donne justement la durée de la période. Soit donné (élaboré) un programme de fabrication d'un des ensembles de tâches mentionnées ci-dessus. Celui-ci peut être représenté le mieux par un diagramme Gantt (v. fig. 1). L'élaboration d'un tel programme est un problème de programmation temporelle de la fabrication (dit aussi l'ordonnancement des tâches, le problème de l'atelier).

Sur la figure, on a réservé à chaque machine à façonner un axe (axe du temps) et les tâches à réaliser sont indiquées par des segments (épaissis sur l'axe correspondant).
<figure><img src="image_1.png" /><figcaption>Fig. 1</figcaption></figure>

Dans ce programme, chaque machine possède un intervalle temporel de fonctionnement ; les longueurs (durées) de ces intervalles sont :

$$ \text{pour la machine no 1: } d_1 = t_{11} - t_{10} $$

$$ \text{pour la machine no 2: } d_2 = t_{21} - t_{20} $$

$$ \text{pour la machine no 3: } d_3 = t_{31} - t_{30} $$

On désignera par

$$ d = \max(d_1, d_2, d_3) \text{ ou plus généralement} $$

$$ (1.1) \qquad d = \max_k d_k $$

où $d_k$ désigne la durée de l'intervalle de fonctionnement de la machine n° k et la valeur de d indique la durée de la période de fabrication, puisqu'après le déroulement de cette durée (calculée du moment de départ de chaque machine, c'est-à-dire de $t_{10}$ respectivement de $t_{20}$ resp. de $t_{30}$ etc.), le procèsus de fabrication peut être recommencé en réalisant l'ensemble de tâches suivant.

Une autre notion, c'est le cycle de fabrication. Sa durée est

$$ \delta = \max(t_{11}, t_{21}, t_{31}) - \min(t_{10}, t_{20}, t_{30}) $$

c'est-à-dire la durée de l'intervalle temporel pendant lequel la réalisation d'un ensemble de tâche a lieu.

On a

$$ (1.2) \qquad \delta \geq d. $$

Si la durée de la période diminue, cela veut dire que la production en un intervalle fixé (par ex. en un an) croît et les réalisations valoriques

<figure><img src="image_2.png" /><figcaption>Fig. 2</figcaption></figure>

de l'entreprise (par ex. les revenus nets) croissent aussi. Si la durée du cycle de fabrication diminue, cela veut dire que les fonds pour les produits „en cours” sont immobilisés pour une durée plus courte, les frais afférents à cette immobilisation (intérêts) diminuent aussi, ce qui équivaut du point de vue économique à une croissance des revenus. En conclusion, on demandera que les deux durées soient minimales.

À propos de ces remarques, on devra reviser la définition de la durée de la période donnée par la formule (1.1). En effet, il y a des cas où l'on peut réduire cette durée au dessous de la valeur indiquée par cette formule.

Considérons le programme de fabrication représenté dans la figure 2.

La machine n° 1 fonctionne dans les intervalles $[0,2[$, $[4,5[$ et $[8,9[$ et la machine n° 2 dans $[1,5[$. Supposons que les pauses dans le fonctionnement de la machine n° 1 sont conditionnées par des causes technologiques. Par exemple, la tâche n° 4 ne peut pas être commencée avant le moment $t=4$, car la tâche précédente (qui est réalisée sur une autre machine qui n'est pas indiquée dans le diagramme afin de ne pas compliquer la représentation) vient d'être terminée seulement à ce moment. Conformément à la définition (1.1), la durée de la période serait $d=9$. Mais cette période peut être raccourcie de la manière suivante (voir fig. 3).

On peut placer la tâche n° 2 dans l'intervalle vide $[2,4[$ bien entendu pas pour l'ensemble de tâches n° 1, dont la réalisation est représentée dans la figure 2, mais pour l'ensemble précédent, celui avec le n° 0. Dans la figure 3, on a représenté deux périodes consécutives ; on y voit la réalisation intégrale de l'ensemble de tâches n° 1 et des parties des ensembles n° 0 et n° 2, la durée de la période étant cette fois égale à 5 (au lieu de 9) unités de temps. Comme on peut le constater, les cycles de fabrication ne sont plus disjoints mais ils se recouvrent partiellement. En fait, le programme de la figure n° 3 est en essence identique au programme de la figure 2.

<figure><img src="image_3.png" /><figcaption>Fig. 3</figcaption></figure>
gramme de la figure 2, mais la répartition des tâches sur les divers ensembles est autrement faite. Par cet artifice, nous avons réduit la durée de la période de $d = 9$ à $d = 5$ pendant que la durée du cycle $\delta = 9$ est restée la même pour les deux variantes du programme.

Nous développerons cette idée d'une manière plus générale (l'idée du schéma qui suit appartient à M. B. Sussmann, maître de recherches à SEMA, Paris). Il y a plusieurs machines, on a réparti à chaque machine des tâches qui lui appartiennent (cette distribution est déterminée par le procédé technologique adopté). Pour chaque tâche, on en connaît la durée d'exécution. Il y a des paires de tâches (les deux tâches appartiennent en général à des machines différentes) pour lesquelles on donne une relation de succession technologique : la deuxième tâche ne peut être commencée qu'après l'achèvement de la première. On peut déterminer pour chaque machine la durée minimale nécessaire pour la réalisation de toutes les tâches qui y sont réparties. Cette durée $T_h$ (pour la machine n° k) est égale à la somme des durées d'exécution des tâches réparties à la machine n° k. La durée minimale de la période est alors évidemment

$$ (1.3) \qquad d = \max_h T_h $$

ce qui remplace la formule (1.1).

On peut construire un programme qui réalise cette durée $d$ (1.3) de la manière suivante :

Dans le diagramme Gantt, l'axe des temps pour chaque machine sera divisé en des périodes de durée $d$ (l'origine arbitraire de ces périodes sera la même pour toutes les machines, voir fig. n° 4). Dans une période quelconque (par ex. dans celle n° 1), on fixera, dans un ordre arbitraire, toutes les tâches — chacune sur la machine à laquelle elle appartient. La seule restriction est que les intervalles d'exécution des tâches appartenantes à la même machine, soient disjoints. Les longueurs des segments représentant les tâches seront proportionnelles aux durées correspondantes.

Sur la figure, c'est la machine n° 1 qui est la plus chargée, c'est elle qui détermine la durée $d$ de la période. Les nombres sur les segments des tâches indiquent leur numérotation, d'ailleurs arbitraire.

Ce programme sera transposé, sans modifications, aux autres périodes. Nous avons déjà dit, que le procédé technologique établit des relations de succession entre certaines paires de tâches. Soit par exemple (1,6) une telle paire. On tracera alors un vecteur de succession de l'extrémité à droite (achèvement) de l'intervalle n° 1 à l'extrémité à gauche (commencement) de l'intervalle n° 6. Soit (6,8) une autre paire de cette sorte. Ici, dans la période n° 1, la réalisation de la tâche no 8 commence avant que la tâche no 6 ne soit terminée. Pour cette raison, le vecteur de succession sera tracé de l'achèvement de la tâche n° 6 de la période n° 1 au commencement de la tâche n° 8 de la période n° 2; l'intervalle n° 8 de la période n° 1 appartiendra à l'ensemble de tâches qui précède l'ensemble n° 1, étudié.

<figure><img src="image_4.png" /><figcaption>Fig. 4</figcaption></figure>

En procédant de cette manière pour toutes les paires de tâches liées par des relations technologiques de succession, on établira le programme de fabrication, avec une durée minimale de la période de fabrication $d$. Le cycle de fabrication dure de la période n° 1 jusqu'à la dernière période $n$ chez laquelle on constate encore l'existence de vecteurs de succession entre deux tâches appartenant à l'ensemble n° 1 de tâches. Cette durée $\delta$ dépend de l'ordre choisi des tâches sur les diverses machines. On cherche précisément l'ordre optimal des tâches qui minimise la durée $\delta$ du cycle de fabrication.

Cette méthode est susceptible de diverses généralisations. D'abord, une paire de tâches comme (6,8) peut être programmée dans la même
période, c'est-à-dire que le vecteur de succession sera orienté à gauche et non à droite en admettant qu'on a réalisé — dans une période de préparation — un stock tampon avant la machine n° 3 sur laquelle on doit réaliser la tâche n° 8. Alors, quand on devra commencer la réalisation de cette tâche, on utilisera de ce stock tampon ; ce stock, consommé, sera complété à nouveau après l'achèvement de la tâche n° 6 et il attendra d'être utilisé, dans la période prochaine, pour rendre possible le commencement de la tâche n° 8 du *prochain* ensemble de tâches.

De cette façon, le cycle de fabrication peut être raccourci, lui aussi, mais on aura, en revanche, un accroissement des stocks tampon lesquels immobilisent des fonds, une circonstance qui fait naître, elle aussi, des frais supplémentaires.

Une autre généralisation consiste dans la possibilité de ne pas choisir la valeur minimale pour la durée de la période. Une période un peu plus longue permettra peut-être un raccourcissement de la durée du cycle de fabrication ou bien une diminution des stocks tampon.

En conclusion, on aura trois grandeurs à minimiser :

*d*: la durée de la période de fabrication

*δ*: la durée du cycle de fabrication

*σ*: la valeur totale des stocks tampon.

Dans cet ouvrage, on discutera deux modalités de composer la fonction économique à optimiser.

Dans les paragraphes 2, 3 et 4, on choisira à priori $d = d_{min}$ où $d_{min}$ est la durée définie par la formule (1.3) et on demandera de minimiser une combinaison, une fonction de $\delta$ et $\sigma$. On abordera dans le paragraphe 5 le cas plus général d'une fonction économique $f(d, \delta, \sigma)$. Enfin dans le paragraphe n° 6, on étudiera la situation plus générale quand il y a plusieurs exemplaires du chaque type de machines, cas dans lequel la distribution des tâches sur les exemplaires individuels du même type de machines n'est plus déterminée par la technologie utilisée.

## 2. Le modèle n° 1

Ce modèle représente la situation dans laquelle il y a un seul exemplaire de chaque type de machines et dans laquelle on donne une priorité absolue à la réduction de la durée de la période de fabrication par rapport à la diminution des frais liés à l'immobilisation des fonds circulants (des „en cours”).

On fixe donc la durée de la période égale à la quantité *d* donnée par la formule (1.3). Les tâches à réaliser (on peut appeler *opération* l'action de réaliser une tâche) sont numérotées, d'ailleurs arbitrairement, de 1 à *n*. Ces nombres forment l'ensemble

$$N = \{1, 2, \dots, n\}$$

représentant l'ensemble des opérations.

Désignons par $H = \{(i, j)\} \subset N \times N$ l'ensemble des paires (ordonnées) de tâches entre lesquelles il y a une relation de succession technologique ; la relation $(i, j) \in H$ affirme que la tâche *j* est successeur technologique immédiat de la tâche *i*. L'ensemble $H$ est antisymmétrique en ce sens qu'on a

$$ (2.2) \qquad (i, j) \in H \Rightarrow (j, i) \notin H. $$

Désignons par $J = \{(i, j)\} \subset N \times N$ l'ensemble des paires de tâches qui vont être réalisées sur la même machine. L'ensemble $J$ est symmétrique en ce sens qu'on a

$$ (2.3) \qquad (i, j) \in J \Leftrightarrow (j, i) \in J. $$

Afin de simplifier nos considérations, nous choisirons la durée *d* fixée par (1.3) comme unité de temps. Le moment du commencement de l'opération *i* sera désigné par $x_i$. Si l'opération *i* commence au moment $x_i$, alors il y a aussi une opération *i* (appartenant bienentendu à un autre ensemble de tâches, différent de l'ensemble étudié) dont le moment de commencement est $x_i + k$, où *k* est un entier quelconque. Afin de fixer le lieu précis des tâches, on numérotera les ensembles successifs de tâches et on précisera que $x_i$ appartient à l'opération *i* de l'ensemble n° 1 de tâches.

La partie entière de $x_i: n_i = [x_i]$ précise la période dans laquelle l'opération *i* commence; la partie fractionnaire de $x_i: \xi_i = \{x_i\}$ précise la place du moment de commencement de l'opération *i*, dans l'intérieur de la période.

On se donne le temps d'exécution $t_i$ de l'opération *i*, $t_i$ étant un nombre positif plus petit que l'unité (avec l'échelle de temps choisie). On suppose qu'une opération une fois commencée, elle ne sera plus interrompue jusqu'à son achèvement complet.

On suppose encore qu'une machine exécute en un moment donné une opération au plus et qu'une opération sera exécutée sur une seule machine.

On fera encore une simplification. On fera abstraction du temps de réglage (temps de préparation) des machines nécessaire en vue du commencement d'une opération et aussi du temps de manipulation (contrôle, transport etc.) après l'achèvement de l'opération (voir [8], [9], [11]). Ces simplifications sont d'ailleurs insignifiantes.

D'autres inconnues sont :

$$ s_i, i \in N' $$

qui indiquent la grandeur du stock tampon préparé à l'avance pour assurer l'exécution ininterrompue de l'opération *i*. L'unité de mesure est ici la quantité des produits (par ex. le lot de pièces à façonner) soumis à l'exécution de l'opération respective. $N' \subset N$ est le sous-ensemble des tâches qui possèdent des précédents technologiques :

$$ (2.4) \qquad N' = \{j | (i, j) \in H\}. $$
Les grandeurs $s_i$ sont par définition positives :

$$ (2.5) \qquad s_i \ge 0, \quad i \in \mathcal{N}'. $$

On désigne encore par

$$ (2.6) \qquad \delta = n_0 + \xi_0 $$

$(n_0: \text{entier}, 0 \le \xi_0 < 2)$. Cette formule doit être interprétée comme suit : $\delta$ est la distance temporelle du moment initial de la première opération de l'ensemble n° 1 de tâches ($t_0 = 0$) jusqu'au moment ($t_u$) de l'achèvement de la dernière opération ($\delta = t_u - t_0 = t_v$). Cette dernière opération commence dans la période n° $n_0$. Toutes les opérations de l'ensemble n° 1 des tâches qui commencent dans cette période $n_0$ forment la classe des dernières opérations de l'ensemble considéré.

En ce qui concerne la grandeur $s_i$ du stock tampon, on introduira une restriction qui d'une part simplifiera beaucoup les calculs et qui d'autre part approximera mieux la situation réelle.

Jusqu'ici les grandeurs $s_i$ n'étaient soumises qu'aux conditions (2.5). Mais il est évident que des valeurs $s_i > 1$ n'ont aucune justification technico-économique. De même, un stock tampon $0 < s_i < 1$ est inefficace. En effet, si on a $s_i < 1$, alors ce stock n'assurera pas nécessairement le déroulement ininterrompu de l'opération $i$, car il pourrait arriver que le stock s'épuise et l'opération $k$ ($(k, i) \in H$) ne soit pas encore terminée. On n'admettra donc pour $s$ que les valeurs 0 ou 1.

Après ces considérations préliminaires, nous passons à la construction du modèle mathématique de notre problème. Les inconnues en sont :

$$ n_i, \xi_i, i \in \mathcal{N} $$

$$ s_i, i \in \mathcal{N}' $$

de même que

$$ n_0 \text{ et } \xi_0 $$

et elles doivent minimiser la fonction économique

$$ (2.7) \qquad z = n_0 + \xi_0 + \sum_{i \in \mathcal{N}'} \alpha_i s_i $$

avec les coefficients positifs $\alpha_i$ donnés. La justification de cette forme résultera du paragraphe 4.

Les inconnues sont soumises aux restrictions suivantes :

$$ (2.8a) \qquad n_i \ge 0, \text{ entier}, \quad i \in \mathcal{N} $$

$$ (2.8b) \qquad 0 \le \xi_i < 1, \quad i \in \mathcal{N} $$

$$ (2.8c) \qquad s_i \ge 0, \quad i \in \mathcal{N}' $$

$$ (2.8d) \qquad n_0 - n_i \ge 0, \quad i \in \mathcal{N} $$

$$ (2.8e) \qquad \xi_0 - \xi_i \ge t_i, \quad i \in \mathcal{N}^0, $$

$$ (2.8f) \qquad \xi_0 - \xi_i \ge t_i - 1, \quad i \in \mathcal{N}^1. $$

On a désigné ici par

$$ (2.9) \qquad \begin{cases} \mathcal{N}^0 = \{i \mid n_i = n_0\} \subset \mathcal{N} \\ \mathcal{N}^1 = \{i \mid n_i = n_0 - 1\} \subset \mathcal{N} \end{cases} $$

les classes des dernières opérations.<fnref n="2" />

En dehors de ces restrictions, on doit encore formuler deux conditions essentielles. La première s'appelle la restriction de la continuité et elle exprime les conditions dans lesquelles le déroulement ininterrompu des opérations est assuré. On doit avoir donc une relation entre les inconnues $n, \xi, s$ d'une paire d'opérations $(i, j) \in H$.

Le modèle doit contenir quatre situations typiques (voir fig. 5) :

<figure><img src="image_5.png" /><figcaption>Fig. 5</figcaption></figure>

<footnote n="2">² Ces ensembles ne sont pas donnés en préalable; ils sont déterminés par la solution du problème.</footnote>
I, la situation a) est caractérisée par les conditions

$$
(2.10) \qquad \begin{cases} \xi_j - \xi_i \ge t \\ n_j - n_i \ge 0; \end{cases}
$$

la situation b) par

$$
(2.11) \qquad \begin{cases} \xi_j - \xi_i \ge t_i - 1 \\ n_j - n_i \ge 1; \end{cases}
$$

la situation c) par

$$
(2.12) \qquad n_j - n_i \ge 2;
$$

enfin la situation d) par

$$
(2.13) \qquad s_j \ge 1.
$$

Nous faisons remarquer que les conditions (2.8c) et (2.7) assurent
l'annulation de s_j dans les trois premières situations, de même que s_j = 1
résulte de (2.7) et (2.13).

Ces quatre conditions seront réunies dans une seule qui contient aussi
la signe $\lor$ de la disjonction logique :

$$
(2.14) \quad \begin{gathered} \xi_j - \xi_i \ge t_i, n_j - n_i \ge 0 \lor \xi_j - \xi_i \ge t_i - 1, n_j - n_i \ge 1 \lor \\ n_j - n_i \ge 2 \lor s_j \ge 1, \quad (i,j) \in H^{(3)} \end{gathered}
$$

I, la deuxième condition s'appelle celle de la non-interférence ou du
chargement et assure que les intervalles de temps $[n_i + \xi_i, n_i + \xi_i + t_i[$
qui représentent l'exécution d'une opération et qui se rapportent aux
opérations sur la même machine ($(i, j) \in J$) sont disjoints. En fait, ces
conditions ne contiennent que les inconnues $\xi_i$.

Supposons qu'on ait fixé l'opération i avant l'opération j. Deux
situations peuvent alors être envisagées (fig. 6).

Dans la situation a), on doit avoir

$$
(2.15) \qquad \xi_j \ge \xi_i + t_i.
$$

<figure><img src="image_6.png" /><figcaption>Fig. 6</figcaption></figure>

Dans la situation b), aux conditions (2.15) s'ajoute la restriction

$$
(2.16) \qquad \xi_j + t_j - 1 \le \xi_i,
$$

condition vérifiée d'ailleurs aussi dans la situation a). En tenant compte
de la possibilité d'inverser l'ordre de i et j, les conditions cherchées seront.

$$
(2.17) \quad \begin{gathered} \xi_j - \xi_i \ge t_i, \quad \xi_i - \xi_j \ge t_j - 1 \quad \forall \quad \xi_i - \xi_j \ge t_j, \quad \xi_j - \xi_i \ge t_i - 1, \\ [i, j] \in \mathcal{J}^4 \end{gathered}
$$

Les formules (2.7) (2.8), (2.14) (2.17) constituent conjointement le modèle n° 1 de l'ordonnancement des opérations dans le cas de la production en série, ce modèle constitue un problème de programmation linéaire avec des conditions logiques (disjonctions).

Pour la résolution d'un problème d'un tel type on utilise le procédé
bien connu Branch and Bound (respectivement S.E.P. resp. l'algorithme
de RADÓ [3], [5], [15], [16]). Il serait superflu, à notre avis, de décrire
ici cette méthode, nous mentionnons seulement qu'elle revient à la résolution
d'une suite de problèmes de programmations „ordinaires" dénommés
problèmes fondamentaux du problème considéré. Dans le paragraphe
suivant, on présentera l'énoncé de ces problèmes fondamentaux, les métho-
des de leur résolution et on montrera comment de nouveaux problèmes
fondamentaux résultent des problèmes fondamentaux déjà résolus.

<footnote n="3">³ La virgule qui intervient à l'interieur d'un terme de la disjonction, signifie comme d'habitude la conjonction logique.</footnote>

<footnote n="4">⁴ Dans cette formule, les paires $[i, j]$ sont non-ordonnées, c'est-à-dire que les paires $(i, j)$ et $(j, i)$ se confondent.</footnote>
### 3. Les problèmes fondamentaux

Un problème fondamental $\mathcal{Q}$ est constitué par les conditions „ordonnaires” du modèle considéré (les restrictions (2.7) et (2.8)) et par un des termes de chaque élément d'un sous-ensemble donné de l'ensemble $H \cup J$ des disjonctions (2.13) et (2.16).

On se donne donc les ensembles $H_1, H_2, H_3, H_4$ disjoints deux à deux et pour lesquels on a

$$ (3.1) \qquad H_0 = H_1 \cup H_2 \cup H_3 \cup H_4 \subset H; $$

$J_1$ et $J_2$, disjoints, pour lesquels on a

$$ (3.2) \qquad J_0 = J_1 \cup J_2 \subset J. $$

On construit avec ces ensembles les ensembles suivants :

$$ (3.3) \qquad \left\{ \begin{array}{l} H' = H_1 \cup H_2 \cup H_3 \\ J' = H_1 \cup H_2 \cup J_0 \cup \bar{J}_0 \\ N_0 = \{J \mid (i, j) \in H_4\}. \end{array} \right. $$

Ici, l'ensemble $\bar{A}$ des paires de nombres est défini par la relation

$$ (3.4) \qquad (i, j) \in A \Leftrightarrow (j, i) \in \bar{A}. $$

On désigne encore par

$$ (3.5) \qquad a_{ij} = \begin{cases} 0, & (i,j) \in \begin{Bmatrix} H_1 \\ H_2 \\ H_3 \end{Bmatrix} \\ 1, & (i,j) \in \begin{Bmatrix} H_1 \\ H_2 \\ H_3 \end{Bmatrix} \\ 2, & (i,j) \in \begin{Bmatrix} H_1 \\ H_2 \\ H_3 \end{Bmatrix} \end{cases}. $$

Le problème $\mathcal{Q}$ prend alors l'aspect suivant :

$$ (3.6) \qquad \begin{cases} \xi_j - \xi_i \ge t_i, \\ \xi_j - \xi_i \ge t_i - 1, \end{cases} \quad \begin{array}{l} (i, j) \in H_1 \cup J_1 \cup \bar{J}_2 \\ (i, j) \in H_2 \cup J_2 \cup \bar{J}_1 \end{array} $$

$$ (3.7) \qquad n_j - n_i \ge a_{ij}, \quad (i, j) \in H' $$

auxquels on ajoute les restrictions

$$ (3.8) \qquad \left\{ \begin{array}{l} n_i \ge 0 \text{ entier} \\ 0 \le \xi_i < 1 \\ n_0 - n_i \ge 0 \\ \xi_0 - \xi_i \ge t_i, \quad i \in \mathbb{N}^0 \\ \xi_0 - \xi_i \ge t_i - 1, \quad i \in \mathbb{N}^1 \end{array} \right. \qquad i \in N $$

et on demande que la valeur de la fonction

$$ (3.9) \qquad y = n_0 + \xi_0 + \sum_{i \in N_0} \alpha_i $$

devienne minimale.

Nous faisons d'abord la remarque que les restrictions de $\mathcal{Q}$ se divisent en deux parties : la première ne contient que les inconnues $n_i$, la seconde seulement les $\xi_i$.

Nous avons par conséquent

$$ (3.10) \qquad \left\{ \begin{array}{l} n_i \ge 0 \text{ entier} \\ n_0 - n_i \ge 0 \end{array} \right. \qquad i \in N $$

$$ (3.11) \qquad n_j - n_i \ge a_{ij}, \quad (i, j) \in H' $$

en demandant que $n_0$ soit minimal (le problème $Q_n$) : et

$$ (3.12) \qquad \left\{ \begin{array}{l} 0 \le \xi_i < 1, \quad i \in N \\ \xi_0 - \xi_i \ge t_i, \quad i \in \mathbb{N}^0 \\ \xi_0 - \xi_i \ge t_i - 1, \quad i \in \mathbb{N}^1 \end{array} \right. $$

$$ (3.13) \qquad \xi_j - \xi_i \ge b_{ij}, \quad (i, j) \in J' $$

en demandant que $\xi_0$ soit minimal (le problème $Q_\xi$). On a utilisé ici la notation

$$ b_{ij} = \begin{cases} t_i, & (i,j) \in \begin{Bmatrix} H_1 \cup J_1 \cup \bar{J}_2 \\ H_2 \cup J_2 \cup \bar{J}_1 \end{Bmatrix} \\ t_i - 1, & (i,j) \in \begin{Bmatrix} H_1 \cup J_1 \cup \bar{J}_2 \\ H_2 \cup J_2 \cup \bar{J}_1 \end{Bmatrix} \end{cases}. $$

En vue de la résolution du problème $Q_n$, on attache aux relations (3.11) un graphe $G(N, H')$ orienté, en attribuant à un arc $(i, j) \in H'$ la longueur $a_{ij}$. Le problème $Q_n$ est un problème de potentiel (voir par ex. [1], [2] ou [17]) dont on cherche la solution minimale universelle. À cause de la
longueur 0, 1 ou 2 des arcs, cette solution vérifie automatiquement la première condition (3.10) et on obtient

$$ (3.14) \qquad n_0 = \max_{i \in N} n_i. $$

La solution obtenue détermine aussi les ensembles $N^0$ et $N^1$.

Si le problème $Q_n$ est compatible, alors les circuits éventuellement existants ne contiennent que des arcs de longueur 0 et c'est pourquoi toutes les valeurs $n_i$ appartenant aux sommets d'un circuit (et plus généralement d'une composante fortement connexe) seront égales entre elles. Si l'on forme donc le graphe réduit $G*(N^*, H^*)$ correspondant aux composantes fortement connexes de $G$, alors ce graphe sera sans circuits et la solution minimale universelle du problème $Q_n$ peut être obtenue rapidement.

Passons au problème $Q_ξ$. On attache aux conditions (3.13) un graphe orienté $Γ(N, J')$ dont les arcs auront la longueur $b_{ij}$. Ces conditions constituent elles aussi un problème de potentiel qui est compatible si est seulement si le graphe $Γ$ ne possède aucun circuit de longueur strictement positive. Si cette condition est satisfaite, alors en y ajoutant la restriction $ξ_i ≥ 0$, $i ∈ N$, on en peut déterminer la solution minimale universelle. Les méthodes de résolution afférentes sont itératives et bien connues. Si et seulement si la solution obtenue vérifie aussi les conditions $ξ_i < 1$, le problème $Q_ξ$ est compatible et on a

$$ (3.15) \qquad \xi_0 = \max \left[ \max_{i \in N^0} (\xi_i + t_i), \max_{i \in N^1} (\xi_i + t_i) \right]. $$

Pour la comparaison des solutions des divers problèmes fondamentaux, on utilisera la fonction $y$ dans (3.9).

On déduit d'un problème fondamental résolu plusieurs problèmes fondamentaux nouveaux $Q'_1, Q'_2$ (ev. encore $Q'_3, Q'_4$) comme suit.

À l'occasion de la formation du problème fondamental $Q$, on a utilisé une partie $H_0 ⊂ H$ des disjonctions (2.14) et une partie $J_0 ⊂ J$ des disjonctions (2.17). La solution obtenue vérifiera aussi une partie de $H-H_0$ (qui peut être d'ailleurs vide) et de $J-J_0$. On désignera les ensembles des disjonctions non vérifiées par la solution par $K ⊂ H-H_0$ resp. $L ⊂ J-J_0$. On choisira de l'ensemble $K ∪ L$ un des éléments (une disjonction (2.14) ou (2.17)) et on ajoutera un à un les termes de cette disjonction choisie aux conditions du problème $Q$. Si cette disjonction est du type (2.17) c'est-à-dire à deux termes, on obtiendra deux problèmes fondamentaux nouveaux $Q'_1$ et $Q'_2$. Si la disjonction choisie est du type (2.14), on en obtiendra quatre : $Q'_1, Q'_2, Q'_3$ et $Q'_4$. Nous soulignons que dans ce dernier cas, la solution de $Q'_4$ est identique à la solution de $Q$, mais l'ensemble $N_0$ utilisé pour le calcul de la valeur de la fonction $y$ (3.9) s'augmentera d'un élément nouveau.

### 4. Simplifications et particularisations ; le modèle no 2

Dans ce qui suit, on montrera quelques particularisations du modèle présenté dans le paragraphe 2. Ces modèles particularisés peuvent être résolus plus facilement, mais leurs solutions donnent des valeurs supérieures pour $y$ à la valeur minimale de $y$ qu'on obtiendrait par la solution du modèle du paragraphe 2. Il s'agit donc de solutions approximatives.

A) On obtient une première approximation par la condition supplémentaire

$$ (4.1) \qquad s_i = 0, \quad i \in N' $$

c'est-à-dire que nous renonçons à priori aux stocks tampon. Par cette mesure, le quatrième terme des disjonctions (2.13) sera éliminé ce qui réduit le nombre des problèmes fondamentaux.

La fonction utilisée pour la comparaison des solutions sera

$$ (4.2) \qquad y_A = n_0 + \xi_0. $$

B) On obtient une autre simplification plus grande par la restriction

$$ (4.3) \qquad n_0 = n_i^* = 0, \quad i \in N. $$

Les restrictions (2.14) sont remplacées cette fois par

$$ (4.4) \qquad \xi_j - \xi_i \ge t_i \lor s_i = 1, \quad (i, j) \in H $$

ce qui d'une part réduit sensiblement le nombre des problèmes fondamentaux à résoudre, mais aussi les inconnues $n_i$ y manquent. Un problème fondamental aura la forme

$$ (4.5) \qquad \left\{ \begin{array}{l} \xi_i \ge 0 \\ \xi_i \le 1 - t_i \\ \xi_j - \xi_i \ge b_{ij}, \end{array} \right. \quad i \in N, (i, j) \in J' $$

et on en demande la solution minimale universelle. Si elle existe, on obtient

$$ (4.6) \qquad \xi_0 = \max_{i \in N} (\xi_i + t_i) $$

et la grandeur de comparaison sera

$$ (4.7) \qquad z_B = \xi_0 + \sum_{i \in N_0} \alpha_i. $$
On remarque qu'au cas B), les ensembles $H_2$ et $H_3$ (voir (3.1)) sont vides.

Dans la plupart des cas, la méthode B) donnera des résultats meilleurs que l'approximation A). En effet, avec la méthode B), on raccourcit la durée du cycle de fabrication en augmentant les stocks tampon. Mais les frais indirects pour une période sont proportionnels à la valeur totale du lot de produits tandis que la valeur du stock tampon pour une opération n'est qu'une fraction de cette valeur totale.

Nous présenterons maintenant une généralisation du modèle du paragraphe 2, le modèle no 2. Dans ce modèle, nous ne fixerons plus la durée de la période égale à la durée minimale possible, car il se pourrait qu'avec une durée un peu plus longue de la période, les économies obtenues par la diminution des „en cours” contrebalancent la perte de revenu causée par la prolongation de la durée de la période. On aura donc comme paramètres du problème les quantités $d$, $\delta$ et $\sigma = \sum \alpha_i$.

Les restrictions du problème souffrent de légères modifications. On écrira pour les moments de commencement

$$ (4.8) \qquad x_i = d(n_i + \xi_i) $$

et au lieu de la formule (2.6) :

$$ (4.9) \qquad \delta = d(n_0 + \xi_0). $$

Dans les conditions (2.8), (2.14) et (2.17), la quantité $t_i$ sera remplacée partout par $t_i/d$.

Une analyse économique plus approfondie donne (maximiser le revenu net total annuel) la forme suivante pour la fonction économique :

$$ (4.10) \qquad w = \frac{A}{d} - (n_0 + \xi_0 + d + \sum_{i \in N_0} \alpha_i) : \max l $$

La formule (2.7) en résulte immédiatement avec $d = 1$.

Les problèmes fondamentaux, résultats de ce système de restrictions ne sont plus des problèmes de potentiel, ils ne sont plus même linéaires. Afin de les résoudre, on pourra les considérer comme des problèmes de programmation (de potentiel) paramétrique, avec le paramètre $d$. Alors on devra résoudre une suite de tels problèmes avec différentes valeurs pour $d$ en approximant la solution optimale avec la précision souhaitée.

Sous ce rapport il est utile d'en savoir plus sur l'allure de la fonction $w_{max}(d)$. Une telle remarque est la suivante. On a

$$ (4.11) \qquad \lim_{d \to \infty} w_{max} = -\infty. $$

En vue de la détermination de la valeur $d_{opt}$ qui maximise la fonction $w_{max}(d)$, la méthode présentée dans [14] peut être utile.

## 5. Plusieurs machines du même type

La méthode d'approximation qui va être proposée représente une généralisation du modèle n° 1. L'idée fondamentale consiste en cela que les tâches qui vont être réalisées sur un type donné de machines — répartition déterminée par le processus technologique — seront distribuées d'avance sur les exemplaires du type en question, avant la construction proprement dite du programme. Cette distribution constitue donc le premier pas de l'établissement du programme. La répartition se fait de la manière suivante :

Sur un type donné de machines dont il y a $\mu$ exemplaires, on doit réaliser $v$ tâches dont les temps d'exécution forment l'ensemble $T = \{t_1, t_2, \dots, t_v\}$. On cherche une partition de $T$ en $\mu$ sous-ensembles

$$ (5.1) \qquad T = \bigcup_{k=1}^{\mu} T_k $$

laquelle minimise la grandeur

$$ (5.2) \qquad S^* = \max_{k=1, \dots, \mu} S_k $$

où on a désigné par

$$ (5.3) \qquad S_k = \sum_{t_i \in T_k} t_i. $$

En vue de la réalisation de cette partition, nous proposons une méthode approximative.

On se donne la suite de nombres $T = (t_1, t_2, \dots, t_v)$ ordonnée non-croissante. On peut supposer que les nombres $t_i$ sont des nombres naturels. Désignons par

$$ (5.4) \qquad S = \sum_{i=1}^{v} t_i $$

et

$$ (5.5) \qquad M = \frac{S}{\mu}. $$

Afin de construire les sous-ensembles $T_k \subset T$ on séparera d'abord les éléments $t_i$ avec

$$ t_i \geq M. $$
Chacun de ces éléments constitue à lui seul un ensemble $T_k$. On désigne
dans ce qui suit par $[x]'$ le plus petit nombre entier qui n'est pas plus petit
que $x$. On détermine le nombre

$$
(5.6) \qquad P = \max ([t_1]', [M]'),
$$

Un sous-ensemble $T_k$ sera formé du plus grand nombre $t_i \in T$ encore non-utilisé pour la construction des ensembles $T_k$; on y ajoute le nombre $t_j \in T$ le plus grand suivant (de même encore non utilisé) pour lequel a lieu :

$t_i + t_j \le P.$

On continue ce procédé, en respectant toujours la condition

$$
(5.7) \qquad S_k \le P.
$$

On passe ensuite à la détermination du sous-ensemble $T_{k+1}$. Si l'on a construit tous les $\mu$ sous-ensembles $T_k$ avec $S_k \le P$ et s'il y a encore des éléments $t_i$ non-répartis, on utilise alors un procédé complémentaire. À savoir, le plus grand des éléments restés non-distribués sera réparti à l'ensemble $T_k$ avec le plus petit $S_k$. On continue ce procédé jusqu'à ce que tous les $t_i$ soient distribués.

Voici deux exemples illustratifs

$$
\text{Exemple 1.} \quad T = (10, 10, 10, 8, 8, 8, 7, 6, 6, 4, 3, 1, 1) \quad \begin{array}{c} v = 13 \\ S = 82, \mu = 6, M = 13,67, P = 14 \end{array}
$$

$$
T_1 = \{10, 4\} \qquad S_1 = 14
$$

$$
T_2 = \{10, 3, 1\} \qquad S_2 = 14
$$

$$
T_3 = \{10, 1\} \qquad S_3 = 11
$$

$$
T_4 = \{8, 6\} \qquad S_4 = 14
$$

$$
T_5 = \{8, 6\} \qquad S_5 = 14
$$

$$
T_6 = \{8\} \qquad S_6 = 8
$$

L'élément 7 est resté non-réparti. Le procédé complémentaire ajoute
cet élément à $T_6$ et on obtient $T'_6 = \{8, 7\}$, $S'_6 = 15 = S^*$. Distribution
optimale.

\textbf{Exemple 2.} $T = (11, 10, 9, 7, 5, 4, 3, 2) \quad \begin{array}{c} v = 8 \\ S = 51 \\ \mu = 3 \\ M = P = 17 \end{array}$

$$
T_1 = \{11, 5\} \quad S_1 = 16
$$

$$
T_2 = \{10, 7\} \quad S_2 = 17
$$

$$
T_3 = \{9, 4, 3\} \quad S_3 = 16; \quad T'_3 = \{9, 4, 3, 2\} \quad S'_3 = 18.
$$

Cette distribution n'est pas optimale. Une telle solution est par exemple

$$
T_1 = \{11, 4, 2\}
$$

$$
T_2 = \{10, 7\}
$$

$$
S_1 = S_2 = S_3 = S^* = 17.
$$

$$
T_3 = \{9, 5, 3\}
$$

Remarque. Pour l'ordonnancement des opérations au cas de la fabri-
cation des unicats ou de petites séries (fabrication non périodique), il y
a d'autres modèles et méthodes de résolution basées dans la plupart des
cas de même sur des techniques Branch and Bound. Ces problèmes ne
sont pas très difficiles dans le cas où chaque machine est d'un autre type
([6], [18]), mais il deviennent très complexes, s'il y a plusieurs exemplaires
de chaque type ([4], [7], [8], [13]).

La méthode de la distribution préalable des tâches sur les exemplaires du type réduit le problème de l'atelier ici aussi au cas plus simple où il n'y a qu'un seul exemplaire de chaque type. On a ici une méthode approximative qui peut être utile.

En conclusion il faut dire que les modèles présentés conduisent à un
volume trop grand de calculs dans la plupart des cas pratiques. Par con-
séquent ils doivent être considérés comme des réserves scientifiques pour
les ordinateurs futurs, beaucoup plus puissants que les calculateurs actuels.
Il est possible d'ailleurs d'en déduire des méthodes d'approximation bien
appliquables.

BIBLIOGRAPHIE

[1] Berge, C., Théorie des graphes et ses applications. Paris, 1958.

[2] Berge, C., Ghouila-Houri, A., Programmes, jeux et réseaux de transport. Paris, 1962.

[3] Bertier, P., Roy, B., *Une procédure de résolution pour une classe de problèmes pouvant avoir un caractère combinatoire*. Bull. du Centre Intern. de calcul, Rome, 4, 1, 19-28 (1965).

[4] Descamps, R., Chevignon, P., Algorithmes d'optimisation pour une classe générale de problèmes d'ordonnancement avec limitation des vessources. Metra V, 4, 603-618 (1966).

[5] Ignali, E., Schrage, L., Application of the Branch and Bound Technique to some Flow-Shop Scheduling Problems. JORSA 13, 3, 400-412 (1965).

[6] Németi, L., Das Reihenfolgeproblem in der Fertigungsprogrammierung und Linearplanung mit logischen Bedingungen. Mathematika (Cluj), 6, 1, 87-99 (1964).

[7] — Über das Reihenfolgeproblem in der Fertigung im Falle mehrerer Maschinen derselben Art. Rev. Roum. Math. Pures et Appl. 13, 835-840 (1968).

[8] — Sur la programmation temporelle de la fabrication. Metra, VII, 327-338 (1968).

[9] — Das Reihenfolgeproblem in der Fertigung mit Pufferbeständen. Rev. Roum. Math. Pures et Appl. 13, 1009-1016 (1968).

[10] — Sur le problème de l'ordonnancement dans le fabrication en série. Rev. Fr. Inf. Rech. Op. 2, 47-60 (1968).
[11] — Über die Durchführungsdauer eines Arbeitsganges in der Ablaufplanung. Bull. Meth. Soc. Sc. Math. R.S. Roum. **12**, 3, 81–86 (1968).

[12] — On the Scheduling Problem in the Case of Several Machines of the Same Type. Mathematica (Cluj), **13**, 2, 251–261 (1971).

[13] Németi, L., Radó, F., *Sur la programmation temporelle de la fabrication. Mathe-matica (Cluj)*, **8**, 1, 109–111, (1966).

[14] Radó, F., *Le calcul approximatif des extrêmes d'une fonction. Mathematica (Cluj)*, 3, 1, 171–177 (1961).

[15] — Programare liniară cu condiții logice. Comun. Acad. R.P.R. **13**, 1039–1042 (1963).

[16] — Un algorithme pour résoudre certains problèmes de programmation mathématique. Mathematica (Cluj), **6**, 1, 105–116 (1964).

[17] Roy, B., *Cheminement et connexité dans les graphes. Application aux problèmes d'ordon-nancement*. Metra, Série spéciale n° 1, 1962.

[18] Roy, B., Sussmann, B., *Les problèmes d'ordonnancement avec contraintes disjonc-tives*. SEMA, Direction scientifique, Rapport de recherche no. 9, 1964.

Reçu le 15. XII. 1972.

Institutul de calcul din Cluj
al Academici Republicii Socialiste România