Algorithmus zur Verfügbarkeitsberechnung

[Mike_]

Guten Abend ihr Lieben,

diesmal handelt es sich um etwas ausgetüfteltes.

Es geht um einen Algorithmus (Siehe Anhang) welche aus den zugrunde liegenden Daten den besten Verfügbarkeitsplan berechnet.

Was ich meine wird klar, wenn Ihr den Anhang betrachetet.


Nun meine Frage:

a.) Gibt es solch einen Algo oder einen ähnlichen bereits ?
b.) Mein Ansatz ist, zu erst eine Gewichtung vorzunehmen. Die mit den geringsten 1en bei H1-H9 werden zu erst gesetzt. (Also in die Planung miteinbezogen)

Es wird jedoch jeder Wert vor dem direkten Eintragen in den "Endplan" mit dem nächst höheren in der Priorität abgeglichen (In meinem Beispiel wäre der nächst höhrere von PC4 PC3, da dieser nur 2 Stunden im Netz sein soll).

Beispiel:

PC4 hat A1 = 1
dann wird nachgeschaut ob PC3, welcher in der Priorität als nächstes kommt auch A1=1 hat.

Falls nicht, wird A1=1 für PC4 gesetzt.
Falls ja, wird der nächste Wert bei PC4 genommen (Sofern das Maximum an gecheckten H1-H9 nicht schon erreicht ist)




Also neben der Frage Nr. 1 oben, interessiert mich außerdem, ob Ihr einen besseren Ansatz habt oder ob es noch leichter (Oder besser berechnet) klappt ?

Man schreibt sich,

Mike :thumb:

[mkinzler]

Leider hast du den Anhang vergessen.

[Mike_]

Zitat:

Zitat von mkinzler (Beitrag 1080173)

Leider hast du den Anhang vergessen.

Darin befand sich ein kleiner Fehler, es ist wiede drinne :o

[BUG]

Zitat:

Zitat von Mike_ (Beitrag 1080172)

Es geht um einen Algorithmus (Siehe Anhang) welche aus den zugrunde liegenden Daten den besten Verfügbarkeitsplan berechnet.

Mir ist nicht ganz klar, was genau das Problem ist :gruebel:
Was ist für dich ein guter/bester Verfügbarkeitsplan?
Wann ist er besser als ein anderer?

[patti]

@BUG:
Wenn du dir die Tabelle anschaust, dann siehst du, dass pro Spalte nur eine 1 stehen darf, der Rest muss anscheinend 0 sein ;-)

[Mike_]

Es dürfen keine Zeiten nach Möglichkeit offen bleiben.

Würde das Tool z.B. chronologisch von oben nach unte zufällig die Zeiten wählen, dann würde der letzte PC4 zu keinen Zeiten mehr verfügbar sein.

Um bei meinem Beispiel zu bleiben, wenn es chronologisch wäre würde folgendes passieren:

PC1 1 1 1 0 0 0 0 0 0 0
PC2 0 X 0 0 0 0 0 0 1 1 <- Hier macht es zum ersten mal rums, da H2 belegt ist, aber 3 Verfügbarkeiten sein sollen (siehe Bild)
PC3 0 0 0 1 0 0 0 1 0 0
PC4 Hätte keine offenen Zeiten mehr, da H1-H4 bereits vergeben sind


Das wäre z.B. ein schlechter Algorithmus.

Ich brauche halt die beste Überlegung, wie ich mir die Stunden zur Verfügbarkeit (H1-H4) in Relation zu den Verfügbarkeiten der PC´s am besten heraussuche, dass nach Möglichkeit am Ende jeder PC im Plan steht.


Daher kam mir die Idee die PCs zu priorisieren nach der Gesamtverfügbarkeit (Alle 1en von H1-H9 addiert) und dann :

Beispiel an H1:

1.) Zu schauen ist H1 noch frei ?
Wenn ja dann wird geschaut ob PC3 auch H1 frei hat.
Wenn das der Fall ist, geht PC4 weiter und guckt bei H2 ob PC3 auch H2 noch nehmen kann.

Das "Problem" bzw eher suboptimale an meiner Überlegung ist halt, dass es dann keine optimale Berechnung ist !

Denn wenn der Algorithmus so vorgeht wie ich es vorschlage (Den PC mit der nächst höheren Priorität [Welche sich durch alle 1en von H1-H9 addiert bestimmt] abgleicht), kann es trotzdem vorkommen dass z.B. PC2 auch bei H1 frei ist aber auch NUR DORT verfügbar ist.

Wenn PC3 bei H1 keine Schicht hat, würde sich PC1 bei H1 jedoch eintragen und somit würde H1 dem Rest nicht mehr zur Verfügung stehen.


Ich hoffe ich konnte es treffend erklären :)

Eigentlich suche ich nach eine Methode die Quasi alle PC1 bis PC4 abgleicht und dann möglichst immer versucht ALLE einzuplanen, ohne dass jemand übrig bleibt bzw. unbesetze H1-H9 entstehen.

[BUG]

Wenn es insgesamt mehr PC-Stunden als 9 gibt, gibt es Zeiträume, in denen mehrere PCs laufen (oder es bleiben Stunden übrig).

Wenn es weniger gibt, ist keine Überdeckung möglich.

Wenn es genau so viele gibt: einfach nacheinander den PC freie Zeiträume zuteilen, geht ja genau auf.


Wie wird in jedem der drei Fälle die Qualität der Aufteilung ermittelt?

[jfheins]

Ich schlage mal "intelligentes Duchprobieren" vor.

Es gibt ja 2 Zustände, 0 und 1. Die Spaltensumme soll immer 1 ergeben, die Zeilensumme einen definierten Wert. Jetzt werden erstmal alle Summen gebildet. Dann wird geschaut, wo zuviel ist. (Klar soweit?) Dann jeweils die Zeile und die Spalte mit der größten Summe hernehmen und den Wert in der Zelle durch eine 0 ersetzen. Dann prüfen ob alle Bedingunen erfüllt wurden. Wenn nicht, den gleichen Algorithmus rekursiv anwenden, wenn das auch nicht hilft eine alternative Zelle auf 0 setzen.

Also eine (einfache) Heuristik und Backtracking. Könnte ganz gut funktionieren, und liefert garantiert ein Ergebnis wenn es eines gibt. Die Frage ist nur, wie lange es braucht - das kann ich jetzt nicht genau abschätzen. Für das Beispiel tippe ich mal auf eine Laufzeit unter 100ms.

[BUG]

Delphi-Quellcode:

function belegung(pcStunden: array[1..i] of Cardinal): array[1..j] of [0..i];
var
  aktPc: Cardinal;
  aktZeit: Cardinal;
begin
  // keine PCs zugeteilt
  for aktZeit := 1 to j do
    result[aktZeit] := 0;
  // nacheinander PCs durchgehen und Zeiten belegen
  aktZeit := 1;
  for aktPc := 1 to i do
  begin
    while pcStunden[aktPc] > 0 do
    begin
      if aktZeit > j then
        raise "Mehr PC-Stunden aus freie Zeiten";
      pcStunden[aktPc] := pcStunden[aktPc] - 1;
      result[aktZeit] := aktPc;
      aktZeit := aktZeit  + 1;
    end;
  end;
  if aktZeit <= j then
    raise "Weniger PC-Stunden als freie Zeiten";
end;

Das Ergebnis sieht dann so aus:

Code:

   |H1|H2|H3|H4|H5|H6|H7|H8|H9
PC1| 1| 1| 1| 0| 0| 0| 0| 0| 0
PC2| 0| 0| 0| 1| 1| 1| 0| 0| 0
PC3| 0| 0| 0| 0| 0| 0| 1| 1| 0
PC4| 0| 0| 0| 0| 0| 0| 0| 0| 1

Wieso möchtest du dieses Ergebnis nicht (ich nehme mal an du willst es nicht so)?

[jfheins]

Zitat:

Zitat von BUG (Beitrag 1080218)

Wieso möchtest du dieses Ergebnis nicht (ich nehme mal an du willst es nicht so)?

Also in dem Beispiel sind 2 "Matrizen" abgebildet, und zwar oben eine mit den Verfügbarkeiten. Und nur wo dort eine 1 steht, darf am Ende eine 1 stehen.

[jobo]

@Bug
Deine Lösung berücksichtigt nicht die >"Erreichbarkeit"

[BUG]

Zitat:

Zitat von jfheins (Beitrag 1080219)

Also in dem Beispiel sind 2 "Matrizen" abgebildet, und zwar oben eine mit den Verfügbarkeiten. Und nur wo dort eine 1 steht, darf am Ende eine 1 stehen.

Ich wusst doch, dass ich was übersehen habe :stupid:

[Mike_]

Zitat:

Zitat von BUG (Beitrag 1080204)

Wenn es insgesamt mehr PC-Stunden als 9 gibt, gibt es Zeiträume, in denen mehrere PCs laufen (oder es bleiben Stunden übrig).

Wenn es weniger gibt, ist keine Überdeckung möglich.

Wenn es genau so viele gibt: einfach nacheinander den PC freie Zeiträume zuteilen, geht ja genau auf.


Wie wird in jedem der drei Fälle die Qualität der Aufteilung ermittelt?

a.) Niedrigste Priorität.

b.) Kommt nicht vor, solche Eintragungen werden vorher abgefangen.

c.) Höchste Priorität.


__________________________________________________ ___________________________

*[Der Übersicht halber gelöscht, da meine Überlegungen ins leere liefen]*
__________________________________________________ ___________________________


Hier mal das "realere" Beispiel:

Zitat:

Siehe Bild im Anhang

Das bedeutet zu Zeit1 sollen 2 PC´s laufen.
Zu Zeit2 einer etc. .

SollZeit = Die "Zeit[i]", wie oft der PC eingetragen sein darf.
(z.B. PC1 darf nur in einem Zeit1 eingetragen sein)


Das optimale Ergebnis wäre z.B. so:

Zitat:

Siehe Bild im Anhang

Aber ich habe gerad den Überblick verloren wie man dahin kommt... ich geh jetzt erst einmal raus und schnap frische Luft um dann herumzuprobieren wie jfheins es vorgeschlagen hat.



Edit:\
@BUG, Wow.

Erstmal Danke für deine Arbeit ! :thumb:

Leider ist die Erreichbarkeit nicht berücksichtigt (Siehe Bild Post1)

[BUG]

Wenn ich das Ergebnis angucke:

• Die Gesamtzeit eines PCs kann im Ergebnis größer sein als die Soll-Zeit, aber nicht kleiner.
• Die Auslastung des Zeitraums ist eine obere Schranke, dh. weniger ist erlaubt.

Ist das richtig?

[Mike_]

Die SollZeit gibt an, wieviel der PC optimalerweise eingeplant werden soll.
D.h. die SollZeit darf nicht überschritten oder unterschritten werden.

PC war vllt kein gutes Beispiel.

Sagen wir Mitarbeiter.



Ein Mitarbeiter muss seine SollZeit schaffen, kann aber nur so eingetragen werden wie er selbst seine "Verfügbarkeit" (Die H´s) angibt.

Nun muss der Algorithmus entsprechend den Mitarbeiter so verplanen, dass dieser seine SollZeit schafft (Sofern möglich, kann auch sein dass es dafür gar keine Möglichkeit gibt).

Die "ZeitAuslastung" gibt dementsprechend an wieviele Mitarbeiter zum Zeitpunkt X (H1 / H2 / H3 etc) zur Verfügung stehen müssen.

Ich denke so lässt es sich einleuchtender veranschaulichen :stupid:


P.S.:
Ja, die Auslastung des Zeitraums ist das Optimum.
Sie soll möglichst 100 % erreicht werden !
(Wie gesagt, kann manchmal nicht möglich sein, aber dann soll der Algo das Optimum herausholen)

[Jumpy]

Da es schon recht spät für mich ist und ich nicht mehr klar denken kann nur eine Idee:

Geht das nicht in Richtung lineare Optimierung (da gibt es dann u.U. schon Algor. für, die man nur an sein Problem anpassen muss).

[Mike_]

Das ist (Nachdem zu urteilen was ich im Internet las) richtig.

Jedoch fand ich dazu keine Algorithmen.

Im Anhang noch einmal die "bugfreie" Version des vorher/nachher Zustandes.

[alzaimar]

Mit Backtracking geht das auf jeden Fall, so wie das aussieht sind es auch nicht endlos viele Möglichkeiten...
Und da es kein Kriterium für "Optimal" gibt, sondern nur für "OK", muss man auch nicht den ganzen Baum durchsuchen...

[Jumpy]

Das Simplex-Verfahren ist da glaub ich der Standard-Algorythmus. Wobei ich mich da auch nur aus einer lang vergessenen Numerik-Vorlesung dunkel dran erinnere, programmiert hab ich ihn auch noch nie gesehen.

Nur als Nebenbemerkung zu deinen Problem: Wenn du eine optimale Lösung irgendwie findest, muss diese nicht Eindeutig sein, d.h. es kann evtl. mehrere gleichwertige Lösungen geben.