Problème de séquencement des tâches

1. Triez tous les travaux par ordre décroissant de profit.
2. Initialisez la séquence de résultats avec le premier travail dans les travaux triés.
3. Faire pour les travaux restant (n-1)
   • Si le travail en cours peut tenir dans la séquence de résultats actuelle sans manquer la date limite, ajoutez le au résultat. Sinon ignorer le travail en cours.

# travaux : liste des travaux
# creneaux : nombre de créneaux horaires
def Sequencement(travaux, creneaux):

    # nombre de travaux
    n = len(travaux)

    # Trier les travaux dans l'ordre décroissant des bénéfices
    for i in range(n):
        for j in range(n - 1 - i):
            if travaux[j][2] < travaux[j + 1][2]:
                travaux[j], travaux[j + 1] = travaux[j + 1], travaux[j]

    # créneaux disponibles
    result = [False] * creneaux

    # résultat
    job = []

    # pour chaque travail
    for i in range(len(travaux)):

        # trouver créneau disponible
        for j in range(min(creneaux - 1, travaux[i][1] - 1), -1, -1):

            # créneau disponible
            if result[j] is False:
                result[j] = True
                job.append(travaux[i][0])
                break

    print(job)


# tester la fonction
travaux = [['a', 4, 20],  # travaux
           ['b', 1, 10],
           ['c', 1, 40],
           ['d', 1, 30]]


print("Ce qui suit est la séquence de profit maximum des travaux ")
Sequencement(travaux, 3)

            

                Ce qui suit est la séquence de profit maximum des travaux
                ['c', 'a']