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

مسابقة تخصص · Recherche Opérationnelle

Formation doctorale Mathématiques Appliquées, Spécialités : ROMaD, Épreuve de spécialité, USTHB, Faculté de Mathématiques — 26 Octobre 2017.

التمرين 1

Exercice 1 — Ordonnancement de flow-shop à deux machines (Johnson)

#flow-shop#johnson-algorithm#scheduling#gantt-diagram

Une entreprise de Bâtiments et Travaux Publics est spécialisée dans la réalisation d'ouvrages d'art en béton armé. Pour effectuer ses travaux, elle dispose de deux corps de métier, les coffreurs et les maçons (le coffrage doit précéder le bétonnage). Cette entreprise doit réaliser six travaux dont les durées estimées (en jours) sont :

Numéro du travail	1	2	3	4	5	6
Durée de Coffrage ( $M_1$ )	3	1	6	10	6	3
Durée de Béton ( $M_2$ )	4	3	7	6	4	6

a. Cherchant à optimiser la durée totale de réalisation, vous devez proposer à cette société l'ordre de prise en compte des travaux. (Donner un ordonnancement optimal). b. Avec cet ordre quel est le nombre de jours économisés par rapport à une prise en compte des fabrications dans l'ordre de leur arrivée ? c. Si on doit tenir compte d'un temps inter-opératoire fixe de deux jours entre la fin du coffrage et le début du béton (1 jour imputable au coffrage et l'autre au béton), que devient l'ordre que vous avez proposé ? Donner l'ordonnancement optimal.

◀الحل

a.

Par l'algorithme de Johnson : on classe les travaux en comparant $p_{i1}$ et $p_{i2}$ . Si $p_{i1} \leq p_{i2}$ , le travail va en début (ordre croissant de $p_{i1}$ ). Sinon en fin (ordre décroissant de $p_{i2}$ ). Travaux avec $p_{i1} \leq p_{i2}$ : {1,2,3,6}. Travaux avec $p_{i1} \gt p_{i2}$ : {4,5}. Ordre optimal : 2, 1, 6, 3, 5, 4 (ou similaire selon l'algorithme).

\boxed{\text{Ordre de Johnson : 2, 1, 6, 3, 5, 4}}

b.

Calculer $C_{\max}$ pour l'ordre naturel (1,2,3,4,5,6) et l'ordre optimal par diagramme de Gantt. La différence donne les jours économisés.

c.

Avec le temps inter-opératoire, on modifie l'algorithme de Johnson en ajustant les durées : $p'_{i1} = p_{i1} + 1$ et $p'_{i2} = p_{i2} + 1$ . On réapplique Johnson.

\boxed{\text{Réappliquer Johnson avec les durées ajustées}}

التمرين 2

Exercice 2 — Problème de tournées de véhicules (ambulances)

#vehicle-routing#tsp#scheduling#transportation

Une société d'ambulance assure, pour l'hospitalisation à domicile, un service de transport des malades lorsque ceux-ci doivent subir des examens de contrôles à l'hôpital (H). Une journée type se déroule comme suit :

En début de journée, on connaît la liste des malades à transporter à l'hôpital.
La société n'est pas tenue de respecter un horaire précis. Elle organise ses transports, puis prévient chaque malade de l'heure de départ qu'elle a choisie.
À huit heures, une ambulance (A) part du garage (G), va chercher à son domicile le premier patient (P1), le transporte vers H, puis se rend au domicile du second patient (P2), etc. Après le dernier malade, l'ambulance retourne au garage.
Pour le retour des malades, une autre ambulance (B) reconduit, après examen, les malades à leurs domiciles respectifs. Le coût d'exploitation des ambulances se compose d'un coût fixe (salaires) et d'un coût proportionnel à la distance.

a. On souhaite organiser la journée de sorte à minimiser les coûts d'exploitation. Quelles tournées faut-il prévoir pour les ambulances A et B ?

◀الحل

a.

Pour l'ambulance A (aller) : c'est un problème de voyageur de commerce (TSP) partant du garage G, passant par les domiciles des patients dans un ordre optimal, déposant chacun à H, puis retournant au garage. L'objectif est de minimiser la distance totale.

Pour l'ambulance B (retour) : c'est un TSP inverse, partant de H, récupérant les patients après examen, les reconduisant à leurs domiciles, puis retournant au garage.

La tournée optimale pour A est : G → P le plus proche → ... → H → ... → G (résolu par heuristique du plus proche voisin ou méthode exacte pour petit nombre de patients).

\boxed{\text{TSP pour chaque ambulance}}

→←

→السابقConcours Doctorat 2017 — Université des Sciences et de la Technologie Houari Boumediène (USTHB) — Épreuve N°03 التاليConcours Doctorat 2017 — Université des Sciences et de la Technologie Houari Boumediène (USTHB) — Épreuve N°04←