Sobre a Complexidade de um Algoritmo Clássico para Escalonamento de Projetos com Maximização de Valor Presente Líquido

Entre os problemas de escalonamento de projetos está a maximização de Valor Presente Líquido (VPL) sem restrição de recursos, com precedência do tipo término-início e lag zero entre as atividades. Para esse problema, Demeulemeester et al. [1996] propuseram um algoritmo organizado em três passos. De acordo com tais autores, o primeiro e o segundo passos ocorrem em tempo de complexidade O(n^2). No entanto, a complexidade do terceiro e mais importante dos passos era uma questão em aberto até então, impossibilitando determinar a complexidade total do algoritmo. Assim, neste trabalho, apresentamos uma análise da complexidade para esse passo, onde o pior caso ocorre em um arranjo com atividades sequenciais, que exige o máximo de desconexões e conexões entre as atividades. Deste modo, o terceiro passo também se configura em tempo de complexidade O(n^2). Tal caracterização confirma a robustez da solução proposta, bem como contribui para outros algoritmos e trabalhos de pesquisa relacionados.