مسابقة دكتوراه 2013 — Université des Sciences et de la Technologie Houari Boumediène (USTHB) — الموضوع 04

مسابقة تخصص · Recherche Opérationnelle · المدة: 2سا

Concours d’accès à la Formation Doctorale Recherche Opérationnelle et Mathématiques Discrètes, ROMaD, épreuve de Recherche Opérationnelle, USTHB, Faculté de Mathématiques, 20 octobre 2013, durée 2h.

التمرين 1

Exercice 1 — Complexité de problèmes d’ordonnancement

#scheduling#complexity-theory#graham-notation

Définir et donner la complexité des problèmes suivants.

$P2\|C_{\max}$ .
$P\|\overline C$ .
$1|r_i|C_{\max}$ .
$1\|L_{\max}$ .
$1\|T_{\max}$ .
$1\|\sum w_i$ .
$F2\|C_{\max}$ .
$F3\|C_{\max}$ .
$F2|\text{no-wait}|C_{\max}$ .
$O2\|C_{\max}$ .

◀الحل

1.

$P2\|C_{\max}$ est faiblement NP-difficile.

2.

$P\|\overline C$ se résout par SPT.

3.

$1\|L_{\max}$ et $1\|T_{\max}$ se résolvent par EDD.

4.

$F2\|C_{\max}$ se résout par Johnson.

\boxed{F2\|C_{\max}\text{ est polynomial}}

\boxed{F3\|C_{\max}\text{ est fortement NP-difficile}}

التمرين 2

Exercice 2 — Ordonnancement sur trois machines

#flow-shop#parallel-machines#makespan

Les temps opératoires sont

\begin{array}{c|cccc}&T_1&T_2&T_3&T_4\\p_{1i}&8&5&6&7\\p_{2i}&2&4&1&3\\p_{3i}&4&5&3&2 \end{array}.

Déterminer un ordonnancement optimal pour $F3\|C_{\max}$ .
Déterminer un ordonnancement pour $R3\|C_{\max}$ .

◀الحل

1.

Comme $\min p_{1i}\ge\max p_{2i}$ , on applique la réduction de Johnson.

\boxed{\sigma=(T_2,T_1,T_4,T_3)}

2.

Le cas $R3\|C_{\max}$ se résout par une affectation équilibrée des tâches aux trois machines.

التمرين 3

Exercice 3 — File d’attente M/M/2

#queueing-theory#birth-death-process#stationary-distribution

Une file $M/M/2$ a un taux d’arrivée $\lambda$ , deux serveurs de taux $\mu$ et $\lambda\lt2\mu$ .

Établir les équations de Kolmogorov pour $P_k(t)$ .
Déterminer le régime permanent $P_k$ .
Un client arrive lorsque les deux serveurs sont occupés et que $n$ clients attendent. Aucun nouvel arrivant n’est ensuite accepté. a. Calculer son temps d’attente moyen. b. Calculer le temps moyen de vidage.

◀الحل

1.

\lambda_k=\lambda, \qquad \mu_k=\min(k,2)\mu.

2.

Avec $a=\lambda/\mu$ et $\rho=\lambda/(2\mu)$ ,

p_0=\left(1+a+\frac{a^2}{2(1-\rho)}\right)^{-1}.

3.

\boxed{\mathbb{E}(W)=\frac{n+1}{2\mu}}

\boxed{\mathbb{E}(T_{\mathrm{vide}})=\frac{n+4}{2\mu}}

التمرين 4

Exercice 4 — Fiabilité de m machines

#markov-chains#reliability#stationary-distribution

Une usine possède $m$ machines indépendantes. Chaque machine tombe en panne pendant une journée avec probabilité $1/2$ . Un technicien répare au plus une machine chaque soir. $X_n$ est le nombre de machines en marche au début du jour $n$ .

Modéliser la situation par une chaîne de Markov.
Justifier l’existence d’une distribution stationnaire.
Montrer que la proportion stationnaire des soirées travaillées vaut

p=1-\left(1-\frac1{2^m}\right)\pi_m.

◀الحل

1.

Si $X_n=i$ , le nombre de survivantes suit $\operatorname{Bin}(i,1/2)$ , puis

X_{n+1}=\min(m,Y+1).

2.

La chaîne est finie et possède une classe fermée accessible.

3.

\boxed{p=1-(1-2^{-m})\pi_m}

→←

→السابقمسابقة الدكتوراه 2013 — Université Badji Mokhtar - Annaba التاليConcours Doctorat 2013 — Université Frères Mentouri - Constantine 1 — Épreuve N°05←