Problème de séquencement des tâches

Do you want to read our courses in English? please visit our new website cs-teachers.com Click here

Problème de séquencement des tâches

Problème ! Étant donné un ensemble de travaux pour lesquels chaque travail a une date limite et les bénéfices associés si le travail est terminé avant la date limite. Il est également indiqué que chaque travail prend une seule unité de temps, de sorte que le délai minimum possible pour tout travail est 1. Comment maximiser le profit total si un seul travail peut être planifié à la fois.
Exemple :
travaildate limitebénéfice
a420
b110
c140
d130

  Ce qui suit est la séquence de profit maximum des travaux (c,a)

  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']
            

Partager ce cours avec tes amis :

Rédigé par M. ESSADDOUKI

Many people realize their hearts desires late in life. Continue learning, never stop striving and keep your curiosity sharp, and you will never become too old to appreciate life.

0 Commentaire(s)

Pour laisser un commentaire vous devez avoir un compte Inscription, ou Se connecter