JavaScript Funktion zur Erstellung optimaler Kombinationen

[-Rayz-]

Guten Morgen,
ich suche eine Funktion bzw. bin an einer dran die mir leicht Kopfschmerzen bereitet.. erstmal zur Erklärung:
In Angular habe ich folgendes Array und einen Startpunkt:

let start = 1;
const example = [
    {
        taskId: 1,
        limit: 5,
        needed: 3,
        combinations: [
            {
                firstId: 1,
                secondId: 123,
                val1: null,
                val2: null
            },
            {
                firstId: 2,
                secondId: 123,
                val1: null,
                val2: null
            },
            {
                firstId: 2,
                secondId: 456,
                val1: null,
                val2: null
            }
        ]
    },
    {
        taskId: 2,
        limit:8,
        needed: 5,
        combinations: [
            {
                firstId: 1,
                secondId: 123,
                val1: null,
                val2: null
            },

        ]
    }
]

Nun brauche ich folgende Funktion. jedes Objekt hat verschiedene Kombinationsmöglichkeiten. Ziel ist es, die beste Kombination zu finden.Wir starten bei 1. Needed zeigt an, was benötigt wird.
Die erste mögliche Kombination wäre also:
{
firstId: 1,
secondId: 123,
val1: 1,
val2: 3
},
Dadurch wurde die firstId und secondId nun mit 1 - 3 belegt. Man könnte aber auch die anderen Kombinationen mit diesem Wert belegen.
Das nächste Objekt mit TaskId: 2 hat nur eine Kombinationsmöglichkeit und zwar mit den Ids 1 und 123.
Dadurch, dass aber die 1 und auch die 123 bereits mit 1-3 belegt wurden, müssen wir hier allerdings mit 4 anfangen. Plus die 5 die benötigt werden, blockieren nun die IDs 1 und 123 zusätzlich den Zahlenraum 4-9.Besser wäre es allerdings gewesen, hätte das erste Objekt die Ids ausgewählt, die das zweite Objekt eh nicht besitzt. In dem Fall 2 und 456. Dann würde diese nämlich die Zahlen 1-3 für die IDs 2 und 456 blockieren. Das zweite Objekt hätte dann zwei freie Ids 1 und 123 und könnte dann auch bei 1 anfangen und hätte dann die Zahlen 1-6.Das hier sind nur Beispielzahlen und ein Array kann ca. 20-80 solcher Tasks besitzen mit ca. 10-20 Kombinationen.

Nun benötige ich eine Funktion, um halt das Optimum zu finden.Zum Thema limit noch was. Das Limit gibt an, das versucht werden sollte, dass ein bestimmter Wert nicht überschritten werden sollte, sofern es sich vermeiden lässt. Hätte das zweite Objekt die Zahlen 4-9 bekommen, wäre das z.b. über dem Limit von 8.

Im ersten Schritt hatte ich vor, jede Kombination in einem Set als json zu speichern um dann mit has zu überprüfen, ob dieser Wert bereits vorhanden ist oder nicht.
Das ganze innerhalb einer While Schleife wo die Abbruchbedingung wäre, wenn ich in einem Durchgang bei keiner Kombination mehr neue Werte hinzufügen kann.

Über weitere Ideen wäre ich sehr dankbar.

 

[floq0r]

Und ich kriege Kopfschmerzen wenn ich mir dieses Requirement anschaue:

• Was bezeichnet "firstId" und "secondId"?
• Sollen die Werte in "val1" und "val2" IDs sein oder worauf beziehen sie sich?
• Worum geht es hier überhaupt? Erklär das etwas greifbarer, wenn das so abstrakt bleibt kann zumindest ich mir nichts gescheites dazu überlegen.

 

[-Rayz-]

Das ist ja nur ein Beispiel. Die Benennung ist eigentlich egal, die Funktion dahinter sollte halt die gleiche bleiben.
Aber es geht hier um eine Zuweisung von Aufgaben zu Geräten und Mitarbeitern. Eine Aufgabe kann von mehreren Geräten bedient werden. Ein Gerät wiederum von mehreren Mitarbeitern. Am Ende brauch eine Aufgabe halt ein zugewiesenes Gerät und einen Mitarbeiter.
Eine Aufgabe hat aber auch eine Deadline die versucht werden sollte, einzuhalten. Auch hat eine Aufgabe immer eine geschätzte Dauer. D.h ein Start,-und Enddatum.
Während dieser Zeit ist Gerät und Mitarbeiter natürlich blockiert.

Das mal eine Deadline gerissen wird, kann nicht verhindert werden. Aber es soll halt das best mögliche versucht werden.
Was später dann zusätzlich hinzukommt ist, ist eine Aufgabe vor der Deadline fertig, und es kommt eine Aufgabe mit der gleichen ID rein und die Deadline liegt nicht weiter in der Zukunft als z.b. 3 Wochen, dann sollte diese Aufgabe an die bestehende angehängt werden. Ohne aber irgendwo anders die Deadline zu reißen, falls diese sonst noch eingehalten werden könnte.
Aber das letzte Thema mit Aufgaben zusammenfassen ist erstmal optional.

Hoffe es ist nun greifbarer.

Ich hab das auch schon geschrieben das Programm. Aber weil ich einfach für rekursives Zeug zu dumm bin, ist meine Funktion ewig lang + mir fehlt der Teil der best möglichen Kombination. Ich Priorisiere einfach nach der Deadline, und erstelle dann meine Aufgaben.
Ob es aber nicht noch bessere Möglichkeiten in der Zuweisung gibt, überprüfe ich gar nicht.

 

[floq0r]

Ok und wie legt sich dieses Logik auf dein Beispiel um? Was ist "needed", was ist "val1" und "val2", heißt "1-3" jetzt "eins bis drei" oder "eins und drei"?

 

[-Rayz-]

needed sind die Tage die eine Aufgabe benötigt.
val1 wäre Startdatum, val2 Enddatum.
Startdatum ist immer der aktuelle Tag, ansonsten natürlich der frühst mögliche freie Tag.
Limit ist die Anzahl der Tage bis die Deadline erreicht ist.

 

[KingLz]

Sind Geräte und Mitarbeiter alle gleich und Austauschbär?
Gibt es pro Gerät immer einen Mitarbeiter? Sollen Geräte/Mitarbeiter Kombinationen gehalten werden oder können die auch einfach wechseln? Können sie auch während einer Aufgabe wechseln?

Wenn alles beliebig getauscht werden kann, was spricht gegen ein simples Aufgaben nach Deadline sortieren und einfach aufsteigend zuordnen von freien Resourcen nach einfachem FIFO (ähnlichem) Prinzip?

 

[floq0r]

Verstehe, ich würde dann wahrscheinlich zunächst eine Priorisierung festlegen, damit die Tasks als erstes bearbeitet werden, die bei den zur Verfügung stehenden Ressourcen (Kombinationen) am wenigsten flexibel sind. Vielleicht wäre es auch brauchbar den Ressourcenpool objektorientiert zu führen, damit du in deinen Iterationen leichter feststellen kannst welche Ressourcen zu welchem Zeitpunkt verfügbar sind, so ala ressourcePool.getAvailableRessourcesForTask(taskID)

 

[-Rayz-]

@KingLz
Ne, sind nicht gleich. Aufgaben können, müssen aber nicht jedes Gerät besitzen. Auch haben Mitarbeiter nur Zugriffe zu den Geräten, die Ihnen zugewiesen wurden.
Und ja... sie können wechseln in mitten einer Aufgabe. Z.b. wenn das Gerät kaputt geht oder Mitarbeiter krank wird.

@floq0r

Meine bisherige Priorisierung bezieht sich halt zuerst auf die Deadline.
Danach schaue ich nach, welche Geräte + mitarbeiter evtl. noch gar keine Zuweisung bekommen haben und nehme dann diese.
Aber dadurch kann halt oben beschriebenes Problem entstehen. Das ich anfangs etwas zuweise, was halt nicht optimal wäre. Weil ich es bei der Zuweisung an der Stelle noch gar nicht weiß.

Deswegen dachte ich noch, dass ich nicht nur nach der Deadline priorisiere sondern auch nach der Anzahl möglicher Geräte und Mitarbeitern.
Dacht macht aber nur Sinn, wenn das Tool frisch gestartet wird und man nicht viel Auswahl hat...
Jede Aufgabe hat aber eine Auswahl von ca. 5-8 Geräten und jedes Gerät eine Auswahl von 6-20 Mitarbeitern.

 

[floq0r]

Ein paar lose Gedanken dazu:

• Ist die Zuweisung einer Ressource mit der Dauer von 6 Tagen zu einem Task gleichwertig mit zwei Zuweisungen zu zwei Tasks von jeweils 3 Tagen?
• Ist es besser verpasste Deadlines zu verhindern oder die Auslastung zu maximieren?
• Ist es vorzuziehen, wenn Ressource A 5 Tage Task 1 zugewiesen wird anstatt 3 Tage zu Task 2 wenn bei beiden Tasks die Deadline nicht eingehalten wird?

Der iterative Ansatz ist vermutlich eh die einzige Möglichkeit. Wenn es darum geht die Auslastung zu maximieren dann kannst du den Zielwert gut feststellen und probieren mit welcher Priorisierung du die beste Lösung erhältst.

 

[KingLz]

Ohne das riesen Diagramm jetzt durchzuarbeiten (sry, aber dafür keine Zeit), wäre meine Einschätzung des Problems folgendes.

Im Prinzip handelt es sich um ein Task Scheduling Problem, wie in einer CPU.
Ich glaube nicht dass rekursiv die Lösung zu suchen wirklich alle Optionen durchzuprobieren der Lösungsweg ist.

Die Aufgaben sollten nach der Deadline priorisiert sein.
Die Geräte würde ich nach geschätzer oder bekannter Auslastung (was in der Vergangenheit war oder wie oft es in der Zukunft benutzt werden muss) priorisieren, da ein Gerät welches für jede Aufgabe verwendet werden muss vermutlich der Flaschenhals sein wird.

Mein erster Ansatz wäre halt:

Aufgaben nach Deadlines aufsteigend sortieren und auswählen.
Geräte nach erwarteter Auslastung absteigend sortieren und auswählen.
Mitarbeiter für jedes Gerät absteigend nach Flexibilität (wie viele verschiedene Geräte außer dem aktuellen bedient werden können) sortieren und auswählen.

Damit müsste man, so wie ich das Problem bisher verstehe, eine relativ gute Aufteilung erreichen.
Naja, sind erstmal nur ein paar Gedanken in den Raum geworfen, ich hoffe es kann helfen.

 

[-Rayz-]

@floq0r
Punkt 1
hängt natürlich von der Deadline ab. Ansonsten ja, ist gleichwertig. Was hier aber noch ein Nice to have wäre.. Kommt die gleiche Aufgaben ID erneut rein, und kann aber nicht an eine bestehende drangehängt werden, so möchte man versuchen das gleiche Gerät + Mitarbeiter an die neue Aufgabe zu hängen. Das hat den einfachen Grund, damit man das Gerät für eine Aufgabe anderer ID nicht extra wieder umbauen muss.

Punkt 2
verpasste Deadlines verhindern

Punkt 3
in dem Fall wäre es egal.
Optimum wäre dann halt, die Deadline so gering wie möglich zu reißen

@KingLz
Dein Ansatz wäre zwar nicht das Optimum aber wie du schon sagtest, durch die unterschiedlichen Sortierungen fängt man wahrscheinlich vieles ab.


Schon einmal danke für die bisherigen Antworten. So komme ich bei dem Thema auch endlich mal auf neue Gedankengänge. Je länger ich mich damit beschäftige umso festgefahrener sind meine Ideen dazu.

 

[floq0r]

Punkt 1 wäre dann nur eine weitere Priorisierung. Das ganze wäre ja ein Paradebeispiel für AI/neural networks

 

[-Rayz-]

Damit hab ich halt noch nie etwas gemacht.. wüsste nicht mal wie ich das Thema dazu anfangen sollte um es in mein Projekt zu migrieren

 

[-Rayz-]

Ich habe nun eine Sortierungsfunktion mit Priorisierung:

  return data.sort((a, b) => {
    const lengthA = a.tasksAssigned.length + a.possibleTasks.length;
    const lengthB = b.tasksAssigned.length + b.possibleTasks.length;

  
    if (a.tasksAssigned.length === 0 && b.tasksAssigned.length > 0) {
      return -1;
    } else if (b.tasksAssigned.length === 0 && a.tasksAssigned.length > 0) {
      return 1;
    }
    const dayA = moment(a.latestDate).format('YYYY-MM-DD');
    const dayB = moment(b.latestDate).format('YYYY-MM-DD');
    if (dayA !== dayB) {
      return moment(dayA).diff(dayB,'day');
    }
    return lengthA - lengthB;
  });

höchste Priorisierung ist, wenn noch keine Aufgabe vorhanden ist.
Danach, wann das frühste Datum wäre und zum Schluss, wer halt am wenigsten zu tun hat. Das nutze ich dann für Geräte + Mitarbeiter und aktualisiere nach jedem Durchlauf einer Aufgabe die Sortierung.