Planification avec des délais

Énoncé de l'exercice conception et anlyse des algorithmes : Planification avec des délais

Une entreprise a une série de tâches \( J = \{1, 2, \ldots, n\} \) à exécuter. Chaque tâche \( i \) :

• Prend exactement une unité de temps à être exécutée.
• Génère un bénéfice \( g_i \) si elle est terminée avant sa date limite \( d_i \).

La ressource exécutant ces tâches ne peut réaliser qu'une seule tâche à un instant donné. L'objectif est de maximiser le bénéfice total tout en respectant les délais des tâches.

Données fournies

On vous donne :

1. Une liste de \( n \) tâches avec leurs bénéfices respectifs \( g_1, g_2, \ldots, g_n \).
2. Les délais associés \( d_1, d_2, \ldots, d_n \), indiquant la dernière unité de temps où une tâche peut être exécutée.

Exemple

Considérez les \( n = 4 \) tâches suivantes :

Questions

1. Déterminer les séquences possibles : Lister toutes les séquences réalisables des tâches (en respectant les dates limites) et calculer le bénéfice total pour chacune.
2. Identifier la séquence optimale : Quelle séquence maximise le bénéfice total ? Justifiez votre réponse.
3. Implémenter l'algorithme glouton : Développez un algorithme glouton pour résoudre ce problème. L'algorithme doit :
   • Trier les tâches par bénéfice décroissant.
   • Ajouter chaque tâche à une solution si elle respecte les contraintes de faisabilité (pas de dépassement de délai).
   Appliquez cet algorithme à l'exemple donné.
4. Propriété d'optimalité : Expliquez pourquoi cet algorithme glouton est optimal pour ce problème en vous basant sur les concepts de faisabilité et de maximisation du bénéfice.

5. Gestion de tâches supplémentaires :Si une tâche peut être partiellement exécutée pour un bénéfice proportionnel (par exemple, une tâche nécessitant 2 unités de temps donne la moitié de son bénéfice si elle n'est exécutée qu'une unité), comment adapteriez-vous l'algorithme ?

6. Complexité :Analysez la complexité temporelle de l'algorithme développé.