Ich habe ein reales Problem, das ich darstellen und automatisieren möchte. Ich habe es vereinfacht und auf Folgendes abstrahiert:
- Es gibt n Arbeitsplätze (P1, P2, ..., Pn).
- Jeder Ort, Pn hat einen Schlüssel, Kn.
- Es gibt m Arbeiter (W1, W2, ..., Wm).
- Um bei Pn arbeiten zu können, muss ein Arbeiter Kn halten.
- Jeder Schlüssel kann entweder von einem Mitarbeiter gehalten oder an der Börse E hinterlassen werden.
Ein Mitarbeiter kann jederzeit eine Reise zur Börse unternehmen, um nicht beanspruchte Schlüssel abzuholen oder einige Schlüssel abzugeben, damit andere sie verwenden können.
Jetzt gibt es einen exogenen Arbeitsplan, der in einer strengen Reihenfolge abgeschlossen werden muss. Beispielsweise:
- 2016-04-21 W1 muss bei P6 arbeiten
- 2016-04-21 W2 muss bei P3 arbeiten
- ** Schlüsselaustausch erforderlich **
- 2016-04-22 W3 muss bei P3 arbeiten
- 2016-04-22 W2 muss bei P6 arbeiten
Eine beliebige Anzahl von Arbeitnehmern muss möglicherweise irgendwann in ihrem Zeitplan bei Pn arbeiten, allerdings nie am selben Tag
Wir wissen:
- Der Startort aller Schlüssel, entweder mit Arbeitern oder bei E.
- Die zukünftigen Arbeitsaufträge, die jeder Mitarbeiter erfüllen muss
Ich kämpfe also darum, diese ganze Situation zu modellieren. Können Sie Datenstrukturen und Algorithmen vorschlagen, die ich mir ansehen sollte, um sie in den Griff zu bekommen und die Fahrten zum Austausch für jeden Mitarbeiter zu optimieren?
Was ich minimieren möchte, ist die Gesamtzahl der Fahrten nach E. Ein sekundäres Ziel wäre es, sicherzustellen, dass kein Arbeitnehmer eine unverhältnismäßig große Anzahl von Fahrten unternimmt.
Danke im Voraus!!
quelle
Antworten:
Die Frage ist in einem wichtigen Punkt etwas mehrdeutig: Welche Elemente versuchen wir zu lösen? Möchten wir die Reihenfolge optimieren, in der Ressourcen delegiert werden? Reisen zur Börse minimieren? Arbeitsauftragsdurchsatz maximieren?
In diesem Sinne gehe ich davon aus, dass wir eine beliebige Mischung dieser Dinge tun und die Antwort auf einem ziemlich hohen Niveau halten könnten.
Das erste, was mir in den Sinn kommt, ist, dass sich die miteinander verbundenen Probleme, die damit gelöst werden sollen, hauptsächlich auf das Abhängigkeitsmanagement konzentrieren. Arbeiter, Schlüssel und Standorte können als Abhängigkeiten betrachtet werden, die aufgelöst werden müssen, um Arbeitsjobs abzuschließen.
Um dies auf die nächste Ebene zu bringen, würde ich eine Anpassung der topologischen Sortierung betrachten ( https://en.wikipedia.org/wiki/Topological_sorting ). Modellieren Sie den Problemraum als großen Graphen (moderne Graphendatenbanken könnten auch für einige dieser Analysen ein gutes Medium sein) und verwenden Sie dann verschiedene topologische Sortierungen, um verschiedene Aspekte des Problemraums zu lösen.
Auf eine leichte Tangente klingt dies nach einem wirklich lustigen Projekt. Heute beneide ich Sie, Sir.
quelle