Uma abordagem Branch and Bound para RCPSP em um ambiente de computação colaborativa

Submitted by Elaine Almeida (elaine.almeida@nce.ufrj.br) on 2017-05-09T16:56:00Z No. of bitstreams: 1 09_04_000635609.pdf: 237511 bytes, checksum: b25149aa9f2ea96ac2fd0882b255307f (MD5)Made available in DSpace on 2017-05-09T16:56:00Z (GMT). No. of bitstreams: 1 09_04_000635609.pdf: 237511 bytes, checksum: b25149aa9f2ea96ac2fd0882b255307f (MD5) Previous issue date: 2004-12-31Um 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