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

[mkinzler]

Leider hast du den Anhang vergessen.

[Mike_]

Zitat von mkinzler:

Leider hast du den Anhang vergessen.

Darin befand sich ein kleiner Fehler, es ist wiede drinne

[BUG]

Zitat von Mike_:

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
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 von BUG:

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.