DAA - Jobsequenzierung mit Frist

Problemstellung

Bei Jobsequenzierungsproblemen besteht das Ziel darin, eine Sequenz von Jobs zu finden, die innerhalb ihrer Fristen abgeschlossen wird und maximalen Gewinn bietet.

Lösung

Betrachten wir eine Reihe von ngegebene Jobs, die mit Fristen und Gewinn verbunden sind, werden verdient, wenn ein Job innerhalb seiner Frist abgeschlossen ist. Diese Jobs müssen so bestellt werden, dass ein maximaler Gewinn erzielt wird.

Es kann vorkommen, dass nicht alle angegebenen Aufträge innerhalb ihrer Fristen ausgeführt werden.

Angenommen, Frist von i^th Job J_i ist d_i und der Gewinn aus diesem Job ist p_i. Daher ist die optimale Lösung dieses Algorithmus eine praktikable Lösung mit maximalem Gewinn.

Somit ist $ D (i)> 0 $ für $ 1 \ leqslant i \ leqslant n $.

Zu Beginn werden diese Jobs nach Gewinn sortiert, dh $ p_ {1} \ geqslant p_ {2} \ geqslant p_ {3} \ geqslant \: ... \: \ geqslant p_ {n} $.

Algorithm: Job-Sequencing-With-Deadline (D, J, n, k) 
D(0) := J(0) := 0 
k := 1 
J(1) := 1   // means first job is selected 
for i = 2 … n do 
   r := k 
   while D(J(r)) > D(i) and D(J(r)) ≠ r do 
      r := r – 1 
   if D(J(r)) ≤ D(i) and D(i) > r then 
      for l = k … r + 1 by -1 do 
         J(l + 1) := J(l) 
         J(r + 1) := i 
         k := k + 1

Analyse

In diesem Algorithmus verwenden wir zwei Schleifen, eine befindet sich in einer anderen. Daher ist die Komplexität dieses Algorithmus $ O (n ^ 2) $.

Beispiel

Betrachten wir eine Reihe gegebener Jobs, wie in der folgenden Tabelle gezeigt. Wir müssen eine Reihe von Jobs finden, die innerhalb ihrer Fristen abgeschlossen werden und maximalen Gewinn bringen. Jeder Job ist mit einer Frist und einem Gewinn verbunden.

Job	J₁	J₂	J₃	J₄	J₅
Frist	2	1	3	2	1
Profitieren	60	100	20	40	20

Lösung

Um dieses Problem zu lösen, werden die angegebenen Jobs in absteigender Reihenfolge nach ihrem Gewinn sortiert. Daher werden die Jobs nach dem Sortieren wie in der folgenden Tabelle gezeigt sortiert.

Job	J₂	J₁	J₄	J₃	J₅
Frist	1	2	2	3	1
Profitieren	100	60	40	20	20

Aus diesen Jobs wählen wir zuerst aus J₂, da es innerhalb seiner Frist abgeschlossen werden kann und maximalen Gewinn beiträgt.

Nächster, J₁ wird ausgewählt, da es im Vergleich zu mehr Gewinn bringt J₄.
In der nächsten Uhr J₄ kann daher nicht ausgewählt werden, da die Frist abgelaufen ist J₃ wird ausgewählt, wenn es innerhalb seiner Frist ausgeführt wird.
Die Arbeit J₅ wird verworfen, da es nicht innerhalb seiner Frist ausgeführt werden kann.

Die Lösung ist also die Reihenfolge der Jobs (J₂, J₁, J₃), die innerhalb ihrer Frist ausgeführt werden und maximalen Gewinn bringen.

Der Gesamtgewinn dieser Sequenz beträgt 100 + 60 + 20 = 180.