In Job-Sequenzierung Problem ist das Ziel, die Reihenfolge der Aufträge, die innerhalb ihrer Fristen abgeschlossen ist und geben maximalen Gewinn zu finden.
Wenn eine Reihe von n Jobs angegeben werden, die mit Fristen verbunden sind, und ein Gewinn erzielt wird und ein Job innerhalb seiner Frist abgeschlossen wird. Diese Jobs müssen so bestellt werden, dass ein maximaler Gewinn erzielt wird.
Nehmen wir ein Beispiel. Wie in Abbildung 1.1 gezeigt, wird eine Reihe von Jobs angegeben, bei denen jeder Job eine Frist und einen damit verbundenen Gewinn hat, wenn der Job vor Ablauf der Frist abgeschlossen ist. Es ist auch gegeben, dass jeder Job einzelne Zeiteinheit nimmt, so dass die minimal mögliche Frist für jeden Job ist 1. So maximieren Sie den Gesamtgewinn, wenn jeweils nur ein Job geplant werden kann.
Eine einfache Lösung besteht darin, alle Teilmengen einer bestimmten Menge von Jobs zu generieren und die einzelne Teilmenge auf Machbarkeit von Jobs in dieser Teilmenge zu überprüfen. Verfolgen Sie den maximalen Gewinn unter allen möglichen Teilmengen. Die zeitliche Komplexität dieser Lösung ist exponentiell.Wir können dieses Problem auch mit einer gierigen Methode lösen, die optimaler ist als eine einfache Lösung.Lösen wir dieses Problem also über die gierige Methode.
Um das Jobsequenzierungsproblem über die Greedy-Methode zu lösen, gehen Sie folgendermaßen vor:
- Sortieren Sie alle Jobs in absteigender Reihenfolge des Gewinns.
- Initialisiert die Ergebnissequenz als ersten Job in sortierten Jobs.
- Folgen Sie für die verbleibenden n-1-Jobs.
- Wenn der aktuelle Job in die aktuelle Ergebnissequenz passt, ohne die Frist zu verpassen, fügen Sie den aktuellen Job zum Ergebnis hinzu. Andernfalls ignorieren Sie den aktuellen Job.
Wie Sie in Abbildung 1.1 sehen können, sind die Arbeitsplätze bereits in absteigender Reihenfolge des Gewinns.Hier hat Job 1 den höchsten Gewinn und die Frist ist 3, also stellen Sie diesen Job zwischen 2-3 ein, wie in Abbildung 1.2 gezeigt.Job 2 hat den zweithöchsten Gewinn und die Frist ist 4, also stellen Sie diesen Job zwischen 3-4 ein und machen Sie dasselbe mit allen jobs.So die letzte Sequenz ist J4-J3-J1-J2 und der Gesamtgewinn beträgt 110.
Sie können den Code für diesen Algorithmus unter https://www.geeksforgeeks.org/job-sequencing-problem bevorzugen.
Die Zeitkomplexität dieser Lösung ist O (n2).Es kann durch disjunkte Datenstruktur optimiert werden.
Hoffe der Artikel gefällt euch.Danke 🙂
