Cours analyse de l’algorithme glouton

Interval Partitioning

■ Le cours j commence à l’instant sj et finit à l’instant fj.
■ But : trouver un nombre minimal de salles permettant de programmer les cours dans des salles distinctes.
Ex: 4 salles nécessaires pour programmer ces 10 cours.
■ Le cours j commence à l’instant sj et finit à l’instant fj.
■ But : trouver un nombre minimal de salles permettant de programmer les cours dans des salles distinctes.
Ex: Dans ce cas seulement 3 salles sont nécessaires.

Interval Partitioning : Algorithme glouton

Algorithme glouton. On considère les cours dans l’ordre chronologique de leur début : on attribue une salle compatible à chaque cours.
Trier les intervalles par ordre chronologique de leur fin de sorte que s1  s2  …  sn.
d  0
Nombre de salles utilisées
pour j = 1 à n {
si (le cours j est compatible avec une salle, k)
programmer le cours j dans la salle k
sinon utiliser une nouvelle salle d + 1 programmer le cours j dans la salle d + 1 d  d + 1
}
Implémentation. O(n log n).
■ Pour chaque salle k, on garde trace de l’instant de fin du dernier cours qui lui a été affecté.
■ On garde les salles dans une file de priorité (priority queue.)

Interval Partitioning : Analyse de l’approche gloutonne

Observation. L’algorithme glouton ne programme jamais deux cours incompatibles dans la même salle.

Théorème. L’algorithme glouton est optimal.

Preuve.
■ Soit d = nombre de salles que l’algorithme glouton affecte.
■ La salle d a été ouverte car il était nécessaire de programmer un cours, par exemple j, qui était incompatible avec les d-1 autres salles.
■ Puisqu’on trie selon l’ordre chronologique des débuts de cours, toutes ces incompatibilités étaient causées par des cours dont le début n’est pas postérieur à sj.
■ On a donc d cours qui se chevauchent à l’instant sj + e, pour un certain e >0.
■ Observation clé Þ aucune programmation ne peut utiliser moins de d salles. ▪

Minimiser le retard

Organiser les tâches afin de minimiser le retard
Minimizing lateness problem.
■ Un processeur (unique) exécute une tâche (et une seule) à la fois.
■ L’exécution de la tâche j demande tj unités de temps de travail du prcesseur et doit être achevée à l’instant dj.
■ Si la tâche j commence à l’instant sj, elle finit à l’instant fj = sj + tj.
■ Retard : j = max { 0, fj – dj }.
■ But : programmer les tâches afin de minimiser le retard maximal

Minimizing Lateness : algorithmes gloutons

“Gabarit” glouton. On traite les tâches dans un certain ordre.
■ [Shortest processing time first] On considère les tâches dans l’ordre croissant de leur durée d’exécution tj.
■ [Earliest deadline first] On considère les tâches dans l’ordre chronologique de leur instant-limite dj.
■ [Smallest slack] On considère les tâches dans l’ordre croissant des différences dj – tj.
“Gabarit” glouton. On traite les tâches dans un certain ordre.
■ [Shortest processing time first] On considère les tâches dans l’ordre croissant de leur durée d’exécution tj.
Algorithme glouton. Stratégie “Earliest deadline first”.
Trier les n tâches par date-limite d1  d2  …  dn t  0
pour j = 1 à n
Affecter la tâche j à l’intervalle [t, t + tj] sj  t, fj  t + tj
t  t + tj
retourner les intervalles [sj, fj]

Minimizing Lateness: analyse de l’algorithme glouton

Théorème. La programmation gloutonne S est optimale.
Preuve. Soit S* une programmation optimale ayant aussi peu d’inversions que possibles.
■ On peut supposer que S* ne programme aucune inactivité.
■ Si S* n’a pas d’inversion, alors S = S*.
■ Si S* a une inversion, soit i-j une inversion contiguë.
– échanger i et j n’accroît pas le retard et diminue (strictement) le nombre d’inversions
– cela contredit la définition de S*