DAA - Sequenciamento de Trabalho com Prazo

Declaração do Problema

No problema de sequenciamento de tarefas, o objetivo é encontrar uma sequência de tarefas, que seja concluída dentro do prazo e que dê o máximo de lucro.

Solução

Vamos considerar um conjunto de ndeterminados trabalhos que estão associados a prazos e lucro é obtido, se um trabalho for concluído dentro do seu prazo. Esses trabalhos precisam ser ordenados de forma que haja lucro máximo.

Pode acontecer que todos os trabalhos fornecidos não sejam concluídos dentro dos seus prazos.

Suponha, prazo de i^th trabalho J_i é d_i e o lucro recebido por este trabalho é p_i. Portanto, a solução ótima desse algoritmo é uma solução viável com lucro máximo.

Assim, $ D (i)> 0 $ para $ 1 \ leqslant i \ leqslant n $.

Inicialmente, esses trabalhos são ordenados de acordo com o lucro, ou seja, $ 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

Análise

Neste algoritmo, estamos usando dois loops, um dentro do outro. Portanto, a complexidade desse algoritmo é $ O (n ^ 2) $.

Exemplo

Vamos considerar um conjunto de trabalhos fornecidos, conforme mostrado na tabela a seguir. Temos que encontrar uma sequência de trabalhos, que serão concluídos dentro dos prazos e darão o máximo de lucro. Cada trabalho está associado a um prazo e lucro.

Trabalho	J₁	J₂	J₃	J₄	J₅
Data limite	2	1	3	2	1
Lucro	60	100	20	40	20

Solução

Para resolver esse problema, os empregos fornecidos são classificados de acordo com seu lucro em ordem decrescente. Portanto, após a classificação, os trabalhos são ordenados conforme mostrado na tabela a seguir.

Trabalho	J₂	J₁	J₄	J₃	J₅
Data limite	1	2	2	3	1
Lucro	100	60	40	20	20

Deste conjunto de trabalhos, primeiro selecionamos J₂, pois pode ser concluído dentro do seu prazo e contribui com o lucro máximo.

Próximo, J₁ é selecionado porque dá mais lucro em comparação com J₄.
No próximo relógio, J₄ não pode ser selecionado porque seu prazo acabou, portanto J₃ é selecionado à medida que é executado dentro de seu prazo.
O emprego J₅ é descartado porque não pode ser executado dentro do prazo.

Assim, a solução é a sequência de jobs (J₂, J₁, J₃), que estão sendo executados dentro do prazo e dão lucro máximo.

O lucro total desta sequência é 100 + 60 + 20 = 180.