Dans le problème de séquençage des tâches, l’objectif est de trouver la séquence des tâches, qui est terminée dans leurs délais et de donner un profit maximal.
Si un ensemble de n emplois est donné qui sont associés à des délais et que le profit est réalisé et qu’un travail est terminé avant son délai. Ces emplois doivent être commandés de manière à générer un profit maximal.
Prenons un exemple. Comme le montre la figure 1.1, un tableau d’emplois est donné où chaque emploi a une date limite et un bénéfice associé si le travail est terminé avant la date limite. Il est également donné que chaque travail prend une seule unité de temps, donc le délai minimum possible pour tout travail est de 1. Comment maximiser le profit total si un seul travail peut être planifié à la fois.
Une solution simple consiste à générer tous les sous-ensembles d’un ensemble donné de travaux et à vérifier la faisabilité des travaux dans ce sous-ensemble. Gardez une trace du profit maximal parmi tous les sous-ensembles réalisables. La complexité temporelle de cette solution est exponentielle.Nous pouvons également résoudre ce problème en utilisant une méthode gourmande qui est plus optimale qu’une solution simple.Permet donc de résoudre ce problème via une méthode gourmande.
Pour résoudre le problème de séquençage des tâches via la méthode greedy, procédez comme suit:
- Trier tous les emplois par ordre décroissant de profit.
- Initialisez la séquence de résultats en tant que première tâche dans les tâches triées.
- Procédez comme suit pour les tâches n-1 restantes.
- Si la tâche en cours peut s’insérer dans la séquence de résultats en cours sans manquer la date limite, ajoutez la tâche en cours au résultat. Sinon, ignorez le travail actuel.
Comme vous pouvez le voir sur la figure 1.1, les emplois sont déjà par ordre décroissant de profit.Ici, le travail 1 a le bénéfice le plus élevé et la date limite est de 3, alors définissez ce travail entre 2 et 3 comme indiqué dans la figure 1.2.Le travail 2 a le deuxième profit le plus élevé et la date limite est de 4, alors définissez ce travail entre 3 et 4 et faites de même pour tous jobs.So la séquence finale est J4 -J3 – J1-J2 et le bénéfice total est de 110.
Vous pouvez préférer le code de cet algorithme à https://www.geeksforgeeks.org/job-sequencing-problem.
La complexité temporelle de cette solution est O(n2). Elle peut être optimisée par une structure de données disjointe.
J’espère que vous aimez l’article.Merci 🙂
