Scribd
Importer
40 vues2 pages

Exercices d'Ordonnancement sur Machine

Ce document contient plusieurs exercices d'ordonnancement sur une seule machine. Les exercices proposent des problèmes d'ordonnancement avec différents objectifs (makespan, temps total, retard total) et donnent des instances à résoudre.

Transféré par

SALAH EDDINE
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
40 vues2 pages

Exercices d'Ordonnancement sur Machine

Ce document contient plusieurs exercices d'ordonnancement sur une seule machine. Les exercices proposent des problèmes d'ordonnancement avec différents objectifs (makespan, temps total, retard total) et donnent des instances à résoudre.

Transféré par

SALAH EDDINE
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

U.S.T.H.B.

/ Faculté de Mathématiques Année universitaire : 2019/2020


Département de Recherche Opérationnelle Matière : Ordo (M1, RO-2MIR)

Série d’exercices n˚2 (Ordonnancement sur une seule machine)

Exercice n˚ 1 : Donner une formulation mathématique sous forme d’un programme linéaire
mixte pour chacun des problèmes suivants :
1/ 1/ri /Lmax 4/ 1/ri /U 7/ 1/ri /L
2/ 1/ri /C 5/ 1/ri , delivery − time/Cmax 8/ 1/ri /T
3/ 1/prec, pi = 1/U 6/ 1/ri , dei /Cmax 9/ 1/ri /Tmax

Exercice n˚ 2 : Etant donné le tableau suivant :

Ti T1 T2 T3 T4 T5 T6 T7 T8
pi 10 2 4 7 3 1 3 2

Résoudre le problème 1//C.

Exercice n˚ 3 : Etant donné le tableau suivant :

Ti T1 T2 T3 T4 T5 T6 T7
pi 29 13 31 20 7 3 9
di 80 20 67 48 100 30 50

Résoudre le problème 1//Lmax

Exercice n˚ 4 : Soit l’instance à trois tâches et une machine :

Ti T1 T2 T3
pi 2 1 1
di 3 6 5

1/ Calculer Lmax pour la séquence T1 , T2 , T3 .


2/ Conclure.

Exercice n˚ 5 : Considérons un problème d’ordonnancement à une seule machine avec les


données suivantes :

Ti T1 T2 T3 T4 T5
pi 7 8 4 6 6
di 9 17 18 19 21

1/ Déterminer un ordonnancement optimal pour le critère Tmax .


2/ Déterminer un ordonnancement optimal pour le critère U .

1
Exercice n˚ 6 : Considérons l’instance à une machine et 7 tâches :
Ti T1 T2 T3 T4 T5 T6 T7
pi 6 18 12 10 10 17 16
di 8 42 44 24 90 85 68
1/ Déterminer un ordonnancement optimal pour le critère Tmax .
2/ Déterminer un ordonnancement optimal pour le critère U .
Exercice n˚ 7 : Etant donné le tableau suivant : Résoudre le problème 1//NT

Ti T1 T2 T3 T4 T5 T6 T7 T8 T9 T10
pi 5 3 1 2 4 4 2 1 1 4
di 19 16 25 3 8 14 31 23 2 15

Exercice n˚ 8 : Considérons le problème d’ordonnancement 1/pi = 1/Tw .


1/ Montrer que ce problème est équivalent au problème d’affectation.
2/ Donner une formulation mathématique adéquate.
3/ Conclure.

1
Pn
Exercice n˚ 9 : Considérons le problème d’ordonnancement 1//E où E = n i=1 Ei avec
Ei = max{0, di − Ci } et soit l’instance à trois tâches :

Ti T1 T2 T3
pi 2 1 2
di 3 7 5
1/ Donner un ordonnancement optimal. Combien peut-on en définir ?
2/ Montrer que le critère d’optimisation E n’est pas régulier.
P
3/ Montrer que T + E = n1 ni=1 |Ci − di |.
4/ Donner un ordonnancement optimal pour 1||T + E. Peut-on avoir un autre ?

Vous aimerez peut-être aussi