Optimisation apprise avec OR-Tools [Planification linéaire: gestion de projet]

Ce blog est ce que

Nous apprendrons l'optimisation mathématique à l'aide des outils OR développés par Google. La plupart du contenu est basé sur ce livre. Practical Python AI Projects: Mathematical Models of Optimization Problems with Google OR-Tools (English Edition)

Cliquez ici pour une liste des codes par auteur Le code décrit dans ce blog est presque le même que celui d'origine de l'auteur, et il n'est que partiellement corrigé en japonais.

La rigueur mathématique et les commentaires théoriques sont peu prioritaires. S'il vous plaît, pardonnez-moi.

Cette fois: Planification linéaire-Gestion de projet-

Lorsqu'il y a plusieurs tâches, chacune avec un temps requis et une tâche précédente, nous voulons un moyen de la terminer dans les plus brefs délais.

Réglage de la scène

Takashi a décidé d'essayer la cuisine parce qu'il était libre pendant la période de maîtrise de soi. Au fait, l'auteur est un mauvais cuisinier, alors j'ai peut-être écrit quelque chose d'approprié. Takashi, qui a décidé de faire du curry et du riz comme un élève du primaire, voulait pouvoir le faire plus vite qu'une mère habile. Le riz au curry a plusieurs processus, mais quel processus doit être lancé et quand le temps de cuisson doit-il être le plus court?

point

Le point clé dans les problèmes de gestion de projet est grand ・ Temps requis pour chaque tâche ・ Tâche prédécesseur de chaque tâche Il y en a deux. Les tâches prédécesseurs sont des tâches qui doivent être terminées avant de pouvoir démarrer la tâche. Dans l'exemple du curry et du riz, les tâches précédentes pour «faire frire la viande et les légumes» sont «couper la viande et les légumes» et «saupoudrer l'huile de salade dans une poêle». C'est le cas du curry et du riz que je connais.

Pour le reste de la discussion, permettez-moi de généraliser un peu l'histoire. Il y a un ensemble de tâches $ T $, chaque élément · Temps requis ・ Tâche prédécesseur qui est un sous-ensemble de $ T $ (un ensemble vide est également possible) il y a. Un exemple est présenté dans le tableau ci-dessous.

La tâche semble être numérique et inorganique, veuillez donc l'appliquer de manière appropriée. Il peut y avoir trop de processus pour le curry et le riz. Probablement du curry indien.

Formulation

Exprimons-le avec une formule mathématique. Dans cet exemple, la variable décisive est "quelle tâche commencer quand". En décidant bien cette variable tout en respectant les contraintes de la tâche précédente, vous pouvez minimiser le temps nécessaire pour terminer la dernière tâche.

Soit l'ensemble des tâches $ T $ et définissez l'heure de début de chaque tâche comme suit.

0 \leq t_i \quad \forall i \in T

Dans l'exemple du tableau ci-dessus, $ t_0 = 3 $, $ t_5 = 7 $. Pour prendre en compte les contraintes de la tâche prédécesseur, le temps nécessaire à la tâche $ i $ (correspondant à la deuxième colonne du tableau) et le sous-ensemble $ T_i \ sous-ensemble T $ (tableau) représentant la tâche prédécesseur de la tâche $ i $. Préparons-nous (correspondant à la troisième ligne de). En utilisant ces derniers, la contrainte de limite inférieure de l'heure de début de la tâche $ i $ est exprimée par la formule suivante.

t_j + D_j \leq t_i \quad \forall j \in T_i ; \forall i \in T

Par exemple, la tâche prédécesseur de la tâche 7 est 6, donc $ t_6 + D_6 (= 7) \ leq t_7 $ doit tenir.

Cela semble persistant, mais le but de ce temps est de minimiser le temps pour terminer le projet (ici la fabrication du curry). Si chaque tâche est effectuée à tour de rôle, (heure de début de la dernière tâche + heure requise) est applicable. En réalité, ce n'est pas le cas et certaines tâches doivent être traitées en parallèle. Je ne sais pas si la cuisine est différente de celle des femmes au foyer vétérans à cause de ce traitement parallèle. Que faire si je ne sais pas quelle tâche est la dernière, ou s'il n'y a pas une dernière tâche?

Par conséquent, nous allons introduire une nouvelle variable $ t $. Pour cette variable, placez une contrainte qui "est supérieure à l'heure de début de toute tâche + l'heure requise".

t_i + D_i \leq t \quad \forall i \in T

Et si vous voulez minimiser $ t $, $ t $ sera le temps d'achèvement du projet.

la mise en oeuvre

Voici le code pour résoudre cet exemple. my_or_tools.py et tableutils.py Veuillez consulter Author GitHub pour le contenu.

my_project_management.py

from my_or_tools import ObjVal, SolVal, newSolver

def solve_model(D):
  s = newSolver('Project management')                       #Déclarer le solveur
  n = 12                                                    #Nombre de tâches
  max = sum(D[i][1] for i in range(n))                      #Calculer la limite supérieure du déterminant
  t = [s.NumVar(0,max,'t[%i]' % i) for i in range(n)]       #Variable déterminante. Heure de début de la tâche i
  Total = s.NumVar(0,max,'Total')                           #Heure de fin. Je veux minimiser ce temps.
  for i in range(n):  
    s.Add(t[i]+D[i][1] <= Total)                            #Contraintes auxquelles la fonction objectif doit répondre
    for j in D[i][2]:
      s.Add(t[j]+D[j][1] <= t[i])                           #Contraintes sur les tâches prédécesseurs
  s.Minimize(Total)
  rc = s.Solve()
  return rc, SolVal(Total),SolVal(t)

Data = [    [0, 3, []],                                     #Exemple de données
            [1, 6, [0]],
            [2, 3, []],
            [3, 2, [2]],
            [4, 2, [1,2,3]],
            [5, 7, []],
            [6, 7, [0,1]],
            [7, 5, [6]],    
            [8, 2, [1,3,7]],
            [9, 7, [1,7]],
            [10, 4, [7]],
            [11, 5, [0]]    ]                                                    


def main():
    import sys
    import tableutils
    n = len(Data)
    C = Data
    if sys.argv[1]=='data':                                 #Afficher les données si l'argument est des données
        T=[]
        for i in range(n):
            TT=[C[i][0],C[i][1]]
            s='{'
            for j in C[i][2]:
                s = s+' '+str(j)
            s=s+' }'
            TT.append(s)
            T.append(TT)
        T.insert(0,['Task', 'Duration','Preceding tasks'])
        tableutils.printmat(T,True)
    elif sys.argv[1]=='run':                                #Si l'argument est exécuté, le résultat de l'exécution est affiché.
        rc,V,G=solve_model(C)
        T=[]
        TT=['Task']+[C[i][0] for i in range(n)]
        T.append(TT)
        TT=['Start']+[int(G[i]) for i in range(n)]
        T.append(TT)
        TT=['End']+[int(G[i]+C[i][1]) for i in range(n)]
        T.append(TT)
        tableutils.printmat(T,True)

main()

résultat

Le code ci-dessus vous donnera la solution optimale suivante.

Comme vous pouvez le voir dans le tableau, l'heure de fin la plus courte est 28. Si vous créez une table de nomenclature, ce sera comme suit.

Une chose à garder à l'esprit ici est que certaines tâches n'affecteront pas votre temps de travail global à chaque fois que vous démarrez, tant qu'elles sont après la tâche précédente. La tâche 11 est censée commencer à la dernière minute même si la tâche 0 de la tâche précédente se termine au temps 3. En fait, dans cette formulation, la solution optimale change en fonction du solveur. (La valeur optimale du temps de travail ne change pas)

Une autre solution et un calendrier sont présentés ci-dessous.

La tâche en bas s'est légèrement déplacée vers la gauche. Tant que la tâche précédente est terminée, il est pratique de démarrer la tâche dès que possible. En effet, le projet se déroule rarement comme prévu, et ce dernier est moins susceptible d'augmenter le temps de travail global en cas de problème.

Les tâches assombries (0,2,1,6,7,9) dans le tableau sont des chemins critiques. En termes simples, retarder l'un de ces éléments augmentera le temps de travail global. Dans cet exemple, c'est évident si vous créez un tableau, mais ce n'est pas le cas pour un grand projet avec de nombreux processus. Je traiterai également de la façon de calculer le chemin critique à l'avenir.

Pour obtenir une solution pour démarrer la tâche le plus tôt possible

Vous pouvez réécrire la ligne qui dit s.Minimize (Total) en s.Minimize (sum (t [i] for i in range (n))).

Résumé

Takashi a réussi à trouver la procédure pour faire du riz au curry dans les plus brefs délais, mais la mère qui est femme au foyer depuis 15 ans a perdu le temps nécessaire pour chaque tâche plus courte que Takashi.