Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Problema de agendamento de processos com data limite utilizando programação dinâmica

0 votos
13 visitas
perguntada Out 16 em Ciência da Computação por Matheus Cintrão (26 pontos)  

Este problema foi apresentado como exercício no capítulo 2 do livo "Dynamic programing: a computational tool", se trata do exercício 2.8 - Scheduling with deadlines.

O objetivo do exercício é desenvolver um algorítimo utilizando programação dinâmica para encontrar a melhor ordem de execução de 5 atividades ou processos que possuem data limite diferente e tem retornos diferentes. Neste caso a duração de cada um é a mesma. todos tem duração unitária.

Este problema costuma ser resolvido por algorítimos gananciosos (greed), mas neste caso o autor pede que a solução seja feita através de programação dinâmica.

Neste exercício temos 5 tarefas, i = {0, 1, 2, 3, 4} com retornos g={10, 15, 20, 1, 5} e deadlines d={1, 2, 2, 3, 3}, respectivamente.

a função proposta pelo autor para resolver o problema é:
\[f(k,S) = max_{d \in S} \lbrace c(d \vert S) + f(k+1, S - \lbrace d \rbrace ) \rbrace \]
onde \(c(d \vert S) = g_d\) , se \(d\) for incluido no conjunto \(S\), e \(c(d \vert S) = 0\), caso contrário.

O autor também informa que a resposta correta é escolher a seguinte ordem de tarefas: 1, 2 e 4. Ou seja, tarefa 1 no tempo 1, tarefa 2 no tempo 2 e tarefa 4 no tempo 3.

Compartilhe

1 Resposta

0 votos
respondida Out 16 por Matheus Cintrão (26 pontos)  

O próprio autor sugere uma implementação em java mais a frente no capítulo. Eu optei por seguir um exemplo um pouco diferente retirado de um exercício maior. O código a seguir pode ser utilizado para problemas onde o tempo dos procedimentos também é diferente, ou seja, não é unitário. O código a seguir possui duas etapas:
1) Gerar a tabela com os valores de ótimos de da função \(f\) para cada tempo, \(t\) e para cada processo \(i\). Este procedimento segue a lógica apresentada pelo autor, mas com uma pequena alteração ao considerar a variável l (L minúsculo) que é a duração do processo. É importante destacar que este procedimento exige que os dados estejam organizados em orgem crescente de "deadline"
2) Extrair da tabela e sequência de decisões ótimas. Esta etapa é feita através de uma função recursiva que será definida no início do código. Ela não se presta a resolver o problema de maximização, apenas extrair de forma clara a sequência de decisões ótimas tomadas.

import numpy as np

def escolhaOtima(i, t):
    if i != 0:
        if B[i][t] == B[i-1][t]:
            escolhaOtima(i-1, t)
        else:
            print("processo " + str(i),"será realizado no tempo "+ str(t)) 
            t = min([t, d[i]]) - l[i]
            escolhaOtima(i-1, t)
if __name__ == '__main__':
    #Dados:

    g = [10, 15, 20, 1, 5] #recompensa do processo
    l = [1, 1, 1, 1, 1] #duração do processo
    d = [1, 2, 2, 3, 3] #deadline do processo
    n = len(g) #número de processos
    f = max(d) #período final(ultimo prazo)
    #Primeiramente é necessário que os jobs estejam organizados em ordem crescente de deadline.
    #Isto já é o caso nos dados do exercício, mas caso não fosse deveria ser feito este sort.

    B = np.zeros((n,f+1)) 

    for i in range(n):
        for t in range(f+1):
            t_lim = min([t, d[i]]) - l[i]
            if t_lim < 0:
                B[i, t] = B[i-1, t]
            else:
                 B[i, t] = max([B[i-1, t],B[i-1, t_lim]+g[i]])



    print(B)            
    escolhaOtima(n-1, f)

O \(n-1\) utilizado na fórmula escolhaOtima se deve ao fato de que a contagem dos elementos é feita de \(1 \rightarrow n\), enquanto a enumeração dos elementos é feita de \(0 \rightarrow (n-1)\), por isso o ajuste é necessário.

O resultado obtido é:

 [[ 0. 10. 10. 10.]
  [ 0. 15. 25. 25.]
  [ 0. 20. 35. 35.]
  [ 0. 20. 35. 36.]
  [ 0. 20. 35. 40.]]
 processo 4 será realizado no tempo 3
 processo 2 será realizado no tempo 2
 processo 1 será realizado no tempo 1

Note que as linhas da matriz se referen aos processos e as colunas ao tempo. Foi incluido um tempo 0 apensas para facilitar as formulas.

comentou Nov 6 por CICERO FILHO (26 pontos)  
O exercício foi resolvido de forma muito clara e objetiva. Trago algumas comparações entre a abordagem Greedy e a programação dinâmica, alguns exemplos e quando qual é melhor que a outra.

As principais diferenças entre a abordagem Greedy e programação dinâmica são:

Conceito principal

Abordagem Greedy: escolher a melhor opção que traz a maior vantagem para a etapa atual.
Programação dinâmica: otimiza a solução de backstracking recursivo.

Otimalidade

Abordagem Greedy: somente se for possível provar que a otimização local leva à otimização global.
Programação dinâmica: oferece uma solução ideal.

Complexidade de tempo

Abordagem Greedy: polinomial
Programação dinâmica: polinomial, mas geralmente pior do que a abordagem Greedy.

Complexidade de memória

Abordagem Greedy: mais eficiente porque nunca olhamos para outras opções.
Programação dinâmica: Requer uma tabela DP para armazenar a resposta dos cálculos.

Exemplos

Abordagem Greedy: algoritmo de Dijkstra e Prim
Programação dinâmica: 0/1 Knapsack e subsequência crescente mais longa.

Comentários gerais: de forma geral, se for possível resolver o problema usando uma abordagem Greedy, geralmente é a melhor escolha. No entanto, alguns problemas podem exigir uma abordagem Greedy muito complexa ou não podem ser resolvidos com essa abordagem. Neste caso, deve-se otimizar a solução recursiva para implementar uma abordagem de programação dinâmica.
comentou Nov 9 por Matheus Cintrão (26 pontos)  
Obrigado pela complementação Cícero
...