Algorithme de Johnson

Soyez le premier à donner votre avis sur cette source.

Snippet vu 1 007 fois

Contenu du snippet

Salut,

Je partage mon code de l'algorithme de Johnson pour trouver l'ordonnancement minimum de deux machines. J'ai codé en python 3. Il marche parfaitement pour n'importe quelle situation. C'est-à-dire qu'il prend en charge les doublons. Il faut bien suivre ce qu'on vous demande dans le code. N'hésitez pas à me poser une question. À vous de jouer !

"""
Réalise par : GIANNUZZI Anais
Fichier : main.c
Résume : algorithme de Johnson pour l'ordonnancement minimal
Date de création : le 18/04/20
Date de dernière modification : le 20/04/20
"""

#                   déclaration
L1 = [];
L2 = [];

list_machine1 = [[], []];
list_machine2 = [[], []];

list_final_tache = [];
list_final_ordre = [];

#                   affichage
print ("Bonjour tout le monde !n");
nombre_de_tache = int(input("Combien il y a de tâches ? "));

i = 0;
while i < nombre_de_tache :
#                   remplie les durées pour les deux machines
    print("Pour la tâche",i+1,",");
    duree_courante = int(input("Quelle est le temps de la machine 1 ? "));
    list_machine1[0].append(duree_courante);
    duree_courante = int(input("Quelle est le temps de la machine 2 ? "));
    list_machine2[0].append(duree_courante);
    i = i+1;
    
j = 0;
while j < nombre_de_tache :
#                   remplie les tâches
    list_final_tache.append(j+1);
    list_machine1[1].append(j+1);
    list_machine2[1].append(j+1);
    j = j +1

#                   liste de travail
W = list_machine1[0] + list_machine2[0];

while W != []:
#                   cherche le minimum
    minimum = min(W);
    if (minimum in list_machine1[0]) :
        index = list_machine1[0].index(minimum);
#                   garde en mémoire la tâche
        L1.append(list_machine1[1][index]);
#                   supprime
        del list_machine1[0][index];
        del list_machine2[0][index];
        del list_machine1[1][index];
        del list_machine2[1][index];
#                   nouvelle liste de travail
        W = list_machine1[0] + list_machine2[0];
    else :
        index = list_machine2[0].index(minimum);
#                   garde en mémoire la tâche
        L2.insert(0, list_machine2[1][index]);
#                   supprime
        del list_machine1[0][index];
        del list_machine2[0][index];
        del list_machine1[1][index];
        del list_machine2[1][index];
#                   nouvelle liste de travail
        W = list_machine1[0] + list_machine2[0];

#                   concaténation
list_final_ordre = L1 + L2;

#                   affichage
print ("n");
print ("tâche : ",list_final_tache);
print ("ordre : ",list_final_ordre);

A voir également

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.