Methoden für die Terminplanung

Question

Ich arbeite an einer PHP-Anwendung für ein Unternehmen für häusliche Pflege. Das Unternehmen hat x Pflegekräfte, die jede Woche die Häuser von x Dienstleistungsnutzern (Kunden) besuchen sollen. Jeder Dienstleistungsnutzer hat einen festen "Zeitplan", wann er besucht werden soll, der Zeiten und die Besuchsdauer in Minuten enthält.

So könnte ein Dienstleistungsnutzer zum Beispiel folgenden Zeitplan haben.

      AM   Lunch   Tea   Late   Night   Respite
Mon   30m  -       30m   60m    -       -
Tue   30m  -       -     60m    -       -
Wed   20m  25m     30m   60m    120m    -
Thu   -    -       30m   -      -       -
Fri   30m  25m     -     -      -       -
Sat   -    -       -     -      -       -
Sun   20m  25m     -     -      -       -

Diese Zeiträume werden derzeit in einer Datenbank in folgendem Format gespeichert:

Table: Service_user_schedules
id   service_user_id   day   period   duration

Jede Woche füllen die Betreuerinnen und Betreuer eine Tabelle mit den Zeiten aus, in denen sie arbeiten können. Diese Daten werden dann in das System eingegeben und in der Datenbank in folgendem Format gespeichert:

Table: Carer_available_shifts
id   carer_id   day   period

Das Problem ist nun, dass ich einen Controller erstellen muss, der diese Daten aufnimmt und den Dienstnutzern auf der Grundlage der von ihnen angegebenen Verfügbarkeit automatisch Betreuer zuweist. Dies muss bearbeitbar sein, so dass der Benutzer für den Fall, dass niemand für einen bestimmten Betreuer verfügbar ist, einen auswählen kann, der nicht verfügbar ist, und er wird trotzdem zur Datenbank hinzugefügt.

Im Moment habe ich ein Durcheinander von Schleifen, Funktionen und Echos, um zu prüfen, ob Betreuer für einen bestimmten Dienstleistungsnutzer verfügbar sind, und um es editierbar zu machen.

Hat jemand diese Aufgabe schon einmal durchgeführt und wenn ja, haben Sie eine einfache Lösung gefunden? Ich würde es vorziehen, es objektorientiert zu machen, damit ich die gleiche generische Klasse wiederverwenden kann, aber im Moment bin ich völlig ratlos!

EDIT: Ich habe jetzt ein Kopfgeld auf diese Frage ausgesetzt. Ich recherchiere derzeit genetische Algorithmen (etwas, von dem ich noch nie gehört, geschweige denn verwendet habe!) als Lösung für dieses Problem auf der Grundlage einiger der Antworten. Ich würde gerne wissen, ob jemand von Ihnen andere Methoden zur Lösung dieser Art von Problem verwendet hat, oder wenn Sie genetische Algorithmen verwendet haben, könnten Sie eine weniger allgemeine Erklärung geben, wie Sie sie auf dieses spezielle Problem angewendet haben.

Ich gehe davon aus, dass diese Hürde bei vielen Bewerbungen im Bereich "Personalwesen" recht häufig vorkommt, und bin überrascht, wie wenig darüber im Internet diskutiert wird!

UPDATE

Für dieses spezielle Projekt werde ich wohl die von Tak beschriebene Datenbankmethode verwenden, aber möglicherweise in Zukunft auf die Verwendung von GAs umsteigen, wenn ich mehr Entwicklungszeit zur Verfügung habe.

Ich bin jetzt etwas ratlos, wem ich das Kopfgeld zukommen lassen soll. duedl0r hat sich mit seiner (oder ihrer) Antwort viel Mühe gegeben. Sie hat mir einen großartigen Einblick in die Welt der genetischen Algorithmen gegeben - eine Problemlösungsmethode, mit der ich zuvor noch nie in Berührung gekommen war. Die Antwort von Tak liefert jedoch die Lösung, die ich für dieses Projekt verwenden werde. Daher habe ich die Prämie an Tak vergeben.

Answer 1

Klingt wie das Problem des Dienstplans für die Mitarbeiter was NP-komplett ist.

Wenn Sie denken, dass Metaheuristiken (wie genetische Algorithmen, Tabu-Suche, simuliertes Annealing, ...) zu viel des Guten sind, dann entscheiden Sie sich einfach für eine einfach Erste Anpassung Abnehmend Algorithmus .

Answer 2

Vielleicht können Sie einen genetischen Algorithmus verwenden. Das hat den Vorteil, dass man wirklich verrückte Sachen machen kann (wenn man die Grundlagen geschaffen hat), z. B. könnte man auch sagen, dass ein Betreuer einen Dienstleistungsnutzer, den er vorher besucht hat, optimal besuchen sollte, oder die Entfernung zwischen den Besuchen minimieren :)

Auf diese Weise bekommt jeder Dienstleistungsnutzer einen Betreuer, auch wenn kein Zeitplan vorhanden ist. Der Algorithmus versucht einfach, eine optimale Lösung zu finden

Wahrscheinlich ist es ein bisschen übertrieben, aber es ist ein interessantes Thema :) Ich wollte es erwähnen, weil es vielleicht ein neuer Weg ist, Ihr Problem zu lösen. Zumindest einen Gedanken wert ;)

Einige Links: Genetischer Algorithmus Ressource , Genetischer Algorithmus Tutorial , Wikipedia

---

bearbeiten : Konkretere Erläuterung genetischer Algorithmen.

Ein genetischer Algorithmus ist eine Modellierung der Theorie der evolutionären Entwicklung. Für die evolutionäre Entwicklung braucht man eine Population von bestimmten Lebewesen. Dann simuliert man die Entwicklung der Population unter Verwendung bestimmter biologischer Effekte wie Mutation, Selektion, Kreuzung usw.. Wie Darwin vor ein paar Jahren herausfand :)

Nun müssen Sie Ihr Problem einem solchen Wesen (oder einer DNA) zuordnen. Das bedeutet, dass jedes Lebewesen eine Lösung in Ihrem Problemraum darstellt (jede DNA ist eine Lösung für Ihr Problem).

Die Redewendung "survival of the fittest" bedeutet also lediglich, dass ich eine Lösung für mein Problem erhalte, die optimal sein könnte (allerdings nicht garantiert).

Ein Mapping von Ihrem Problem auf eine solche DNA kann sehr unterschiedlich erfolgen. Zunächst brauchen Sie ein Array, das Ihre DNA repräsentiert. Sie können zum Beispiel dies angeben:

Sie erstellen für jeden Dienstleistungsnutzer Pakete mit 42 Elementen (6 Slots pro Tag, 7 Tage pro Woche). Der erste Eintrag im Array ist dann der "AM"/Mon-Slot für Service-Nutzer 1. Ihr zweiter Eintrag ist der "Lunch"/Mon-Slot für Service-Nutzer 1. Ihr 43. Eintrag ist der "AM"/Mon-Slot für Dienstnutzer 2. Damit ist die DNA Ihrer Kreatur definiert. Dann lassen Sie sie sich gegenseitig bumsen, damit sie sich entwickeln können :)

Um herauszufinden, welches Lebewesen gut passt, braucht man auch eine Formel, die die Passgenauigkeit berechnet. Du erstellst eine Formel, die eine DNA als Eingabe und eine Zahl als Ausgabe hat. Dies ist abhängig von deinen Regeln. Du kannst zum Beispiel Plus- oder Minuspunkte vergeben, wenn bestimmte Regeln gelten oder nicht. Wenn eine Pflegekraft für zwei verschiedene Dienstleistungsnutzer zur gleichen Zeit eingesetzt wird, gibt es Minuspunkte, wenn eine Pflegekraft tatsächlich Zeit für einen Slot hat und für einen Dienstleistungsnutzer eingeplant ist, kann es Pluspunkte geben.

Sie können auch sagen: Ein genetischer Algorithmus versucht herauszufinden, wie man diese Formel mit Hilfe eines genetischen Ansatzes maximieren kann.

Sehr kurze Einführung in genetische Algorithmen wenn man genug Zeit hat und sich auch für das Thema interessiert, lohnt es sich wirklich, sich damit zu beschäftigen man kann einige wirklich coole Sachen damit machen. Aber bedenke, es kann auch chaotisch und kompliziert werden :)

Answer 3

Ich würde es so angehen. Erstens eine Datenbanktabelle, die Zeitfenster mit verfügbaren Betreuern verknüpft...

Table schedules_shifts
id   service_user_schedules_id   carer_available_shifts_id

Jetzt gibt es eine Funktion, die verfügbare Betreuer mit den gewünschten Terminen abgleicht und die Tabelle auffüllt...

* Fetch service_user_schedules for the next week
* For each service_user_schedules row
 * Fetch carer_available_shifts that match the schedule slot
 * For each carer_available_shift row
  * If results
   * Fetch schedules_shifts rows where carer_available_shifts_id is already used
   * If no results
    * Insert a row in the schedules_shifts table for each carer
   * Otherwise carer is busy, do nothing and continue
  * If no results, flag for review or trigger e-mail to manager, or other action
* Trigger e-mail or save log of completion for peace of mind

Die neue Tabelle enthält nun mögliche Übereinstimmungen zwischen Betreuern und Zeitplänen, ohne dass die Zeit eines Betreuers doppelt zugewiesen wird. Es werden jedoch mehrere Betreuerschichten mit einem Zeitplanplatz abgeglichen. Dies könnte eine Funktion sein! Lassen Sie sie so wie sie sind und fügen Sie ein confirmed Spalte zu schedules_shifts so dass ein Vorgesetzter die Arbeit manuell zuweisen kann, oder die Betreuer können sich freiwillig melden, oder die erste Übereinstimmung wird automatisch als confirmed und behalten Sie die anderen Reihen als Alternative für den Fall, dass der erste Betreuer nicht kommen kann.

Dies alles kann jede Woche durch einen Cron ausgelöst werden oder wenn die letzte Karriere ihren Wochenplan aktualisiert. Wahrscheinlich ersteres, weil die Benutzer oft unberechenbar sind.

Jetzt befinden sich die automatisierten Daten in einer Tabelle, die Sie zur Bearbeitung öffnen können. Erstellen Sie eine normale Verwaltungskonsole, wie Sie sie zum Ändern der Zeilen in schedules_shifts oder kennzeichnen Sie verschiedene Zeilen als "bestätigt".

Die Übersetzung in eine generische Klasse sollte nicht allzu schwierig sein - es geht nur darum, eine generische Terminologie zu verwenden. Es ist schon spät und mir fällt keine mehr ein :)

Es ist möglich, die gesamte Datensichtung in PHP-Arrays statt in der von mir oben erstellten Datenbank durchzuführen, aber ich denke, dass SQL besser geeignet ist, um die Daten zu sortieren und Änderungen vorzunehmen.

Genetische Algorithmen klingen allerdings interessant, und wenn du die Zeit hast, solltest du sie untersuchen ^_^

Hoffentlich hilft das?