Made available in DSpace on 2016-12-23T14:33:39Z (GMT). No. of bitstreams: 1 Dissertacao_CRAVO_G_L_2009.pdf: 1278828 bytes, checksum: ebab7f313edc64bb51241b5c7d587d33 (MD5) Previous issue date: 2009-06-25 / This master s thesis presents an implementation of the GRASP meta-heuristic for solving the Multi-mode Resource constrained Problem of Scheduling Project (MRCPSP). The MRCPSP belongs to the class NP-Hard and therefore has received attention of many researchers. In this thesis, a case study problem of Scheduling Industrial Maintenance is viewed as a MRCPSP. The GRASP was tested with a set of benchmark tests obtained from PSPLIB (Project Scheduling Library). The results showed that the GRASP is a good strategy for solving MRCPSP instances. / Esse trabalho apresenta uma implementação da meta-heurística GRASP para a resolução do Problema de Escalonamento de Projetos com Restrições de Recursos e Múltiplos Modos de Processamento (MRCPSP). O MRCPSP é um problema da classe NP Difícil e por isso vem recebendo atenção dos pesquisadores. Nessa dissertação, também é apresentado um estudo de caso cujo problema de Programação de Manutenção Industrial é visto como um problema de escalonamento de projeto. O GRASP foi testado com o conjunto de instâncias do MRCPSP disponíveis na PSPLIB (Project Scheduling Problem Library). Os resultados obtidos mostraram que o GRASP proposto se configura como uma boa estratégia de solução para o MRCPSP.

In the field of operations research, the set of scheduling problems of activities is considered as one of the most relevant ones due to its great applicability and complexity. Within the broad variety of problems in this set, it is remarkable the Resource-Constrained Project Scheduling Problem (RCPSP), since it is regarded as the most important-base problem in this area and it has been the object of study in countless research projects. Basically, this problem consists of a project split into sets of activities that are related to each other by means of precedence-constraints, and require an amount of each limited resource, to be performed. The objective, then, is to allocate in the most efficient way those resources to the activities in order to optimize a scoring function such as the makespan. Similar in importance is the multimodal-version of the RCPSP, called MRCPSP, in which for each activity there exists multiple execution modes that involve a different combination of limited resources, giving rise to a different execution time. In the literature, it has been addressed widely these two problems with both exact methods and approximation methods, being these latter the most successful. These research works have focused mainly on obtaining economic advantages such as costs and project time minimization. However, with the accelerating globalization and the fast countries' growing economies, the race for power resources have increased sharply. In fact, the importance of taking into account the energy consumption on modeling has become so important that it is now considered as important as other performance measures such as productivity and costs. Hence, the main goal of this Ph.D. dissertation is to develop a new RCPSP and MRCPSP approach based on the energetic efficiency, which is aimed at searching for sustainable solutions in terms of time and energy consumption. To this end, it has been proposed an extension of the RCPSP, named MRCPSP-ENERGY, which considers besides the traditional resources of the RCPSP, a variable energetic consumption that generates different execution modes for the activities. This proposal includes a new optimization criterion based on the energetic efficiency of a project, which considers simultaneously the minimization of both the total duration and the energy consumption of such project. Moreover, in order to assess the solution methods for the MRCPSP-ENERGY, the standard library mostly used for this purpose has been extended and a new one has been proposed, called PSPLIB-ENERGY. In order to solve the proposed problem, firstly, the most successful metaheuristics methods, which address the RCPSP, were analyzed. Secondly, it was shown that these methods lead to redundant solutions, hindering the search. Therefore, an evolutive method was proposed, whose main contribution is the development of a new mutation operator that reduces the number of redundant solutions. Similarly, in the multimodal case, it was determined that the most widespread searching methods are also focused on the activity list representation and therefore they yield redundant solutions. As a solution alternative for the MRCPSP-ENERGY, it was shown that such search can be carried out by focusing on the mode list representation, as different mode lists also reach diverse solutions, giving rise to a less number of redundant solutions. Keeping in mind this finds, it was proposed a new evolutive method for solving the MRCPSP-ENERGY, which unifies both searching methods such that the search is conducted with two optimization phases. Based on the obtained results given by the PSPLIB-ENERGY library, the proposed method proved to be able to reach highly efficient solutions. / En la investigación operativa, el conjunto de problemas de secuenciación de actividades es considerado como uno de los más relevantes debido a su gran aplicabilidad y complejidad. Dentro de la amplia variedad de problemas en este conjunto, destaca el problema de programación de tareas con recursos restringidos (RCPSP por su sigla en inglés), pues es considerado como el problema base más importante en esta área y ha sido objeto de estudio de numerosas investigaciones. Básicamente, consiste de un proyecto subdividido en un conjunto de actividades que se encuentran relacionadas mediante restricciones de precedencia y requieren, para ser ejecutadas, una cantidad de cada tipo de recurso cuya disponibilidad máxima se encuentra limitada. El objetivo es asignar los recursos a las actividades de la manera más eficiente posible para optimizar una medida de desempeño, por ejemplo, la duración total del proyecto. Igualmente importante es la versión multi-modal del RCPSP, llamada MRCPSP, en la que para cada actividad existen múltiples modos de ejecución que involucran una combinación diferente de recursos limitados, dando origen a un tiempo de ejecución distinto. En la literatura se han abordado ampliamente estos dos problemas tanto con métodos exactos como de aproximación, siendo estos últimos los más exitosos. Estos trabajos se han centrado principalmente en la obtención de beneficios económicos, como la minimización de los costes o la obtención de la mínima duración del proyecto. Sin embargo, con la aceleración de la globalización y el rápido desarrollo de los países, la competencia por recursos energéticos ha aumentado drásticamente. Incluso, la importancia de tener en cuenta el consumo de energía en los modelos ha crecido de tal manera que, ahora es considerado con la misma relevancia que otras medidas de desempeño como la productividad y los costes. Así, el objetivo principal de esta tesis es desarrollar un nuevo enfoque del RCPSP y del MRCPSP, basado en la eficiencia energética, la cual busca soluciones sostenibles en términos de tiempo y de consumo energético. Para este fin, se ha propuesto una extensión del RCPSP denominada MRCPSP-ENERGY, la cual considera, además de los recursos tradicionales del RCPSP, un consumo de energía variable que da origen a distintos modos de ejecución de las actividades. Esta propuesta incluye un nuevo criterio de optimización basado en la eficiencia energética del proyecto, que tiene en cuenta de manera simultánea la minimización de la duración del proyecto y el consumo total de energía. Adicionalmente, con el objetivo de evaluar los métodos de solución para el MRCPSP-ENERGY, se ha ampliado la librería estándar de prueba más extendida para el RCPSP y se ha propuesto una nueva librería, denominada PSPLIB-ENERGY. Para encontrar solución al problema propuesto, primero se analizaron los mejores métodos metaheurísticos que abordan el RCPSP. Luego, se identificó que estos métodos conducen a soluciones redundantes, entorpeciendo la búsqueda. Por tanto, se propuso un método evolutivo cuya principal aportación es el desarrollo de un nuevo operador de mutación que disminuye la generación de soluciones redundantes. Similarmente, en el caso multi-modal se detectó que los principales métodos de búsqueda también se centran en la representación de lista de actividades y por tanto generan soluciones redundantes. Como alternativa de solución para el MRCPSP-ENERGY, se mostró que la búsqueda puede realizarse enfocándose en la lista de modos, ya que diferentes listas de modos también pueden alcanzar soluciones distintas, generando un menor número de soluciones redundantes. Teniendo en cuenta estos hallazgos, se propuso un nuevo método evolutivo para resolver el MRCPSP-ENERGY, que unifica ambos métodos de búsqueda para realizarla en dos fases de optimización. Basándose en los resultados obtenidos en la PSPLIB-ENERGY, se concluye que el m / En la investigació operativa, el conjunt de problemes de seqüenciació d'activitats és considerat com un dels més rellevants a causa de la seua gran aplicabilitat i complexitat. Dins de l'àmplia varietat de problemes en este conjunt, destaca el problema de programació de tasques amb recursos restringits (RCPSP per la seua sigla en anglés) , perquè és considerat com el problema base més important en esta àrea i ha sigut objecte d'estudi de nombroses investigacions. Bàsicament, consistix d'un projecte subdividit en un conjunt d'activitats que es troben relacionades per mitjà de restriccions de precedència i requerixen, per a ser executades, una quantitat de cada tipus de recurs la disponibilitat màxima de la qual es troba limitada. L'objectiu és assignar els recursos a les activitats de la manera més eficient possible per a optimitzar una mesura d'exercici, per exemple, la duració total del projecte. Igualment important és la versió multi- modal del RCPSP, crida MRCPSP, en la que per a cada activitat hi ha múltiples modes d'execució que involucren una combinació diferent de recursos limitats, donant origen a un temps d'execució distint. En la literatura s'han abordat àmpliament estos dos problemes tant amb mètodes exactes com d'aproximació, sent estos últims els més reeixits. Estos treballs s'han centrat principalment en l'obtenció de beneficis econòmics, com la minimització dels costos o l'obtenció de la mínima duració del projecte. No obstant això, amb l'acceleració de la globalització i el ràpid desenrotllament dels països, la competència per recursos energètics ha augmentat dràsticament. Inclús, la importància de tindre en compte el consum d'energia en els models ha crescut de tal manera que, ara és considerat amb la mateixa rellevància que altres mesures d'exercici com la productivitat i els costos. Així, l'objectiu principal d'esta tesi és desenrotllar un nou enfocament del RCPSP i del MRCPSP, basat en l'eficiència energètica, la qual busca solucions sostenibles en termes de temps i de consum energètic. Per a este fi, s'ha proposat una extensió del RCPSP denominada MRCPSP- ENERGY, la qual considera, a més dels recursos tradicionals del RCPSP, un consum d'energia variable que dóna origen a distints modes d'execució de les activitats. Esta proposta inclou un nou criteri d'optimització basat en l'eficiència energètica del projecte, que té en compte de manera simultània la minimització de la duració del projecte i el consum total d'energia. Addicionalment, amb l'objectiu d'avaluar els mètodes de solució per al MRCPSP-ENERGY, s'ha ampliat la llibreria estàndard de prova més estesa per al RCPSP i s'ha proposat una nova llibreria, denominada PSPLIB-ENERGY. Per a trobar solució al problema proposat, primer es van analitzar els millors mètodes metaheurísticos que aborden el RCPSP. Després, es va identificar que estos mètodes conduïxen a solucions redundants, entorpint la busca. Per tant, es va proposar un mètode evolutiu la principal aportació del qual és el desenrotllament d'un nou operador de mutació que disminuïx la generació de solucions redundants. Semblantment, en el cas multi- modal es va detectar que els principals mètodes de busca també se centren en la representació de llista d'activitats i per tant generen solucions redundants. Com a alternativa de solució per al MRCPSP-ENERGY, es va mostrar que la busca pot realitzar-se enfocant-se en la llista de modes, ja que diferents llistes de modes també poden aconseguir solucions distintes, generant un menor nombre de solucions redundants. Tenint en compte estes troballes, es va proposar un nou mètode evolutiu per a resoldre el MRCPSP-ENERGY, que unifica ambdós mètodes de busca per a realitzar-la en dos fases d'optimització. Basant-se en els resultats obtinguts en la PSPLIB-ENERGY, es conclou que el mètode proposat és capaç d'aconseguir solucions altament eficients. / Morillo Torres, D. (2017). Eficiencia energética en la programación de tareas con recursos restringidos [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/90654