Schichtplanung

[ConstantGardener]

@shmia

...man kann die Fitnessfunktion ja auch dahingehend gestalten, das alle den etwa gleichen "Tod" sterben (Unterschiede in der Stundenverteilung minimiert, Abweichungen von den Mitarbeiter-Präferenzen minimiert usw.)

[Sir Rufo]

Das mit der Fitnessregel ist doch relativ simpel:

Beschreiben wir diese Fitness mal als Zufriedenheit des Mitarbeiters.

Wann ist der zufrieden? Wenn er nicht zuviel arbeiten muss.
Wann wird er unzufrieden? Wenn er zuviel arbeiten muss.

Nehmen wir der Einfachkeit halber an, in jeder Schicht, die er arbeiten muss nimmt die Zufriedenheit um 8 ab.
Jede Schicht, die er nicht arbeiten muss nimmt die Zufriedenheit um 4 (die Hälfte) zu.

Für jede Schicht, die jetzt geplant werden soll kann man nun pro Mitarbeiter den Zufriedenheitsstand ermitteln.
Nach diesem Zufriedenheitsstand wird die Mitarbeiterliste sortiert und der mit der höchsten Zufriedenheit kann eingeplant werden. Hat ein MA die 2 Schichten zuvor schon gearbeitet, so wird er für diese Schichtplanung gesperrt.

Sonderfall Wochenende:

Am Wochenende gelten andere Regeln: Hat der MA am letzten WE gearbeitet, so sinkt die Zufriedenheit an diesem Wochenende rapide ab (Faktor 3=3x8=24). Musste er am vorletzten WE arbeiten, so sinkt die Zufriedenheit um den Faktor 2 (16)

Muss er an diesem Wochenende eh schon arbeiten, so sinkt seine Zufriedenheit nicht, sondern sie steigt (Faktor 4=4x8=32)

[Jumpy]

Zitat von Sir Rufo:

Wann ist der zufrieden? Wenn er nicht zuviel arbeiten muss.
Wann wird er unzufrieden? Wenn er zuviel arbeiten muss.

Und wann geht es so gerade? Wenn er wenigstens nicht mehr arbeiten muss als die anderen armen Teufel in seiner Firma.

[DanielJ]

Hallo,

ich würde nicht den Mitarbeiter sondern den Schichtplan als Individuum sehen, wer arbeitet wann ist dann teil des Genoms.

Die Fitness ist besonderst schlecht wenn die harten Regeln verlezt werden (Arbeitsrecht und externe Erfordernisse).

Bei den weichen Faktoren würde ich von vorherein eine anpassbare Gewichtung vorsehen, dann kann man später einstellen und ausprobieren was die besten Ergebnisse gibt.

Des weiteren kann man ziemlich viel mit den Mutationen und Generationen/ Anzahl Individuen spielen - ziemlich Interessant, aber keine schnelle Nummer!

LG,
Daniel

[Rülps]

Zitat von sx2008:

Zitat von Rülps:

Ich habe hier ein Verständnisproblem: Mitarbeiter zufällig auf Schichten zu verteilen ist kein Problem. Auch habe ich das mit dem Score prinzipiell verstanden. Was aber umfasst ein Mitarbeiter-Objekt und die Listen. Worüber führe ich eine Schleife aus? Das habe ich nicht so ganz verstanden. Hier habe ich noch einen Knoten im Hirn...

Man kann den Algorithmus rein prozedural, also mit Standard-Pascal, oder objekt-orientiert programmieren.
Falls man sich für objekt-orientiert entscheidet, würde man eine Klasse TMitarbeiter erstellen und daraus pro Mitarbeiter ein Objekt erzeugen.
Um die 11 Mitarbeiter-Objekte zu verwalten könnte man diese in einer TObjectList halten. (das war die angesprochene "Liste")
Beim Erzeugen der Mitarbeiter-Objekte könnte man bestimmte Eigenschaften wie z.B. das Alter oder Anzahl der Kinder setzen.
Vielleicht soll auf ältere Mitarbeiter oder Mitarbeiter mit Kindern im Schichtplan besondere Rücksicht genommen werden.
Wie gesagt, man kann das so machen, muss aber nicht.

Mit der Schleife ist gemeint, dass die Schritte des Algorithmus öfters wiederholt werden müssen.
So sieht der 1. Abschnitt des Algorithmus aus, bei dem versucht wird durch blindes Ausprobieren zufälliger Schichtpläne einen möglicht guten Startpunkt zu finden:

Delphi-Quellcode:

ErzeugeZufaelligenSchichtplan(oldplan);
oldscore := BerechneUngleichheitScore(oldplan);
for i := 1 to 1000 do
begin
  ErzeugeZufaelligenSchichtplan(aktplan);
  aktscore := BerechneUngleichheitScore(aktplan);
  if aktscore < oldscore then
  begin
    // besseren Plan gefunden
    CopyPlan(aktplan, oldplan);
    oldscore := aktscore;
  end;
end;

Ich hab's jetzt verstanden. Genial einfach! Vielen Dank! Ich gedenke das so umzusetzen: Für die Mitarbeiter nehme ich Records, da ich im Moment zumindest den Vorteil gegenüber Objekten nicht sehe. Wie ich den Schichtplan definiere weiß ich noch nicht so genau, aber ich denke, dass ich hier auch einen Record verwenden werde. Ich werde probehalber mal einen Monat programmieren. Das könnte dann in etwa so aussehen:

Delphi-Quellcode:

type
  TSchichtplan = record
    Monat: array [0..30] of integer; // hat ein Monat weniger Tage fülle ich den Rest mit -1 auf
    BesondereTage: array [0..30] of integer; // Wochentage: 0, Samstage: 1, Sonn- & Feiertage: 2
    // 2 Mitarbeiter pro Schicht werden für jeden Tag in die folgenden Arrays geschrieben
    Früh1: array [0..30] of string;
    Früh2: array [0..30] of string;
    Spät1: array [0..30] of string;
    Spät2: array [0..30] of string;
    Nacht1: array [0..30] of string;
    Nacht2: array [0..30] of string;
  end;

In ErzeugeZufaelligenSchichtplan fülle ich diesen Record dann zufällig - natürlich immer noch mit etwas Logik - auf. Hier habe ich auch eine Frage: Was sind die Übergabeparameter oldplan und aktplan?
Für jede Regel will ich dann eine function schreiben, die innerhalb BerechneUngleichheitScore aufgerufen werden und als Rückgabewert den Score hat.

Ich werde dies im Laufe der nächsten 1 - 2 Wochen mal sehr (!) quick & dirty programmieren und es dann hier veröffentlichen, so dass wir dann gemeinsam - wenn ihr nix dagegenhabt - die Programmarchitektur verbessern.

Ich bin sehr auf die Ergebnisse gespannt und bedanke mich nochmal für die Hilfe!

[Sir Rufo]

Mit dem Ansatz wirst du dir aber entweder die Ohren brechen oder das Handtuch hinwerfen.

Für eine Schichtplanung die u.a. berücksichtigen soll, dass die MA so oft wie möglich am WE frei haben sollen, ist es unerlässlich auch die Daten vor dem Planungszeitraum zu kennen. Abgesehen davon soll ja auch die Arbeit möglichst gleich verteilt werden, auch da helfen die bisherigen Daten ungemein.

Insgesamt würde ich auch zu einem OOP-Ansatz raten (Beispiel Daten-Model)

Delphi-Quellcode:

type
  TMitarbeiter = class

  end;

  TAbwesenheit = class
    FDatum : TDate;
    FMitarbeiter : TMitarbeiter;
    FGrund : string;
  end;

  TSchichtTyp = ( stFrüh, stSpät, stNacht );

  TSchicht = class
  private
    FDatum : TDate;
    FSchichtTyp : TSchichtTyp;
    FMitarbeiter : TList<TMitarbeiter>; // Mitarbeiter in dieser Schicht
    FMAMin : Integer; // Minimum an Mitarbeitern
    FMAMax : Integer; // Maximum an Mitarbeitern
  public
    function Wochenende : Boolean; // True, wenn es sich um ein Wochenende handelt
  end;  

  TSchichtplan = class
  private
    FMitarbeiter : TList<TMitarbeiter>; // Alle Mitarbeiter
    FAbwesenheiten : TList<TAbwesenheit>; // Abwesenheit-Kalendar der Mitarbeiter
    FSchichten : TList<TSchicht>; // Alle Schichten sortiert nach Datum, SchichtTyp
  end;

Für die Berechnung der Daten entwirft man sich ein weiteres Model

Delphi-Quellcode:

type
  TSchichtPlanung = class
  private
    FSchichtplan : TSchichtplan;
    ...
  public
    constructor Create( ASchichtplan : TSchichtplan; APlanDatumAb : TDate; APlanTage : Integer );
  end;

Ich habe bewusst einige Sachen herausgelassen (z.B. Name des Mitarbeiters), die für die Planung völlig überflüssig sind.
Komplett ist es aber auch nicht

Das kann man jetzt und vor allem später immer wieder erweitern.

Eine Record-basierte Lösung mit einzelnen Arrays pro Schicht/Mitarbeiter und die Referenz auf den Mitarbeiter als string - ich würde mir das nicht antun

[Rülps]

Zitat von Sir Rufo:

Mit dem Ansatz wirst du dir aber entweder die Ohren brechen oder das Handtuch hinwerfen.

Ehrlich gesagt bin ich auch sehr gespannt, ob die Methode "Wenn eine Millionen Affen, eine Millionen Jahre lang auf einer Millionen Schreibmaschinen eintippen, irgendwann mal Shakespeares Hamlet rauskommt" funktioniert. Einen Versuch ist's wert.

Zitat von Sir Rufo:

Für eine Schichtplanung die u.a. berücksichtigen soll, dass die MA so oft wie möglich am WE frei haben sollen, ist es unerlässlich auch die Daten vor dem Planungszeitraum zu kennen. Abgesehen davon soll ja auch die Arbeit möglichst gleich verteilt werden, auch da helfen die bisherigen Daten ungemein.

Ich plane schon beim zufälligen erstellen des Schichtplans einige Regeln zu beachten wie beispielsweise, dass pro Schicht genau zwei Leute gleichzeitig eingetragen werden und diverse weitere Regeln.

Danach wird das ganze evaluiert über die Ungleichheit des Scores. Ob und wie das hinhaut weiß ich nicht, aber da es relativ leicht umzusetzen ist, kann man es mal ausprobieren. Auch das mit den Wochenenden sollte nach meinem Verständnis eigentlich zufällig erreicht und evaluiert werden können, aber du hast schon recht: It's a long shot

Ich muss aber dazu erwähnen, dass ich ein Hobbyprogrammierer bin und ich habe auch nicht die Aufgabe die Schichtplanung zu übernehmen. Das macht weiterhin meine Chefin. Sie versucht schon seit einiger Zeit eine gewisse Systematik in die Planung zu bekommen. Das klappt leider nicht. Da dacht' ich mir: Ich kann mich ja mal dran versuchen.

Zitat von Sir Rufo:

Eine Record-basierte Lösung mit einzelnen Arrays pro Schicht/Mitarbeiter und die Referenz auf den Mitarbeiter als string - ich würde mir das nicht antun

Ja, da hast du 100% Recht. Das meinte ich mit:

Zitat von Rülps:

Ich werde dies im Laufe der nächsten 1 - 2 Wochen mal sehr (!) quick & dirty programmieren

Ich kann's auch besser, aber nicht schneller als so und warum einen Megaaufwand betreiben, wenn's am Ende dann doch nicht klappt?

[Sir Rufo]

Zitat von Rülps:

Ich kann's auch besser, aber nicht schneller als so und warum einen Megaaufwand betreiben, wenn's am Ende dann doch nicht klappt?

Weil es sonst tatsächlich ein Megaaufwand wird

[haentschman]

Moin...

ich habe jetzt nicht jeden Satz gelesen. Kommt in den Modellen auch folgende Konstellation vor bzw. ist berücksichtigt ?

Ein Mitarbeiter ist zwar in deinem Krankenhaus aber 3 Etagen höher mit einem kaputten Bein. Was ist mit sponanen Ausfällen ? (Scheidung etc.)

[Rülps]

Ja, das wird alles berücksichtigt, sogar ein Ausfall des Betriebs wegen Invasion durch Außerirdische und/oder auch afrikanischen Killerbienen