Schichtplanung

[Rülps]

Hallo zusammen,

ich bin gerade an einem Punkt, wo ich an meine "Sich-einen-Algorithmus-ausdenken"-Grenze gestoßen bin. Ich arbeite seit einem Jahr in einem Krankenhaus, in dem 365 Tage im Jahr 24 Stunden am Tag 2 Service-Engineers anwesend sein müssen. Die Schichtplanung ist eine Katastrophe und meine Chefin ist auch am verzweifeln hier eine Systematik hineinzubekommen.

Vorneweg, ich habe bereits einige Schichtplanungs-Demoversionen getestet. Diese sind für unsere Planung aber nicht geeigent. Naja, zumindest die, die ich ausprobiert habe. Das Problem ist, dass diese schon ein Schichtmodell voraussetzen, um eine automatische Genrierung durchführen zu können. Mir geht es aber darum ein "optimiertes" Schichtmodell zu berechnen.

Die Aufgabe ist 11 Mitarbeiter so zu verplanen, dass für alle drei Schichten (Früh 6:00-14:00, Spät 14:00-22:00, Nacht 22:00-6:00) immer zwei Mitarbeiter vorhanden sind. Die Wochenarbeitstunden dürfen maximal 50 Stunden betragen, wobei hier natürlich ein Ausgleich geschaffen werden muss, d.h. wenn in einer Woche 50 Stunden gearbeitet wurde, in einer anderen dafür nur 30 gearbeitet werden muss. Ein weiteres Optimierungskriterium ist, dass jeder Mitarbeiter soviele Wochenenden wie möglich frei hat. Es gibt noch mehrere "Regeln", die in einen solchen Algorithmus einfließen müssten, wie z.B. die Einhaltung der Ruhepausen, d.h. von einer Spätschicht direkt auf eine Frühschicht wechseln geht nicht, weil dazwischen nur 8 Stunden liegen, aber im Moment geht es mir noch um die Herangehensweise.

Wie geht man dabei vor? Rekursion? Neuronale Netze :shock: Wie gesagt, ich habe momentan noch nicht mal einen Ansatz und bin für jede Idee offen.

[BUG]

Prinzipiell würde ich in Richtung Graphentheorie gucken. Scheduling ist da auf jeden Fall ein Thema. Ich würde da an ein Färbungs-Problem denken. Allerdings fällt mir ad-hoc nichts ein, was genau passen würde (Ich bin leider auch kein Experte).

Als ersten Ansatz würde ich die Zeitslots als Knoten modellieren und alle Slots die nicht vom gleichen Mitarbeiter ausgefüllt werden können mit einer Kante verbinden. Dann suchst du eine 11-Färbung des Graphen, so dass alle Farben ungefähr gleich oft vorkommen (insbesondere an den Wochenenden).

Achtung: Färbungsprobleme sind im allgemeinen nicht ganz einfach. Da könntest dir da durchaus ein NP-schweres Problem angelacht haben.

[Robotiker]

Von der Größenordnung her, nur 11 Mitarbeiter, ist das Problem noch in einem Bereich, wo ein Constraint-Solver das hinkriegen müsste.

Für Delphi kenne ich keinen, aber das .net Framework hat einen, also würde Prism gehen.

http://msdn.microsoft.com/en-us/devlabs/hh145003.aspx

[sx2008]

Du könntest eine Monte-Carlo Methode einsetzen.
Jeder Mitarbeiter wird als Objekt modelliert und besitzt einen "Score".
Je höher der Score, umso ungünstiger sind die Arbeitszeiten für den Mitarbeiter.
Bei einer Verletzung einer harten Regel (z.B. >50Std/Woche) ist der Score besonders hoch.

Die Mitarbeiter-Objekte befinden sich in einer Liste und werden auf "Ungleichheit" geprüft.
Dazu wird zuerst der Durchschnitts-Score über alle Mitarbeiter berechnet.
Die Abweichung wird für jeden Mitarbeiter so berechnet: (Score-Durchschnitt)^2
Die Summe dieses Quadrate ist die "Ungleichheit".

Zu Beginn des Algorithmus werden die Arbeitszeiten rein zufällig verteilt.
Dabei ergeben sich natürlich Ungerechtigkeiten und Regelverletzungen.
Es wird die Ungleichheit berechnet.
Führt man dies in einer Schleife aus, dann merkt man sich immer nur den Schichtplan mit der niedrigsten Ungleichheit sowie den Wert der Ungleichheit.

Nach ungefähr 1000 Durchläufen hat man schon einen recht guten Schichtplan.
Dann macht man weiter, aber diesmal werden nur Arbeitszeiten 2er zufälliger Mitarbeiter getauscht und geschaut ob dieser Schichtplan weniger ungleich als der Vorgänger ist.
Falls ja, wird der weniger ungleiche Schichtplan zum aktuellen Kandidaten.

Der Algorithmus bricht ab, falls die Ungleichheit eine untere Schranke erreicht oder vom Benutzer beendet wird.

Dieses Verfahren liefert nicht zwingend den allerbesten Schichtplan aber man ist doch sehr nah an der besten Lösung.
Der Schichtplan wird gerechter sein als wenn er vom Chef vorgegeben würde oder ausgelost wäre.

Der Algorithmus funktioniert auch bei sehr komplexen Regeln wenn andere Algorithmen wegen hohen Anzahl an Schritten längst aufgeben müssen.

[Bummi]

Shima ist mir zuvor gekommen, ich hatte einen ähnlichen Ansatz erwogen.

Die Mitarbeiter können Präferenzen hinterlegen die mit einem Faktor belegt werden:
durchgebende Schichten
Präferenz pro Wochentag
Präferenz für die 3 Schichten
etc.

Die Tabelle
Datum,Schicht,Ma > 1.1.2012,1,11
Datum,Schicht,Ma > 1.1.2012,2,10
Datum,Schicht,Ma > 1.1.2012,3,1
Datum,Schicht,Ma > 2.1.2012,1,11
....
wird vorbelegt mich Wünschen der Mitarbeiter
Danach wird die Tabelle interativ durchgegangen und für jeden Mitarbeiter jedes mal eine Gewichtung berechnet aus Präferenzen unter Berücksichtigung von Tag/Schicht/Schicht Vortag<>durchgehende Schichten/Wochenstunden/2-Wochenstunden(<=80)/Monatsstunden/Urlaub etc.

Der Mitarbeiter mit der höchsten Präferenz wird zugeteilt, nächster Satz gleiches Spiel.

Das Problem wird sein die Gewichtungen sinnvoll zu verrechnen.

[Rülps]

Vielen Dank für die guten Tipps :thumb: Ich muss mich noch mehr damit beschäftigen, um detaillierter nachfragen zu können, aber generell gefällt mir der Monte-Carlo-Ansatz sehr gut.

Zitat:

Zitat von sx2008 (Beitrag 1188711)

Die Mitarbeiter-Objekte befinden sich in einer Liste und werden auf "Ungleichheit" geprüft. Dazu wird zuerst der Durchschnitts-Score über alle Mitarbeiter berechnet. Die Abweichung wird für jeden Mitarbeiter so berechnet: (Score-Durchschnitt)^2 Die Summe dieses Quadrate ist die "Ungleichheit".

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...

[sx2008]

Zitat:

Zitat von Rülps (Beitrag 1188807)

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;

[DanielJ]

Hallo,

wir haben gute Erfahrungen bei der Schichtplanung mit Evolutionären Algorithmen
bei ´nem 150 MA-Callcenter gemacht.

In Anbetracht der Geringen Anzahl an Teilnehmern könnte ich mir vorstellen das auch eine deterministische Lösung im Bereich des Möglichen liegt - so ein Planung kann ja auch über nacht laufen.

LG,
Daniel

[ConstantGardener]

@DanielJ

...jupp in diese Richtung (Genetische Algorithmen) würde ich auch gehen. Das Problem dabei ist halt die Fitnessfunktion und die Gewichte der einzelnen Regeln.

Aber stimmt schon: bei 11 Mitarbeitern vielleicht etwas Overkill.

[shmia]

Zitat:

Zitat von ConstantGardener (Beitrag 1188904)

...jupp in diese Richtung (Genetische Algorithmen) würde ich auch gehen. Das Problem dabei ist halt die Fitnessfunktion ...

Wobei man aufpassen muss was optimiert wird.
Sonst gibt es am Ende nur noch einen einzigen Mitarbeiter, der jeden Tag frei hat.
(alle anderen sind den genetischen Tod gestorben) :-D

[ConstantGardener]

@shmia

...man kann die Fitnessfunktion ja auch dahingehend gestalten, das alle den etwa gleichen ":angel:Tod:twisted:" sterben 8-)(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:

Zitat von Sir Rufo (Beitrag 1188967)

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. :-D

[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:

Zitat von sx2008 (Beitrag 1188842)

Zitat:

Zitat von Rülps (Beitrag 1188807)

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:

Zitat von Sir Rufo (Beitrag 1189124)

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:

Zitat von Sir Rufo (Beitrag 1189124)

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:

Zitat von Sir Rufo (Beitrag 1189124)

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:

Zitat von Rülps (Beitrag 1189111)

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:

Zitat von Rülps (Beitrag 1189151)

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... 8-)

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. :lol: 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 ;-)

[haentschman]

...dann ist es ja gut 8-)

[DanielJ]

Zitat:

Zitat von haentschman (Beitrag 1189172)

Was ist mit sponanen Ausfällen ?

Das Wörtchen spontan sagt es ja schon:
spontan <> planbar

Da kann mann dann nur mit den neuen Fakten einen neuen Plan machen, oder mal in die Runde Fragen: "Wer tauscht mit XY seine Schicht?"
Das zweite funktioniert häufig ziemlich gut!

Die "tatsächlich gearbeitet" Historie sollte dann natürlich in zukünftigen Planungen automatisch berücksichtigt werden.

Der interessante Aspekt ist aber: Jedem Mitarbeiter sollte eine Liste nicht planbarer Zeiten angehängt werden!

[Rülps]

Zitat:

Zitat von DanielJ (Beitrag 1189198)

Zitat:

Zitat von haentschman (Beitrag 1189172)

Was ist mit sponanen Ausfällen ?

Das Wörtchen spontan sagt es ja schon:
spontan <> planbar

Da kann mann dann nur mit den neuen Fakten einen neuen Plan machen, oder mal in die Runde Fragen: "Wer tauscht mit XY seine Schicht?"
Das zweite funktioniert häufig ziemlich gut!

Genau so sieht's aus. Wenn es für einen Monat gut funktionieren sollte, so wird es auf ein Quartal erweitert. So weit gehen unsere aktuellen Schichtpläne auch. Alle drei Monate wird dann neu durchgewürfelt. Man kann natürlich nachträglich noch manuell tauschen.

Zitat:

Zitat von DanielJ (Beitrag 1189198)

Der interessante Aspekt ist aber: Jedem Mitarbeiter sollte eine Liste nicht planbarer Zeiten angehängt werden!

Das ist dann der zweite Schritt.

[Furtbichler]

Ich habe soetwas vor Jahren einfach durch Brute Force erledigt (Es ist ein 0/1-Knapsack Problem). Die Schichtpläne an sich zu erstellen ist dann kein Problem (bzw. den ersten).

An die Optimierung habe ich damals nicht gedacht, denn ich war Froh, überhaupt einen Schichtplan erstellen zu können.

Die Optimierung ("Verändere irgend etwas am Schichtplan und wenn der neue besser ist, hurra!") kann ja beliebig lange laufen und jederzeit abgebrochen werden und für einen Laien wie mich auf jeden Fall umsetzbar und eine gute Lösung.

Mein Problem damals war, das es bei Plänen dieser Art eine Periodizität gibt, die ein menschlicher Planer so umsetzen würde ("Meistens hat Herr K alle 3 Sonntage frei, dafür hat Frau Z. Donnerstags frei"). Ein Algorithmus (zumindest der von mir erdachte) hat aber etwas ziemlich Chaotisches erzeugt.

Die Leute konnten dann einfach ihre Freizeit nicht so gut planen.

Aber man könnte auch diese Periodizität als Kriterium für "ein guter Plan" heranziehen...

[DanielJ]

Hallo,

wir haben seinerzeit die Mitarbeiter vorher ihre Wunscharbeitszeit angeben lassen, übereinstimmung mit den Wünschen war dann Opimierungskriterium. Dabei konnten Mitarbeiter ihre Wochenstunden auch "überplanen" und so der Maschiene mehr Planungsspielraum lassen.
Eine 2 von 4 Samstage - Regel gabe es auch, wer also einen Bestimmten Samstag frei haben wollte, konnte das System dazu überreden in dem er einfach die beidien vorherigen Samstage einen "Arbeitswunsch" angegeben hat.

Ausserdem gab es "Nicht planbare zeiten" z.B. für Studenten die zu bestimmten zeiten Vorlesung hatten, Mütter etc. - Diese haben als "Hartes Kritierium" eine Plan lebensunfähig werden lassen.

Insgesamt hat das ganz gut funktioniert mit deutlich über 90%iger übereinstimmung mit der Wunschplanung - die Parameter waren für sowas aber auch günstiger.
(ich mein es waren so ungefähr ~150 Personen mit im Schnitt ca 30 stunden auf ~100 Arbeitsplätze die 55 stunden zur Verfügung standen - gleichmäßige Auslastung auch als ein weiches Kriterium)