Algoritmos de investigação operacional para um problema de sequenciamento de projectos

Abstract

Os problemas de sequenciamento (ou escalonamento) de projectos com recursos escassos em que as actividades podem ser executadas segundo diferentes modos têm merecido um interesse crescente por parte da comunidade científica. Uma das justificações prende-se com a adequação desses problemas à realidade dos projectos. Tipicamente, é possível realizar as actividades de um projecto de forma mais rápida desde que sejam investidos mais recursos. Na terminologia anglo-saxónica, esses problemas são designados por Multi-Mode Resource Constrained Project Scheduling Problem (MRCPSP). O objectivo do MRCPSP consiste em determinar o instante de tempo em que cada actividade deve ser iniciada e o modo que deve ser usado para realizar cada uma das actividades, sem que para isso sejam gastos mais recursos (renováveis e não renováveis) do que aqueles que estão disponíveis. Nesta dissertação, considera-se como objectivo a minimização da duração global do projecto, e não é permitida a interrupção das actividades. Um dos objectivos desta dissertação foi de avaliar a qualidade de modelos alternativos para o MRCPSP. Para tal, recorremos ao princípo da decomposição de Dantzig-Wolfe que aplicámos a um modelo compacto original descrito na literatura. Três novos modelos foram derivados usando esse princípio. Os resultados computacionais levados a cabo com base em instâncias da literatura permitiram aferir a qualidade dessas decomposições. Uma das decomposições provou ser de boa qualidade, obtendo-se a partir dela limites inferiores próximos do óptimo. Nesta dissertação, também se investigou uma heurística construtiva para o cálculo de limites superiores (soluções válidas) para o MRCPSP em que existem recursos não renováveis. A heurística foi implementada numa linguagem de programação, e testada usando uma vez mais instâncias da literatura. Os testes revelaram o bom desempenho do algoritmo.

Project scheduling problems with scarce resources where activities can be done in different modes have deserved an increasing interest from the scientific community. One may justify this situation by the adequacy of these problems to the reality of the real world projects. Typically, it is possible to execute the activities of a project faster if more resources are used for this purpose. This type of problems is formally known as the Multi-Mode Resource Constrained Project Scheduling Problem (MRCPSP). The objective of the MRCPSP is to determine when to start each activity and which mode should be used for each activity, ensuring at the same time that the limit of resources (renewable or non renewable) is never exceeded. In this dissertation, we deal with the problem where one wants to minimize the total duration without interrupting any activity. One of the goals of this dissertation was to evaluate the quality of alternative models for the MRCPSP. For that purpose, we used the principle of Dantzig-Wolfe decomposition that we applied to a compact and original model described in the literature. Three new models were derived using this principle. The computational tests realized with instances from the literature allowed to evaluate the quality of these decompositions. One of the decompositions proved to be of good quality. By using it, we were able to derive good lower bounds near from the optimum. In this dissertation, we also investigated a constructive heuristic for the computation of upper bounds (feasible solutions) for the MRCPSP, for the case where there are non renewable resources. The heuristic was implemented in a programming language and tested using once more instances from literature. The experiments proved that the heuristic performs well.