Relatório
Uma abordagem Branch and Bound para RCPSP em um ambiente de computação colaborativa
Registro en:
LOURENÇO, F. C. et al. Uma abordagem Branch and Bound para RCPSP em um ambiente de computação colaborativa. Rio de Janeiro: NCE, UFRJ, 2004. 6 p. (Relatório Técnico, 04/09)
Autor
Lourenço, Fábio Campos
Pereira, Felipe C.
Schmitz, Eber Assis
França, Felipe M. G.
Institución
Resumen
Um projeto pode ser representado por uma rede de atividades formando um grafo de precedência, direcionado e acíclico. Quando a quantidade de recursos existentes é limitada, o problema de determinação do menor tempo de realização do projeto é conhecido como RCPSP (Resource Constrained Project Scheduling). A solução ótima para o problema RCPS é reconhecidamente NP-hard. Este artigo mostra um algoritmo distribuído para a solução ótima do problema RCPS usando uma abordagem branch and bound. Este algoritmo foi implementado e avaliado num ambiente de computação colaborativa, do tipo peer to peer, com escalonamento adaptativo distribuído para balanceamento de carga nos nós computacionais. Os resultados sugerem a escalabilidade do algoritmo apenas com a adição de nós computacionais.