[PYTHON] Mit OR-Tools erlernte Optimierung [Lineare Planung: Projektmanagement]

Dieser Blog ist was

Wir lernen die mathematische Optimierung mit von Google entwickelten OR-Tools. Der größte Teil des Inhalts basiert auf diesem Buch. Practical Python AI Projects: Mathematical Models of Optimization Problems with Google OR-Tools (English Edition)

Klicken Sie hier, um eine Liste der Codes nach Autor anzuzeigen Der in diesem Blog beschriebene Code entspricht fast dem Originalcode des Autors und ist nur teilweise auf Japanisch korrigiert.

Mathematische Genauigkeit und theoretischer Kommentar haben eine niedrige Priorität. Bitte verzeih mir.

Diesmal: Lineare Planung-Projektmanagement-

Wenn es mehrere Aufgaben gibt, jede mit einer erforderlichen Zeit und einer vorhergehenden Aufgabe, möchten wir eine Möglichkeit, diese in kürzester Zeit zu erledigen.

Szeneneinstellung

Takashi beschloss, das Kochen zu versuchen, weil er während der Zeit der Selbstbeherrschung frei war. Der Autor ist übrigens ein schlechter Koch, deshalb habe ich vielleicht etwas Passendes geschrieben. Takashi, der sich entschied, Curry und Reis wie ein Grundschüler eines Jungen zuzubereiten, wollte es schneller machen können als eine qualifizierte Mutter. Curryreis hat mehrere Prozesse, aber welcher Prozess sollte gestartet werden und wann sollte die Garzeit am kürzesten sein?

Punkt

Der entscheidende Punkt bei Fragen des Projektmanagements ist groß ・ Zeitaufwand für jede Aufgabe ・ Vorgängeraufgabe jeder Aufgabe Es gibt zwei. Eine Vorgängeraufgabe ist eine Aufgabe, die abgeschlossen sein muss, bevor Sie die Aufgabe starten können. Im Beispiel Curry und Reis lauten die Vorgängeraufgaben für "Fleisch und Gemüse braten" "Fleisch und Gemüse schneiden" und "Salatöl in eine Pfanne streuen". Das ist bei Curry und Reis der Fall, die ich kenne.

Lassen Sie mich für den Rest der Diskussion die Geschichte ein wenig verallgemeinern. Für jedes Element gibt es eine Reihe von Aufgaben $ T $ · Benötigte Zeit ・ Vorgängeraufgabe, die eine Teilmenge von $ T $ ist (leere Menge ist ebenfalls möglich) es gibt. Ein Beispiel ist in der folgenden Tabelle dargestellt.

Die Aufgabe scheint numerisch und anorganisch zu sein. Wenden Sie sie daher entsprechend an. Es kann zu viele Prozesse für Curry und Reis geben. Wahrscheinlich indisches Curry.

Formulierung

Lassen Sie es uns mit einer mathematischen Formel ausdrücken. In diesem Beispiel lautet die entscheidende Variable "Welche Aufgabe soll wann gestartet werden?". Indem Sie diese Variable gut festlegen und dabei die Einschränkungen der Vorgängeraufgabe einhalten, können Sie die Zeit für die Ausführung der letzten Aufgabe minimieren.

Lassen Sie die Aufgabenmenge $ T $ sein und definieren Sie die Startzeit jeder Aufgabe wie folgt.

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

Im Beispiel in der obigen Tabelle ist $ t_0 = 3 $, $ t_5 = 7 $. Um die Einschränkungen der Vorgängeraufgabe zu berücksichtigen, müssen die für die Aufgabe $ i $ erforderliche Zeit (entsprechend der zweiten Spalte der Tabelle) und die Teilmenge $ T_i \ Teilmenge T $ (Tabelle) die Vorgängeraufgabe der Aufgabe $ i $ darstellen. Bereiten wir uns vor (entsprechend der dritten Reihe von). Mit diesen wird die untere Grenzwertbeschränkung der Startzeit der Aufgabe $ i $ durch die folgende Formel ausgedrückt.

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

Zum Beispiel ist die Vorgängeraufgabe von Aufgabe 7 6, also muss $ t_6 + D_6 (= 7) \ leq t_7 $ gelten.

Es scheint hartnäckig zu sein, aber der Zweck dieser Zeit ist es, die Zeit für die Fertigstellung des Projekts zu minimieren (hier Curryherstellung). Wenn jede Aufgabe nacheinander ausgeführt wird, gilt (Startzeit der letzten Aufgabe + erforderliche Zeit). In der Realität ist dies nicht der Fall und einige Aufgaben sollten parallel bearbeitet werden. Ich weiß nicht, dass sich das Kochen aufgrund dieser parallelen Verarbeitung von erfahrenen Hausfrauen unterscheidet. Was ist, wenn ich nicht weiß, welche Aufgabe die letzte ist oder wenn es keine letzte Aufgabe gibt?

Daher werden wir eine neue Variable $ t $ einführen. Legen Sie für diese Variable eine Einschränkung fest, die "größer als die Startzeit einer Aufgabe + die erforderliche Zeit" ist.

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

Und wenn Sie $ t $ minimieren möchten, ist $ t $ die Projektabschlusszeit.

Implementierung

Hier ist der Code zur Lösung dieses Beispiels. my_or_tools.py und tableutils.py Den Inhalt finden Sie unter Author GitHub.

my_project_management.py

from my_or_tools import ObjVal, SolVal, newSolver

def solve_model(D):
  s = newSolver('Project management')                       #Löser deklarieren
  n = 12                                                    #Anzahl der Aufgaben
  max = sum(D[i][1] for i in range(n))                      #Berechnen Sie die Obergrenze der Determinante
  t = [s.NumVar(0,max,'t[%i]' % i) for i in range(n)]       #Determinante Variable. Startzeit der Aufgabe i
  Total = s.NumVar(0,max,'Total')                           #Endzeit. Ich möchte diese Zeit minimieren.
  for i in range(n):  
    s.Add(t[i]+D[i][1] <= Total)                            #Einschränkungen, die die Zielfunktion erfüllen muss
    for j in D[i][2]:
      s.Add(t[j]+D[j][1] <= t[i])                           #Einschränkungen bei Vorgängeraufgaben
  s.Minimize(Total)
  rc = s.Solve()
  return rc, SolVal(Total),SolVal(t)

Data = [    [0, 3, []],                                     #Beispieldaten
            [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':                                 #Daten anzeigen, wenn das Argument Daten sind
        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':                                #Wenn das Argument ausgeführt wird, wird das Ausführungsergebnis angezeigt.
        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()

Ergebnis

Der obige Code gibt Ihnen die folgende optimale Lösung.

Wie Sie der Tabelle entnehmen können, beträgt die kürzeste Endzeit 28. Wenn Sie eine Zeitplantabelle erstellen, sieht diese wie folgt aus.

Beachten Sie dabei, dass einige Aufgaben Ihre Gesamtarbeitszeit bei jedem Start nicht beeinflussen, solange sie nach der Vorgängeraufgabe liegen. Aufgabe 11 soll in letzter Minute beginnen, obwohl Aufgabe 0 der vorhergehenden Aufgabe zum Zeitpunkt 3 endet. Tatsächlich ändert sich in dieser Formulierung die optimale Lösung in Abhängigkeit vom Löser. (Der optimale Wert der Arbeitszeit ändert sich nicht)

Eine andere Lösung und ein anderer Zeitplan sind unten aufgeführt.

Die Aufgabe unten hat sich etwas nach links verschoben. Solange die Vorgängeraufgabe abgeschlossen ist, ist es praktisch, die Aufgabe so schnell wie möglich zu starten. Dies liegt daran, dass das Projekt selten wie geplant verläuft und letztere die Gesamtarbeitszeit weniger wahrscheinlich verlängern, wenn etwas schief geht.

Die abgedunkelten Aufgaben (0,2,1,6,7,9) in der Tabelle sind kritische Pfade. Einfach ausgedrückt: Wenn Sie eine dieser Verzögerungen verzögern, erhöht sich die Gesamtarbeitszeit. In diesem Beispiel ist es offensichtlich, ob Sie eine Tabelle erstellen, dies gilt jedoch nicht für ein großes Projekt mit vielen Prozessen. Ich werde mich auch mit der Berechnung des kritischen Pfades in der Zukunft befassen.

Um eine Lösung zu finden, um die Aufgabe so schnell wie möglich zu starten

Sie können die Zeile mit der Aufschrift "s.Minimize (Total)" in "s.Minimize (Summe (t [i] für i im Bereich (n))") umschreiben.

Zusammenfassung

Takashi gelang es, das Verfahren zur Herstellung von Curryreis in kürzester Zeit zu finden, aber die Mutter, die seit 15 Jahren Hausfrau ist, verlor die für jede Aufgabe erforderliche Zeit, die kürzer als Takashi war.