DAA - Sequenza dei lavori con scadenza

Dichiarazione problema

Nel problema della sequenza dei lavori, l'obiettivo è trovare una sequenza di lavori che venga completata entro le scadenze e dia il massimo profitto.

Soluzione

Consideriamo un insieme di ndeterminati lavori associati a scadenze e profitto viene guadagnato, se un lavoro viene completato entro la scadenza. Questi lavori devono essere ordinati in modo tale da ottenere il massimo profitto.

Può accadere che tutti i lavori forniti non vengano completati entro le scadenze.

Supponiamo, scadenza del i^th lavoro J_i è d_i e il profitto ricevuto da questo lavoro è p_i. Quindi, la soluzione ottimale di questo algoritmo è una soluzione fattibile con il massimo profitto.

Quindi, $ D (i)> 0 $ per $ 1 \ leqslant i \ leqslant n $.

Inizialmente, questi lavori sono ordinati in base al profitto, cioè $ 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

Analisi

In questo algoritmo, stiamo usando due loop, uno all'interno dell'altro. Quindi, la complessità di questo algoritmo è $ O (n ^ 2) $.

Esempio

Consideriamo un insieme di lavori dati come mostrato nella tabella seguente. Dobbiamo trovare una sequenza di lavori, che saranno completati entro le scadenze e daranno il massimo profitto. Ad ogni lavoro è associata una scadenza e un profitto.

Lavoro	J₁	J₂	J₃	J₄	J₅
Scadenza	2	1	3	2	1
Profitto	60	100	20	40	20

Soluzione

Per risolvere questo problema, i lavori forniti vengono ordinati in base al loro profitto in ordine decrescente. Quindi, dopo l'ordinamento, i lavori vengono ordinati come mostrato nella tabella seguente.

Lavoro	J₂	J₁	J₄	J₃	J₅
Scadenza	1	2	2	3	1
Profitto	100	60	40	20	20

Da questo insieme di lavori, prima selezioniamo J₂, poiché può essere completato entro la sua scadenza e contribuisce al massimo profitto.

Il prossimo, J₁ è selezionato in quanto dà più profitto rispetto a J₄.
Nel prossimo orologio, J₄ non può essere selezionato poiché la sua scadenza è scaduta, quindi J₃ è selezionato mentre viene eseguito entro la scadenza.
Il lavoro J₅ viene scartato in quanto non può essere eseguito entro la scadenza.

Quindi, la soluzione è la sequenza di lavori (J₂, J₁, J₃), che vengono eseguiti entro la loro scadenza e danno il massimo profitto.

Il profitto totale di questa sequenza è 100 + 60 + 20 = 180.