Algoritmos baseados em busca tabu e busca tabu reativa para problemas generalizados de programação de projetos
| Autor: | Silva, Juliana Simões e |
|---|---|
| Jazyk: | portugalština |
| Rok vydání: | 2004 |
| Zdroj: | Repositório Institucional da UnicampUniversidade Estadual de CampinasUNICAMP. |
| Druh dokumentu: | masterThesis |
| Popis: | Orientador: Vinicius Amaral Armentano Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação Made available in DSpace on 2018-08-04T02:52:54Z (GMT). No. of bitstreams: 1 Silva_JulianaSimoese_M.pdf: 629718 bytes, checksum: ceb1677c1d500c414d75ed2eb8112ad7 (MD5) Previous issue date: 2004 O problema clássico de programação de projetos com restrição de recursos consiste de atividades, sujeitas a relações de precedência, que têm duração fixa e competem por recursos limitados. Este problema envolve a determinação do instante de início das atividades com o objetivo de minimizar o tempo de término do projeto. Diversas extensões do problema clássico têm sido consideradas na literatura para modelar problemas reais. Uma destas extensões é o problema abordado neste trabalho, denominado problema generalizado de programação de projetos com restrição de recursos. O problema generalizado considera duas extensões do problema clássico. A primeira envolve relações de precedência representadas por intervalos mínimos de tempo entre início de duas atividades, que são importantes em ambientes de produção ¿make-to-order¿, quando existe um tempo de preparação de máquina independente da seqüência entre duas atividades. A segunda extensão consiste de disponibilidade de recursos variante no tempo, que incorpora situações em que somente um subconjunto do total da mão-de-obra ou de máquinas está disponível devido a férias ou manutenção. Devido à alta complexidade combinatória do problema, utilizam-se métodos heurísticos para a resolução de problemas de porte real. Algoritmos que combinam conceitos de busca tabu e busca tabu reativa são propostos e implementados computacionalmente. O desempenho destes é comparado com um algoritmo de busca tabu reativa da literatura The classical resource constrained project scheduling problem consists of activities with fixed duration and subject to precedence relations, which compete for limited resources. This problem involves the determination of the starting time of the activities in order to minimize the completion time of the project. Several extensions of the classical problem have been addressed in the literature to model real problems. One of these extensions is the problem tackled in this work, named generalized resource constrained project scheduling problem. The generalized variant considers two extensions in relation to the classical problem. The first one involves the representation of precedence relations among activities, by means of a minimum time interval between two activities, which is important in the make-to-order production setting, when a machine setup time is incurred between the processing of two activities. The second extension considers that the resource availability is time varying, which represents the situation where only a subset of the total manpower and machines is available due to vacation or maintenance. Due to the high combinatorial complexity of this problem, heuristic methods are used to solve real size problems. Algorithms that combine concepts from tabu search and reactive tabu search are proposed and computationally implemented. Their performance is tested against a reactive tabu search algorithm from the literature Mestrado Automação Mestre em Engenharia Elétrica |
| Databáze: | Networked Digital Library of Theses & Dissertations |
| Externí odkaz: |
|