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

التمرين 1

Exercice 1 — Ordonnancement F2||Cmax avec stockage et gestion de projet

#scheduling#flow-shop#resource-constrained#project-scheduling

Partie I : Soit le problème d'ordonnancement $F2\|C_{\max}$ avec un espace de stockage de capacité égale à $B$ .

Discuter la complexité du problème selon les valeurs de $B$ .
Donner une instance à 5 tâches et $B = 1$ ainsi qu'une solution optimale.
Proposer une méthode de résolution (discuter selon $B$ ).
Proposer un modèle mathématique linéaire.

Partie II :

Considérons une instance d'un projet à 6 tâches et une ressource de capacité 3 comme indiqué ci-dessous.

Tâche	Prédécesseurs	$p_i$	$q_i$
$T_1$	/	4	1
$T_2$	/	1	2
$T_3$	/	2	1
$T_4$	$T_1, T_2$	1	2
$T_5$	$T_3$	2	1
$T_6$	$T_5$	2	3

avec $p_i$ la durée du traitement et $q_i$ la quantité demandée de la ressource. Soit la liste de priorités : $T_2, T_4, T_3, T_5, T_6, T_1$ . Construire une solution en utilisant : a. La méthode sérielle. b. La méthode parallèle. 2. Donner une instance à 3 tâches et une ressource montrant l'instabilité des méthodes sérielles (c'est-à-dire que la date de fin de traitement du projet peut augmenter si on augmente la capacité de la ressource). 3. Donner une instance à trois tâches montrant l'impossibilité d'avoir une solution optimale à l'aide d'une méthode parallèle (utiliser une seule ressource et des dates de disponibilité).

◀الحل

Partie I

1.

Pour $B = \infty$ (stockage illimité), le problème $F2\|C_{\max}$ se résout en $O(n \log n)$ par l'algorithme de Johnson. Pour $B = 0$ (pas de stockage, blocking), le problème est NP-difficile. Pour $B$ fini intermédiaire, la complexité croît.

2.

Instance à 5 tâches avec $B=1$ : on peut prendre des tâches avec des durées variées et appliquer une heuristique de type Johnson modifié.

3.

Pour $B = \infty$ : algorithme de Johnson. Pour $B$ fini : heuristiques (NEH modifié) ou méthodes exactes (branch and bound).

4.

Modèle PLNE avec variables $x_{ij}$ (ordre), $C_i$ (dates de fin), contraintes de non-chevauchement et de capacité de stockage.

Partie II

1.a. Méthode sérielle

On ordonnance les tâches dans l'ordre de la liste de priorités, en respectant les contraintes de précédence et de ressource.

1.b. Méthode parallèle

À chaque instant, on ordonnance les tâches éligibles (prédécesseurs terminés, ressource disponible) selon la liste de priorités.

2.

Exemple classique d'anomalie : 3 tâches indépendantes avec $p_1 = p_2 = p_3 = 1$ , $q_1 = q_2 = 1$ , $q_3 = 2$ . Avec capacité 2 : $C_{\max} = 2$ . Avec capacité 3 : $C_{\max} = 1$ (meilleur). Mais avec un bon choix de paramètres, on montre l'instabilité.

3.

Avec dates de disponibilité différentes, la méthode parallèle (gloutonne) peut manquer la solution optimale car elle ne retarde jamais une tâche éligible.

\boxed{\text{Voir les constructions détaillées ci-dessus}}