Job-Scheduling-Problem

Meine Lösung: Sie benötigen eine PriorityQueue (die in PHP unter SplPriorityQueue verfügbar ist). Die PriorityQueue gibt Ihnen Elemente mit absteigender Priorität (sortiert nach Werten, die kleinste Wert hat die höchste Priorität).

Jedes Mitglied erhält einen zugewiesenen Wert. Dieser Wert ist eine ASCII-Nummer mit n Ziffern (Sie können aus praktischen Gründen 8 Ziffern verwenden), aufgefüllt mit Nullen in n Positionen. Danach hängen Sie an der Name. Sie fügen jedem Mitglied auch die verfügbaren Positionen hinzu

So (n = 5):

• M1-Wert: 99999Albert P1, P2, P3
• M2-Wert: 99999Susi P1, P2
• M3-Wert: 99999Bob P1, P3

Dies erleichtert das Sortieren von Mitgliedern nach Priorität und Namen.

Vorbereitung:

Ein sonniger Tag. Sie rufen die zugewiesenen Positionen und eine Kategorie für einen bestimmten Tag ab. Jedes Mitglied wird in eine lange Liste geladen. Jedes Mitglied, das nicht auf der Arbeit erscheint, wird nicht geladen, aber sein Wert wird um minus zwei verringert. Bob ist nicht hier, also bekommt der neue Wert 99997Bob. Dies bedeutet, dass Bob beim nächsten Mal automatisch ausgewählt wird. Alle anderen Mitglieder erhalten ihren Wert um minus eins verringert.

Die für einen bestimmten Tag zugewiesenen Positionen werden zugeordnet (verwenden Sie SplObjectStorage):

P1- & gt; M1, M2, M3, M4 usw. P2- & gt; usw.

Die Karte enthält nur die Positionen, die an diesem Tag zugewiesen werden müssen. Nach dem

Filter: Sie müssen die Gruppen nachschlagen und alle Positionen auf der Karte löschen, die an diesem Tag nicht zugewiesen werden können. Ihre Gruppenbeschreibung ist etwas unklar.

Zuweisen:

• Sie wählen die zuzuweisende Position
• Liste der Mitglieder abrufen, die die Position füllen können
• Entfernen Sie verfügbare Mitglieder aus der Liste und fügen Sie sie in die PriorityQueue
ein
• Ordnen Sie die Position per extract () von PriorityQueue zu (die korrekte Zuweisung ist abgeschlossen) automatisch). Jedes zugewiesene Mitglied bekommt seinen Wert um erhöht eine (also die Abnahme und Erhöhung Ebenen, wenn Sie hier sind und arbeiten). Wenn Sie hier sind und aus irgendeinem Grund keine Position zugewiesen bekommen, erhalten Sie eine kleine Strafe von einem. Wenn Sie nicht hier sind, erhalten Sie eine Strafe von zwei.
• Nach der Beendigung, setzen Sie die verbleibenden Mitglieder wieder auf die Liste, löschen Sie die PQueue und fahre mit der nächsten Aufgabe fort.

Vorbehalte:

• Sie müssen darauf achten, dass immer genügend Leute für eine Position zur Verfügung stehen.

uff. Ich folge nicht Ihrer Beschreibung, aber in ähnlichen Situationen habe ich SQL verwendet, um diese Art von Problem zu lösen. Wenn Sie PHP verwenden, denke ich, Sie haben SQL verfügbar.

Was ich vorschlagen würde ist, eine Möglichkeit zu finden, diese Informationen in einer Reihe von Tabellen zu speichern und dann herauszufinden, welche SQL-Abfrage Ihnen die gewünschte Antwort gibt. oft ist es in sql viel einfacher als in einer prozeduralen Sprache.

Für den übersprungenen Teil können Sie beispielsweise eine Spalte haben, die aufzeichnet, wenn jemand zuletzt zugewiesen wurde, und dann nach dieser sortieren (so dass Sie die Person auswählen, die lange Zeit nicht zugewiesen wurde). alternativ könntest du die Anzahl der Male als Spalte überspringen lassen und damit ordern.

Was ich verstehe, ist, dass es 'm' Mitglieder und 'n' Positionen gibt.

Kategorie: eine Gruppe von Positionen - ein Mitglied, dem eine Position in der Kategorie zugewiesen wurde, kann keine andere haben?

Gruppe: Eine Gruppe von Positionen - Positionen in derselben Gruppe müssen an verschiedenen Tagen zugewiesen werden.

Letztendlich hat eine Position eine Liste von Mitgliedern, die sie füllen können.

Wenn Sie dies aus der Sicht der Datenstruktur betrachten, fügen Sie die Mitglieder in eine verknüpfte Liste ein - jedes Mitglied muss eine zusätzliche Liste von [Position, Tag] haben, der schließlich zugewiesen wird. Dann haben Sie für jede Position eine Liste von Referenzen auf die Mitglieder, die diese Position füllen können. Implementieren Sie Kategorien als eine andere Liste von Referenzen für eine Position, in der sie sich befindet.

Die tatsächliche Zuweisung: Haben Sie einen Tageszähler = 0, und durchlaufen Sie die Positionen. Durchsuchen Sie für jede Position P die Elemente, die sie füllen können. Ein Mitglied M kann die Position füllen, wenn:

• Jede Position, die er besetzt hat P2 teilt keine Kategorie mit P.
• Jede Position, die er P2 mit Tag = Tageszähler gefüllt hat, teilt keine Gruppe mit P.

Wenn er die Position füllen kann, wird das [position, day] -Paar zum Mitglied hinzugefügt, und der Knoten des Mitglieds wird zum ENDE der Liste verschoben (aus diesem Grund sind Verweise notwendig - alle Verweise sind noch gültig obwohl der Knoten verschoben wurde). Dies stellt sicher, dass die "übersprungenen" Mitglieder die höchste Priorität erhalten und dass die Mitglieder, die nicht erreicht wurden, die nächst höhere Priorität erhielten.

Sobald eine Position gefüllt ist, gehen Sie zur nächsten Position. Wenn die Position eine Gruppe mit einer bereits zugewiesenen Position teilt, überspringen Sie sie, indem Sie alle Positionen durchlaufen, bis Sie am Tag 1 so viele Positionen wie möglich zuweisen können. Erhöhen Sie dann den Tageszähler und wiederholen Sie den Vorgang für Tag 2. Dies sollte Ihnen helfen eine maximale Zuweisung (nicht sicher über Maximum) für alle Jobs.

Tipp: Wenn Sie ein Mitglied an das Ende der Mitgliederliste verschieben, müssen Sie einen Verweis auf das Ende behalten, damit Sie die Liste nicht durchlaufen müssen. Für die nächste Position müssen Sie ohnehin von vorne beginnen, also gibt es keine Punkt durch die ganze Sache gehen.