Gestão de projetos: problema do escalonamento em projetos multinível

Dissertação de mestrado em Engenharia de SistemasO problema apresentado aqui pertence à classe dos problemas de escalonamento de projetos com atividades multinível (ou multimodo), ou em terminologia anglo-saxónica: Multi-mode, Multi-skill Resource Constrained Project Scheduling Problem (MRCPSP-MS). Isto significa que as atividades podem ser executadas em modos diferentes, cada modo utiliza níveis de recursos diferentes, o que implica diferentes custos e durações. A cada atividade deve ser alocada exatamente uma unidade de cada recurso necessário e a unidade de recurso pode ser usada em qualquer um dos seus níveis definidos. O tempo de processamento de uma atividade é dado pelo máximo da duração que resultaria de uma alocação específica de recursos. O objetivo é encontrar a melhor solução que minimize o custo global do projeto, respeitando a data de entrega. Está incluída uma penalidade, para atrasos além da data de entrega especificada e um bónus para a conclusão antecipada do projeto. Num algoritmo Breadth First Search (BFS), todos os nós (soluções parciais) na árvore de pesquisa, são avaliados em cada etapa antes de prosseguir, efetuando assim uma pesquisa exaustiva, que visita todos os nós da árvore. A técnica Branch and Bound (B&B) pode ser vista como um BFS “polido”, uma vez que aplica alguns critérios, a fim de reduzir a complexidade BFS. Geralmente consiste em guardar a melhor solução encontrada até o momento, descartando um nó se este não puder oferecer uma solução melhor. O procedimento Filtered Beam Search (FBS) é uma heurística B&B que utiliza BFS mas apenas os melhores nós são mantidos. Em cada estágio da árvore, são gerados todos os sucessores para os nós selecionados na etapa atual, mas só é guardado um número predefinido de nós descendentes, denominado beam width. Em Santos e Tereso (2010a), apresentamos um modelo formal para MRCPSP-MS e um procedimento BFS. Depois, em Santos e Tereso (2010b), apresentamos a adaptação de um algoritmo FBS a este problema. Em Santos e Tereso (2011a, 2011b), relatamos resultados computacionais, testando a aplicação através de projetos de diferentes dimensões. A aplicação desenvolvida permite determinar a solução do projeto, usando o algoritmo BFS ou o algoritmo FBS. A implementação foi projetada utilizando a linguagem C#.The problem presented here belongs to the class of the optimization scheduling problems with multi-level (or multi-mode) activities, i.e., the Multi-mode, Multi-skill Resource Constrained Project Scheduling Problem (MRCPSP-MS). This means that the activities can be scheduled at different modes, each mode using a different resource level, implying different costs and durations. Each activity must be allocated exactly one unit of each required resource and the resource unit may be used at any of its specified levels. The processing time of an activity is given by the maximum of the durations that would result from a specific allocation of resources. The objective is to find the optimal solution that minimizes the overall project cost, while respecting a delivery date. A penalty and a bonus are included, for tardiness beyond the specified delivery date and for early completion, respectively. In a Breadth First Search (BFS) algorithm, all the nodes (partial solutions) in the search tree are evaluated at each stage before going any deeper, subsequently realizing an exhaustive search that visits all nodes of the search tree. The branch and bound (B&B) search technique can be seen as a polished breadth first search, since it applies some criteria in order to reduce the BFS complexity. Usually it consists of keeping track of the best solution found so far, discarding a node if it cannot offer a better solution. A Filtered Beam Search (FBS) is a heuristic B&B procedure that uses BFS but only the top best nodes are kept. At each stage of the tree, it generates all successors for the selected nodes at the current stage, but only stores a preset number of descendent nodes at each stage, called the beam width. In Santos and Tereso (2010a) we presented a formal model MRCPSP-MS and a breadth-first search procedure description. Then in Santos and Tereso (2010b) we presented an adaptation of a FBS algorithm to this problem. In Santos and Tereso (2011a, 2011b) we reported on further computational results, by testing the application for different problem sizes. The application developed allows determining the project solution using the BFS algorithm or the FBS algorithm procedure. The implementation was designed using the C# language