Arbeitsaufgaben zuweisen [geschlossen]

Selbst bei einem Arbeiter ist dies ein NP-vollständiges Optimierungsproblem (es wird dann zum Problem des reisenden Verkäufers), also vergessen wir "optimal".

Wenn Sie wissen, dass der Arbeiter 1 die Aufgaben A1, A2, ..., Arbeiter 2 die Aufgaben B1, B2, ... und so weiter behandelt, können Sie nach dieser Entscheidung versuchen, die Aufgabe zu lösen die Probleme eines unabhängigen Geschäftsreisenden nacheinander, und Sie erhalten die Zeitpläne und Pfade für alle Ihre Mitarbeiter.

Das Problem ist jedoch, dass Sie nicht wissen können, wie lange es dauert, eine Reihe von Aufgaben A1, A2, ... für einen Arbeiter abzuschließen, bevor Sie das Problem des reisenden Verkäufers für diesen Satz gelöst haben, weil die Gehzeit sich auf die Gesamtzeit für die Ausführung der Aufgaben.

Da es nur ein Spiel ist und die Arbeiter als nicht optimale Denker angesehen werden können, würde ich einen stochastischen Prozess verwenden:

1. Weisen Sie allen Arbeitern nach dem Zufallsprinzip alle Aufgaben zu
2. Verwenden Sie einen Greedy-Algorithmus, um eine Obergrenze für die Gehzeit für jeden Mitarbeiter in der Aufgabengruppe des Mitarbeiters zu berechnen.
3. Versuchen Sie eine zufällige Bewegung, entweder eine Aufgabe von einem Arbeiter zu einem anderen zu verschieben oder Aufgaben zwischen zwei Arbeitern auszutauschen
4. Akzeptieren Sie diese Bewegung basierend auf Tabu Search- oder Simulated-Annealing-Prinzipien, je nachdem, ob die Verschiebung die Obergrenze der maximalen Ausführungszeit (Gehzeit + Taskausführungszeit) verringert, sodass das Ziel darin besteht, die letzte Aufgabe als zu beenden so früh wie möglich
5. Nach N Wiederholungen, stoppe und berechne bessere Lösungen für die Unterprobleme des reisenden Verkäufers, z. Verwenden stochastischer Suche oder explizit, wenn die Probleme klein sind (z. B. weniger als 10 Aufgaben pro Arbeiter)

Anstatt die Arbeiter gierig der nächsten Aufgabe zuzuweisen, versuchen Sie, gierig die am weitesten entfernte Aufgabe ihrem "nächsten" Arbeiter zuzuweisen - das heißt, dem Arbeiter, dessen Pfad eng ist und genügend Zeit hat, damit umzugehen. Auf diese Weise haben Sie eine (gierige) Vorstellung von der kleinsten Zeit, die benötigt wird, um alle Aufgaben zu erledigen.

Zum Beispiel:

D ist die "am weitesten entfernte Aufgabe", auch wenn Sie diesen Begriff noch nicht definiert haben, also ordnen Sie D 1 zu. Es ist 15 + 10 Einheiten entfernt, also setzen Sie t = 25 und die Lücke auf 2 bis 25.

Hier sind nun die Entfernungskosten für die Zuweisung der nächsten Aufgabe unter Berücksichtigung der kürzesten Routen.

Aber hier sind die wahren Kosten nach der gierigen Idee; die Erhöhung auf die maximale Zeit t .

Da C die höchsten Kosten hat (es ist die gefährlichste Aufgabe aus einer gierigen Perspektive), Weisen Sie C 2 zu.

Die nächsten Kosten sind wie folgt

Weisen Sie B zu, weil 22 die größte Zunahme der maximalen Zeit t ist. Weisen Sie es dem Arbeiter 2 zu.

...

Es gibt viele Ansätze für ein Rucksack-Problem, aber wenn Einfachheit gewünscht wird, ist dies wahrscheinlich das nächste, was zu versuchen ist. Vielleicht speichern Sie die kürzesten Wege zwischen den Aufgaben. Es ist eine offen gierige Art, die ein wenig voraus denkt!

Das klingt tatsächlich sehr nach dem (bereits erwähnten) Traveling Salesman Problem (TSP, Ссылка ) für mehrere Agenten. Welches ist eigentlich ein Problem ähnlich wie Multiple Rucksack (MKP, Ссылка ) oder sogar Bin-Verpackung ( Ссылка ).

Es gibt eine Gruppe von Algorithmen, die in dieser Situation geeignet sein könnten, und sie wird 'Ameisenkolonie-Optimierung' genannt (ACO, Ссылка ).

Um beides zu kombinieren, gibt es Implementierungen, die ACO verwenden, um MKP-Probleme zu lösen; Dies scheint in diesem Fall ein guter Weg zu sein, zum Beispiel:

Ссылка

Da es sich um ein RTS-Spiel handelt, würde ich versuchen, einen einfachen, schnellen und leicht verständlichen Ansatz zu wählen.

1. Es muss schnell sein, weil Leistung zählt
2. Es muss leicht verständlich sein , warum ein Arbeiter hier und dort hin geht, weil in einem Spiel die Schergen sich wie erwartet verhalten sollen. Versuche nicht, an die Spieler zu denken.

Zuerst würde ich natürlich den gierigen Ansatz versuchen. Aber du hast bereits erwähnt, dass es einfach nicht funktioniert.

Als nächstes würde ich etwas wie einen Greedy-Algorithmus zweiter Ordnung versuchen. Jeder Arbeiter wählt die nächste Aufgabe A und wählt dann die nächsten Aufgaben B neben A. Sie versuchen (!), Aufgaben auszuwählen, die bisher noch niemand ausgewählt hat. So ähnlich.

Halte es klein und einfach. Und beachten Sie: Egal welchen Algorithmus Sie gewählt haben, wird ein Fall sein, in dem es kläglich scheitert. Schließlich gibt es kein kostenloses Mittagessen .

Ich würde vorschlagen, dass etwas ähnlich wie TobiMcNamobi , aber raffinierter ist:

• Initialisieren Sie eine leere Arbeitswarteschlange für jeden Worker und eine Zeit z , die benötigt wird, um diese Warteschlange zu beenden.
• Geben Sie jeder Aufgabe eine Eigenschaft d , die auf 0 gesetzt wird. Sie gibt an, wie viel diese Aufgabe "gemäß dem aktuellen Plan bereits bearbeitet wird".
• Wiederholen Sie dies, bis alle Worker mindestens einen Job haben und ( z & gt; ein fester Wert oder eine bestimmte Zeit ist vergangen):
  • Nimm einen der Arbeiter w mit minimalem z .
    • Setzen Sie p auf die Position des letzten Eintrags in w 's queue oder w ' s Position, wenn Warteschlange ist leer.
    • Wiederholen Sie die Aufgaben, die sich nicht in dieser Worker Queue befinden, in der Reihenfolge der Entfernung zu p
      • Berechne distance/d
      • Wenn Sie einen Mindestwert für diesen Wert finden, fügen Sie diese Aufgabe der Warteschlange des Arbeiters hinzu, fügen Sie die Entfernung zur Aufgabe + 7 zu z hinzu und fügen Sie 1/z zu d hinzu. Brechen Sie die Schleife.

Bevor Sie das ausführen, sollten Sie die Worker nach Entfernung zur nächsten Aufgabe sortieren. Ansonsten ist die erste Aufgabe eher zufällig und die erste Aufgabe ist die wichtigste.

Sie können dies jedes Mal aktualisieren, wenn ein Job oder ein Worker hinzugefügt wird. Einige der vorherigen Werte wiederverwenden (vielleicht Zwischenergebnisse speichern, wie das Hinzufügen des passenden z zu Aufgaben in der Arbeiterwarteschlange), sollte dieses Update ziemlich schnell sein.

Dies muss wahrscheinlich auch hin und wieder aktualisiert werden, da dieser Algorithmus ziemlich ungenau wird, sobald Sie weit genug in die Zukunft gehen.

Die distance/d -Formel braucht vielleicht auch etwas Feinabstimmung, aber ich denke, Tests würden hier sehr helfen.

Die Definition von "Minimum" liegt bei Ihnen. Ich würde empfehlen, ein lokales Minimum zu nehmen und vielleicht 5 weitere Aufgaben maximal zu überprüfen. Das globale Minimum zu finden, erscheint unnötig teuer.

Ich vermute, dass "Echtzeit" -Gierheit sich als schlecht herausstellt, weil die Arbeiter in wilde Jagd nach Aufgaben geraten, die bei ihrer Ankunft vollständig oder fast abgeschlossen sein werden. Also werde ich einen Planungsalgorithmus vorschlagen: eine Möglichkeit, jedem Arbeiter eine Abfolge von Aufgaben intelligent zuzuordnen, wobei die Vereinigung von Folgen eine Abdeckung ist.

Wie andere gesagt haben, ist der TSP in diese Planungsanforderung eingebettet, also ist dies ein NP Hard-Problem.

Aber es gibt einen einfachen Polynomzeit-Approximationsalgorithmus für den TSP, der einen Pfad erzeugt, der nicht länger als 2x optimal in der Länge ist. Berechnen Sie einfach einen minimalen Spannbaum mit allen Arbeitsbereichen und einem der Worker. Dann berührt der nahe liegende Pfad, der jede Kante einmal in jeder Richtung überquert, jeden Knoten.

Natürlich können Sie beim Backtracking bereits besuchte Knoten "überbuchen". Dies bedeutet, dass Sie die Task-Sequenz einfach ausgeben müssen, indem Sie das MST in der Vorbestellung durchlaufen. Aufgrund der Dreiecksungleichung ist dieser Pfad oft ein gutes Stück besser als 2x optimal. (Ich nehme an, diagonale Schritte sind hier erlaubt. Ansonsten ist das nicht wahr, aber der Algorithmus funktioniert immer noch gut.)

Also ein Ansatz für die Planung ist dies:

1. Berechnen Sie eine MST für jeden Worker und alle Arbeitsstandorte.
2. Benutze die MST, die jedem Arbeiter W zugeordnet ist, um einen Vorbestellungsweg zu berechnen: S_W, T_Wi, i = 1, 2 .... Hier ist S_W der Startort des Arbeiters W. und die T_Wi sind Aufgabenorte in die Reihenfolge W wird sie besuchen.
3. Machen Sie jetzt eine einfache ereignisgesteuerte Simulation, um einen Plan wie unten zu erstellen. (Dies ist eine "innere" Simulation innerhalb der Spielsimulation, nur um einen Plan zu erstellen.)

Im folgenden Algorithmus enthalten Ereignisse eine projizierte Uhrzeit des Auftretens und werden mit dieser Zeit als Schlüssel in die Ereigniswarteschlange gestellt.

Führen Sie nun die Zuordnungen für jeden Worker in der Reihenfolge aus, in der sie in dieser (inneren) Simulation gefunden wurden.

Die Ankunftszeiten werden anhand des vorherigen Standorts und Ziels berechnet, um eine möglichst direkte Route zu erhalten.

Dieser Algorithmus ist ziemlich gierig, aber er ist "im Voraus" gierig. Da Sie simulieren, Aufgaben im Voraus zuzuteilen, werden Sie niemals einen Arbeiter auf einer wilden Jagd zu einer Aufgabe senden, die von einem anderen Arbeiter beendet oder gut begonnen wird, bevor es ankommt.

Außerdem wird kein Arbeiter mehr als 2x eine optimale TSP-Route zurücklegen.

(Anmerkung: Nachdem ich das alles gemacht habe, merke ich, dass Sie 14 Ticks gesagt haben, weil Sie "neben" gedacht haben, während ich es als "neben" interpretiert habe ... also denken Sie daran, dass meine Berechnungen darauf basieren das, aber es sollte das Ergebnis nicht viel ändern.)

Mein erster Instinkt wäre, zuerst für jeden Arbeiter eine unabhängige Warteschlange zu erstellen, basierend auf der optimalen Zeit, vorausgesetzt, dass keine anderen Arbeiter existieren und sich später mit den Konflikten befasst (beachten Sie, dass, wenn ich mit A fertig bin, dann ist B näher als D, aber eine wichtige Sache, die wir verhindern wollen, ist 1, B zu nehmen:

Dann würde ich für jede eine Move + Work Time berechnen:

Als Referenz sind hier nur die gesamten Ticks:

Und hier ist es kumulativ:

Was passiert also, wenn Sie einfach jede Aufgabe durchlaufen, um zu sehen, wer die niedrigste Zeit hat und sie aus den Warteschlangen der anderen Arbeiter entfernen? Offensichtlich müssen die kumulativen Zeiten neu berechnet werden, sobald Sie etwas ändern (was ich gleich tun werde, ugh)

Start (wie oben):

1 hat die niedrigste A-Zeit, also 2 verliert sie, und die D-Zeit von 2 wird neu berechnet:

2 gewinnt B, also ändern sich die Zeiten von 1 für C und D:

2 gewinnt C und ändert wiederum die D-Zeit von 1:

1 gewinnt D:

Was wäre, wenn es eine andere Aufgabe E direkt über B gäbe? Es tut mir leid, dass ich keine Zeit hatte, das zu berechnen.

Ich gehe davon aus, dass das Aussehen der Arbeiter dem ähnlich sein muss, was ein Mensch tun würde (der Algorithmus muss jede Arbeit als menschliche Macht bezeichnen). Wenn der Algorithmus dies nicht tut, wird sich ein Spieler fragen, was die KI ist tun und wahrscheinlich versuchen, manuell zu routen (auch wenn es weniger optimal ist). Ich denke, jede "global optimale" Lösung würde wahrscheinlich nicht dem ähneln, was ein Mensch tun würde ...

Also würde ich argumentieren, dass Ihr (Will) anfänglicher Algorithmus vielleicht nur eine leichte Verbesserung benötigt, um zu funktionieren. Lassen Sie jeden Arbeiter zum nächstgelegenen Impfjob gehen, simulieren Sie aber, dass er dorthin geht und die Simulation stoppt, wenn der Arbeiter den Job erreicht oder ein anderer Arbeiter frei ist, der näher ist (dann wird der Arbeiter diesen Job holen). Wenn keine Jobs für Impfungen erreicht werden können, wählen Sie den nächsten belegten Job und helfen Sie dort.