BANCA EXAMINADORA:

Com amor para Sandra, Eduardo, Jacqueline e Renato

• Ao professor Ricardo M. Barcia, por me incentivar a fazer o doutorado e pela orientação.
• Ao professor Osama Eyada, pela paciência com o meu Inglês e pela orientação.
• Aos professores Adedeji B. Badiru, diretor do Expert Systems Laboratory, School of Industrial Engineeering, University of Oklahoma, Norman OK, USA. e Raymond Li, do Department of Bussiness Systems of the Monash University, Clayton, Australia, por terem fornecido o material necessário à execução dos experimentos.
• Ao professor Luiz F. Heineck, pela ajuda e sugestões.
• Ao CNPq, pelo suporte financeiro.
• Ao André e a Carla, pela amizade.
• Ao José e a Kristini, por seus trabalhos de revisão do manuscrito.
• Aos colegas e funcionários do departamento, pela amizade e o estímulo.
• Ao Ciro e a Aida, pelo amor, o apoio material, a renúncia e principalmente, a Deus por ter-los escolhido como meus pais.
• A minha família na Bolívia, que mesmo a distância me brindou amor e apoio, e a toda minha família brasileira, por ter me acolhido como filho e irmão.
• Finalmente, um especial reconhecimento a minha esposa Sandra pelo amor, a confiança, a abnegação, a compreensão e o apoio em todas as horas, e aos meus filhos Eduardo, Jacqueline e Renato, por entender, suportar e perdoar as minhas falhas.
  
  

RESUMO

ABSTRACT

CAPÍTULO 1

INTRODUÇÃO

1.1. Origem do Trabalho

1.2. Justificativa do Trabalho

1.3. Objetivos do Trabalho

1.4. Organização do Trabalho


CAPÍTULO 2

REVISÃO DA LITERATURA

2.1 O Problema de Programação

2.2 Revisão da História do Desenvolvimento da Teoria da Programação

2.3 O Problema de Programação no Contexto dos Problemas de Otimização Combinatorial

2.4 Um Modelo Geral de Programação

2.5 Complexidade dos Problemas de Programação

2.6 Abordagens para o Problema de Programação

2.7 Classificação dos Problemas de Programação

2.7.1 Problema de Programação da Produção

2.7.2 Problema de Programação de Projetos

2.7.3 Problema de Linha de Montagem

2.8 Relações e Principais Diferenças entre os Problemas de Programação

2.9 Programação de Projetos de Construção com Recursos Limitados

2.9.1 Noções Fundamentais

2.9.2 Tipo de Problema Abordado

2.9.3 Abordagens para o Problema

2.9.4 Formulação Geral do Problema Abordado

2.9.5 Trabalhos Prévios

2.9.6 Conclusões da Revisão da Literatura de Programação de Projetos

2.10 Conceitos Fundamentais de Algoritmos Genéticos

2.10.1 Esquema

2.10.2 Representação da Estrutura de Solução

2.10.3 Tamanho da População e Número de Gerações

2.10.4 Operadores Genéticos

2.10.5 Aplicações de Algoritmos Genéticos à Problemas de Programação


CAPÍTULO 3

UM ALGORITMO EVOLUTIVO PARA A PROGRAMAÇÃO DE PROJETOS

3.1. Abordagem Proposta

3.2. Módulo de Planejamento

3.2.1. Dados Relativos às Atividades

3.2.2. Dados Relativos aos Recursos

3.3. Módulo de Programação Baseado em Algoritmos Genéticos

3.3.1. Função Objetivo

3.3.2. Representação do Problema

3.3.3. Geração da População Inicial de Soluções Viáveis

3.3.4. Avaliação das Soluções Geradas

3.3.5. Operadores Genéticos do Modelo

3.4. Implementação Computacional do Modelo

3.5. Planejamento dos Experimentos

3.5.1. Ajuste dos Valores dos Parâmetros do Algoritmo Genético do Modelo

3.5.2. Eficiência do Modelo

3.5.3. Critérios para a Avaliação da Eficiência do Modelo


CAPÍTULO 4

RESULTADOS NUMÉRICOS

4.1. Características dos Problemas Testados

4.2. Parâmetros do Algoritmo Genético

4.3. Medidas de Desempenho para o Modelo

4.4. Resultados Numéricos da Comparação


CAPÍTULO 5

CONCLUSÕES E RECOMENDAÇÕES

5.1 Conclusões

5.2 Recomendações


BIBLIOGRAFIA


ANEXO I

Figura 2.1 Classificação dos Problemas de Otimização Combinatorial (Ibaraki, 1988)

Figura 2.2 Classificação dos Problemas de Otimização Combinatoriais (Müller -Merbach, 1981)

Figura 2.3 Representação Esquemática para Problemas de Programação da Produção

Figura 2.4 Representação Esquemática dos Problemas de Programação de Projetos

Figura 2.5 Fases das Operações na Administração de Projetos de Construção

Figura 2.6 Procedimento Heurístico Básico para a Programação de Projetos

Figura 3.1 Arquitetura Geral do Modelo Proposto

Figura 3.2 Representação Esquemática do Módulo de Planejamento

Figura 3.3 Relações de Dependência

Figura 3.4 Representação Esquemática do Módulo de Programação

Figura 3.5 Diagrama de Precedências para um Projeto Ilustrativo

Figura 3.6 Representações Legais e Ilegais de uma Programação

Figura 3.7 Representação do Problema de Programação Múltiplos Modos

Figura 3.8 Gerador de Soluções Iniciais Viáveis

Figura 3.9 Representação Esquemática do Processo de Programação das Atividades

Figura 3.10 Utilização de Recursos em Alternativas de Mesma Duração

Figura 3.11 Utilização de Múltiplos Recursos em Alternativas de Mesma Duração

Figura 3.12 Rede Simples para o Problema de 1 Processador e 5 Tarefas

Figura 3.13 Rede Simples para o Problema de 3 Tarefas e 2 Recursos

Figura 3.14 Complexidade de Redes Versus Disponibilidade de Recursos

Figura 5.1 Programações Ótimas para o Problema 26

Tabela 2.1 Alguns Problemas NP-Completos (Adaptado de Lenstra, 1977)

Tabela 2.2 Problemas de Programação NP-Completos

Tabela 2.3 Problemas de um Estágio com um Processador

Tabela 2.4 Problema um Estágio - Processadores Paralelos

Tabela 2.5 Problemas Múltiplos Estágios - Flow-Shop

Tabela 2.6 Problemas Múltiplos Estágios - Job-Shop

Tabela 2.7 Problemas de programação de Projetos

Tabela 2.8 Relações Mútuas entre Problemas Básicos de Programação (Adaptado De Davis, 1973)

Tabela 2.9 Regras Heurísticas mais Comuns

Tabela 3.1 Exemplo de Relações Recursos-Durações

Tabela 3.2 Dados para o Projeto Ilustrado na Figura 3.5

Tabela 3.3 Elementos de uma População de um Algoritmo Genético

Tabela 3.4 Aptidões e Probabilidades de Reprodução dos Elementos de uma População

Tabela 3.5 Aptidões e Probabilidades de Reprodução Modificadas pelo FPUR

Tabela 3.6 Medidas de Complexidade de Redes

Tabela 4.1 Características dos Problemas Teste

Tabela 4.2 Número de Gerações e Tamanho de População Experimentadas

Tabela 4.3 Contagem do Número de Vezes que o Ótimo foi Atingido

Tabela 4.4 Comparação das Durações sob Restrição de Recursos para Diferentes Regras de Prioridade - Estudo do Badiru (1988)

Tabela 4.5 Comparação das Durações sob Restrição de Recursos para Diferentes Regras de Prioridade - Estudo de Li e Willis (1992)

Tabela 4.6 Comparação da Taxa de Eficiência de Regra rm n - Conjunto de Problemas I

Tabela 4.7 Comparação da Taxa de Eficiência de Regra rm n - Conjunto de Problemas II

Tabela 4.8 Comparação das Durações para os Problemas Teste

Tabela 4.9 Taxas de Melhoria da Solução em Relação à Melhor Heurística

Tabela 4.10 Taxas de Melhoria da Solução em Relação à Melhor Heurística Global

Tabela 4.11 Taxas de Melhoria da Solução Considerando o Tamanho dos Problemas - Conjunto de Problemas Grandes

Tabela 4.12 Taxas de Melhoria da Solução Considerando o Tamanho dos Problemas - Conjunto de Problemas Pequenos

Tabela 4.13 Taxa de Atraso de Projeto Utilizando o Modelo e a Melhor Heurística

Tabela 4.14 Melhoria das Soluções Obtidas pelo Modelo Considerando Múltiplos Modos

Tabela 4. 15 Variação do Fator Ponderado de Utilização de Recursos - Caso Único Modo

Tabela 4.16 Variação do Fator Ponderado de Utilização de Recursos - Caso Múltiplos Modos

Tabela 4.17 Tempos de CPU para os Problemas Experimentados

Tabela 4.18 Tempos de CPU Segundo as Características dos Problemas Experimentados - Único Modo