Ordonnancement des taches :

Étant donné un éventail d'emplois où chaque travail 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, de sorte que 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.

1) Triez tous les emplois par ordre décroissant de profit.
2) Initialisez la séquence de résultats comme premier travail dans les travaux triés.
3) Suivez les étapes pour les n-1 emplois restants
…… .a) Si le travail en cours peut tenir dans la séquence de résultats actuelle sans manquer la date limite, ajoutez le travail en cours au résultat. Sinon, ignorez le travail en cours.

Algorithme

Struct job {

Id :caractére ;

Dead :entier ;

Profit :entier ; }

Procedure jobselec (job arr[], n :entire,)

Debut

Sort(arr,arr+n,, comparaison)

Result[n] :entier, slot[n]:booléen;

Pour I allant de 0 à n-1 faire

Slot[i]ß false ;

Fin pour

Pour i allant de 0 à n-1 faire

                Pour j allant de min(n,arr[i].dead)-1 à 0 faire j—

                                Si slot[j]=false alors

                                                Result[j]ß i ;

                                                Slot[j]ß true ;

                                                Jß -1 ;

                                Finsi ;

                Fin pour

Fin pour

Pour i allant de 0 à n-1 faire

                Si slot[i]=true alors arr[result[i].id