Exponentiellen Aufwand bei Ressourcen-Planung reduzieren

Hallo Community

Aktuell arbeite ich an einer Ressourcen-Planung, bei der ich an einem Problem mit exponentiellem Rechenaufwand zu knabbern habe.

Es geht darum n Batches mit Tasks auf m Resourcen aufzuteilen. Die Tasks haben einen Start-Zeitpunkt und eine Duration und dürfen sich nicht überschneiden. Die Tasks pro Batch folgen zeitlich aufeinander und haben eine feste Reihenfolge.

Kennt jemand einen Algorithmus, der sich darauf anwenden lässt? Lässt sich der Aufwand für dieses Problem überhaupt reduzieren? Ich habe leider noch nichts passendes gefunden.

Task
- Start
- Duration
- End

Batch
- Tasks
        
Resource
- Tasks

Beim Einsortieren der Tasks auf die Ressourcen entstehen zwischen drin immer wieder Lücken, diese möchte ich nutzen um das Ergebnis zu optimieren.

foreach batch in batches
    foreach batchTask in batch
        foreach resourceTask in resource
            if batchTask.Start > resourceTask.End && batch.End < nextResourceTask.Start
                resource.Insert(behind resourceTask)

Im Pseudocode sieht man gut, wie sich der Aufwand exponentiell erhöht.

Hier ein kleines Beispiel für die bessere Vorstellbarkeit:

[Batch 1]
- Anton (Resource A) füllt einen Eimer mit Farbe (2 min) und bring in zu Bernd (Resource B)
- B nimmt diesen Eimer und streicht damit eine Wand (25 min)
- A wäscht den benutzen Eimer (4 min)

[Batch 2]
- Anton bringt ein Kabel und Nagel-Schellen (1 min) zu Carlos (Resource C)
- C verlegt das Kabel (35 min)

[Batch 3]
- Anton belädt den Bauaufzug mit Ziegeln und lässt sie nach oben fahren (15 min)
- Daniel (Resource D) deckt damit das Dach (55 min)

Es sollen 18 Wände gestrichen und 12 Kabel verlegt werden. Das Dach braucht 7 Fuhren um gedeckt zu werden.

Gruss
Alf

Wenn das wirklich so "simpel" ist, dann erinnert mich das ein wenig an den Greedy Algo, auch wenns vielleicht nicht 100% passt - ist aber recht beliebt bei simplen Scheduling Implementierungen.

Für boolsches Scheduling im Maschinenbau hab ich auch schon mal den Constraint-Satisfaction Solver angewandt, der auch ein wenig in die Richtung geht wenn es komplexer wird. Google hat da ne recht nette Seite für https://developers.google.com/optimization und auch nen NuGet Package https://www.nuget.org/packages/Google.OrTools

Zitat von Abt

.. Google hat da ne recht nette Seite für https://developers.google.com/optimization und auch nen NuGet Package https://www.nuget.org/packages/Google.OrTools

Das ist perfekt, vielen Dank!

(https://developers.google.com/optimization/scheduling/job_shop)