Gantt Diagramm Aufgabe lösen?
Verstehe nicht die Herangehensweise vielleicht kann mir jemand auf die Sprünge helfen. Mfg
1 Antwort
Ist Knapsack, somit NP-schwer, somit nicht wirklich leicht optimal zu lösen.
Semi-optimal könnte aber klappen.
Mein Ansatz dazu wäre der folgende, du sollst aber wohl einen speziell genannten Algorithmus anwenden:
Du könntest es mit einem Greedy-Algorithmus versuchen, der klappt bei manchen Dingen optimal, aber nicht immer.
Meine Idee dazu wäre, erst einmal die Blöcke der Reihenfolge nach sortieren, sodass du auf einen Blick sehen kannst, welcher Block vor dem anderen kommen darf und welcher nicht.
Dann würde ich mit dem größten Block anfangen, den du setzen kannst, die anderen Maschinen dann mit möglichst passenden Blöcken besetzen. Im nächsten Schritt dannd asselbe für die nächste Gruppe von Blöcken.
Wenn du das hast kannst du versuchen zu optimieren, beispielsweise Leerräume zu füllen.
Nach deinem Algorithmus, der Kürzeste-Operations-Zeit, solltst du es aber genau andersherum machen:
Hier sollst du jeweils den nächsten möglichen Block wählen, der die kürzeste Zeit benötigt.
In der Praxis sähe es auch noch einmal anders aus. Da würdest du vermutlich solche Blöcke bevorzugen, die bald fertig werden müssen, und sichergehen, dass kein Block ewig auf fertigstellung wartet.
Für weitere Infos zu dem Thema, informiere dich zu "Scheduling". Insbesondere im Fachbereich der Informatik findet sich her viel dazu (quasi jedes Betriebssystem für den Heimbetrieb macht das, was du hier machen sollst, die ganze Zeit in der ein oder anderen Form.)