CAPÍTULO 3

UM ALGORITMO EVOLUTIVO PARA A PROGRAMAÇÃO DE PROJETOS

Este capítulo introduz o modelo baseado em Algoritmos Genéticos proposto para resolver o problema de programação de projetos sob restrição de múltiplos recursos, no qual a duração de cada atividade depende da quantidade de recursos alocados para a sua execução, isto é, cada atividade pode ser realizada num dos vários diferentes modos de execução e cada modo é caracterizado por uma duração e uma dada demanda de recursos .

O modelo é amplo o suficiente para permitir manusear o problema que denominamos problema de otimização de tempo e nivelamento com recursos limitados. Este problema foi selecionado porque preenche uma lacuna na literatura da administração de projetos: a integração entre as técnicas de nivelamento de recursos e os métodos para a programação de projetos sob restrição de recursos.

O modelo proposto é desenvolvido baseado nas premissas formuladas no item 2.9.2 do capítulo 2. Quando a quantidade disponível de recursos não é suficiente para satisfazer a demanda das atividades concorrentes, torna-se necessário tomar decisões de programação onde as restrições nos recursos são violadas. Estas decisões podem levar ao aumento na duração do projeto além daquela determinada originalmente quando estas restrições são ignoradas. O objetivo é tomar as decisões de programação de forma a minimizar o incremento na duração do projeto, sujeito a restrições de precedências e de recursos.

Por outro lado, o problema do nivelamento de recursos surge quando existem recursos suficientes e torna-se necessário reduzir a flutuação nos padrões de utilização. O objetivo aqui é fazer com que a demanda dos recursos seja o mais uniforme possível.

No problema original de nivelamento, antagonicamente ao problema de alocação de recursos limitados, não existe restrição quanto ao emprego dos mesmos. O processo de nivelamento é realizado através da reprogramação das atividades não críticas dentro dos limites das suas folgas disponíveis, mantendo a duração do projeto fixa.

O conceito do nivelamento de recursos é incorporado ao modelo proposto de alocação de recursos limitados como um mecanismo guia na busca da melhor solução, esperando obter, não tão somente soluções com durações mínimas, como também, de certa forma nivelados.

A seguir são apresentados os vários componentes, bem como a discussão detalhada dos principais conceitos e premissas no qual o paradigma é fundamentado.

3.1 Abordagem Proposta

Como já discutido no capítulo anterior, as técnicas básicas de programação de projetos como o PERT e o CPM, são frequentemente inadequadas quando existem diversas atividades competindo pelos mesmos limitados meios. Nestas condições, a competição pelos recursos resulta em conflitos de programação. O processo que determina qual atividade deve ser programada e qual deve ser preterida é denominado resolução de conflito de recursos. A maneira como estes conflitos são resolvidos influenciam a duração total de um projeto, ou diferentes projetos de um conjunto de projetos.

Entretanto, a resolução de conflitos de recursos, a complexidade envolvida na programação de tarefas, e a relativa carência de sucesso com métodos matemáticos de otimização, tem levado frequentemente à busca de técnicas baseadas em heurísticas para a solução deste tipo de problemas.

A premissa básica da maioria dos procedimentos heurísticos para a programação de projetos com restrição de recursos é usar o critério de prioridade para ordenar as atividades, para então, programá-las de modo que as limitações dos recursos não sejam violadas e o menor caminho possível seja obtido.

Neste contexto, um modelo baseado em Algoritmos Genéticos é proposto como uma técnica heurística de solução do problema de programação de projetos multi-modos sob restrição de recursos. Esquematicamente, o sistema para a programação de projetos proposto é da forma representada na Figura 3.1.

O sistema consiste de 4 módulos principais: Interfase com o Usuário, Módulo de Planejamento, Módulo de Programação e Módulo Gerador de Relatórios. Os dois principais elementos do sistema, Módulo de Planejamento e Módulo de Programação, são descritos nos ítens 3.2 e 3.3.

3.2 Módulo de Planejamento

No estágio de entrada o sistema solicita ao usuário, via o módulo Interface com o Usuário, os dados necessários para a aplicação do algoritmo proposto, tais como descrição, relações de precedências, relações duração-recursos (modos) de cada atividade, descrição e níveis de disponibilidade dos diferentes tipos de recursos envolvidos, etc.
A figura 3.2 mostra esquematicamente a arquitetura deste módulo

As seções 3.2.1, 3.2.2 e 3.3.3. apresentam uma descrição geral dos diferentes elementos que compõem este módulo e descreve características importantes de cada um deles.

3.2.1 Dados Relativos às Atividades

Para a execução do sistema proposto é necessário fornecer uma completa identificação das atividades do projeto. As informações solicitadas incluem:

1. identificação das atividades,
2. conjunto das atividades antecessoras de cada atividade,
3. relação de dependência entre tarefas precedentes, e
4. relação tempo-recursos (modos de execução).

Os dados requeridos na identificação incluem código e nome da atividade, definição das relações de precedência através do estabelecimento do conjunto de todas as atividades imediatamente antecessoras.

Dentre os quatro tipos de relações de dependência mostrados na Figura 3.3 e que podem ser considerados num diagrama de precedência, somente o tipo tradicional fim-início é implementado no modelo (i.e. a sobreposição de atividades não é permitida).

Relação Tempo-Recursos (Modos De Execução).

Geralmente, é possível executar uma atividade de várias maneiras, cada uma delas utilizando uma combinação recursos-duração diferente. A despeito da maioria dos modelos tradicionais de programação de projetos com restrição de recursos, onde cada atividade é realizada em, exatamente, um único modo, o modelo desenvolvido incorpora vários modos alternativos para a execução de cada uma das atividades.A Tabela 3.1. ilustra relações típicas entre duração e demanda de recursos para uma atividade qualquer de um projeto. O exemplo mostra que uma atividade, tanto pode ser realizada em 6 dias por uma equipe de 3, como em 3 dias por uma equipe de 6 tipos de recursos

No modelo desenvolvido, as relações de recursos-durações para cada atividade, são consideradas como informações estáticas. Informação estática quer dizer que, antes da entrada da relação recurso-duração no sistema, as seguintes premissas foram assumidas:

• A duração de cada atividade, em cada um dos diversos modos de execução, é considerada determinística e permanece constante ao longo da execução da atividade. Uma vez estabelecida a duração, redução ou extensão da mesma não é permitida,
• A quantidade total de trabalho a ser executado permanece constante ao longo da duração da atividade,
• O nível de produtividade de cada modo é constante e conhecido de antemão,
• A combinação de recursos, que leva aos diferentes modos de execução de uma tarefa, é considerado previamente determinado através de qualquer método apropriado,
• Cada tarefa, uma vez iniciada num modo específico, deve ser concluída sem possibilidade de mudança de modo,
• Uma atividade iniciada deve ser totalmente concluída. Isto é, não é permitida a parada temporária de uma atividade em execução, para a liberação dos recursos por ela empregados.
  

3.2.2 Dados Relativos aos Recursos

Os recursos são necessários para a execução das atividades e as atividades são os elementos essenciais dos projetos. Portanto, os recursos podem ser considerados como componentes básicos na elaboração da programação de um projeto.

Os atributos relativos aos recursos, requeridos para a implementação do modelo compreendem:

1. tipos de recursos,
2. classes de recursos,
3. nível de disponibilidade de cada recurso, e
4. importância de cada recurso.

Tipos de Recursos

Os recursos considerados como entrada do modelo são classificados em quatro categorias: mão-de-obra, material, máquinas e dinheiro. Cada categoria é subdividida em tipos de recursos, como por exemplo, em mão-de-obra pode se ter carpinteiros, pedreiros, serventes, etc.

Dadas as características do trabalho desenvolvido em projetos de construção, frequentemente torna-se necessário o emprego de recursos de diversos tipos, com uma natural importância relativa associada a eles. Por exemplo, alguns recursos podem ser escassos, outros podem ser caros. Alguns podem necessitar de manuseio especial ou requerer de uma condição particular de operação. Desta forma, os diversos tipos de recursos podem influenciar de forma diferente a progamação de um projeto.

É muito comum que os recursos, sejam eles mão-de-obra, materiais, equipamentos ou dinheiro, tenham uma demanda maior que a oferta, ou sejam limitados por algum critério técnico ou administrativo. Os limites impostos nos recursos essenciais podem afetar significativamente o inicio, execução e término das atividades de uma programação e, muito provavelmente, será necessário estender a duração do projeto além da data desejada para poder atender estes limites.

Entretanto, há situações em que a extensão do projeto além da data de entrega é indesejada. Nestes casos, o problema de programação deve ser tratado como um problema de restrição de tempo, empregando técnicas de compressão de projetos ou de nivelamento de recursos na sua solução. Estas duas últimas situações pressupõem o uso irrestrito de recursos.

No desenvolvimento deste paradigma é proposto o emprego híbrido de técnicas de nivelamento e de otimização da duração de um projeto sob restrição de recursos, como discutido com mais detalhes no ítem 3.3.4.

Classes de Recursos

Por outro lado, na implementação do modelo somente são empregados recursos agrupados na classe de renováveis com disponibilidade constante, seguindo a classificação sugerida por Slowinski (1980), (1981) e Veglarz (1979), (1981), e discutida no ítem 2.7.2. Renováveis são todos aqueles recursos disponíveis em quantidades limitadas, porém que se renovam período a período. Por exemplo, a mão-de-obra: o número de operários disponíveis para trabalhar num projeto é limitada. Porém esta mão-de-obra pode ser renovada a cada período até um patamar pré-determinado.

Nível de Disponibilidade de Recursos

A disponibilidade constante de um recurso está relacionada com o nível de oferta de cada um dos recursos. O nível de disponibilidade refere-se à limitação na quantidade de um determinado tipo de recurso para um dado período de tempo.

Este nível de disponibilidade pode ser chamado de variável, se o limite na quantidade de recurso difere de período para período durante a execução de uma determinada atividade. É chamado de disponibilidade constante, como nas abordagens clássicas, se a quantidade, para cada tipo de recurso, permanecer inalterada ao longo da vida do projeto.

Importância Relativa de Recursos

Como já colocado linhas acima, dado o uso de diferentes tipos de recursos na execução de uma tarefa, é lógico esperar diferentes níveis de importância entre eles.

Um modelo efetivo para a programação de projetos de construção deve incorporar mecanismos que permitam estabelecer a importância relativa de recursos de natureza diferente. Por exemplo, um modelo deveria ser capaz de distinguir entre recursos limitados pela oferta, recursos limitados por restrições de campo, recursos limitados por restrições técnicas, e recursos limitados pelo custo, atribuindo-lhes pesos diferentes de acordo com a importância de cada um em relação à função objetivo.

Recursos limitados pela oferta são aqueles considerados escassos e difíceis de obter no mercado.

Recursos limitados por restrições de campo são aqueles que o seu emprego durante a execução do projeto está limitado pelas condições de espaço físico. Por exemplo, um projeto desenvolvido numa área grande, pode acomodar mais recursos de um dado tipo do que, outro projeto, confinado a uma área pequena.

Recursos limitados por restrições técnicas são aqueles que o seu uso é influenciado por fatores de natureza técnica ou tecnológica. A modo de ilustração, considere uma atividade que, por uma imposição técnica qualquer, requer o emprego de um guindaste de 10 Tons. e que não pode ser executada usando dois guindastes de 5 Tons. cada um.

Finalmente, um recurso facilmente obtido no mercado, e que por essa razão é considerado ilimitado, pode ser limitado por um critério financeiro. Neste sentido, o recurso pode ser considerado limitado pelo custo.

Por conseguinte, se recursos diferentes são considerados como tendo importâncias diferentes, então é possível assumir que eles podem influenciar uma função objetivo de forma diferente. Recursos escassos podem ter maior influência quando se considera minimização da duração de um projeto, da mesma forma, recursos caros podem ser considerados como tendo maior influência numa função objetivo que trata de minimização de custos.

Outra hipótese viável está relacionada com a possibilidade de usar esta importância relativa dos diversos tipos de recursos, como um meio de comparar diferentes soluções de programação que atingiram o mesmo valor na função objetivo.

É nestas premissas que o modelo desenvolvido se fundamenta para introduzir o nivelamento de recursos, como técnica de ponderação de soluções obtidas através do algoritmo genético.

Estes conceitos e premissas são discutidas na seção 3.3.4

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

O Módulo de Programação é um modelo protótipo que usa a abordagem de Algoritmos Genéticos para programar as atividades de um projeto de construção. O Módulo de Programação utiliza as informações gerenciadas pelo Módulo de Planejamento, relativas as atividades e recursos, para produzir a denominada Melhor Programação Possível.

O desenvolvimento da melhor programação possível é um processo de quatro estágios como ilustrado na Figura 3.4.

No primeiro estágio o módulo de programação consulta o módulo de planejamento para a leitura dos dados do projeto.

No segundo estágio é gerada uma população inicial de programações viáveis sem se preocupar com a duração final do projeto. Este conjunto de soluções viáveis (população) é gerado, usando uma representação única do problema aqui abordado, pelo denominado Gerador de Programações Viáveis.

No terceiro estágio, após se ter o conjunto de soluções viáveis, o módulo de programação avalia cada solução com relação à função objetivo, neste caso, a minimização da duração do projeto.

No quarto e último estágio, os operadores tradicionais de reprodução, cruzamento e mutação são aplicados na geração das populações futuras, levando em consideração a flutuação na utilização dos recursos empregados.

Basicamente, o modelo desenvolvido aloca os recursos independentemente para cada solução gerada pelo algoritmo, avalia a performance de cada solução com relação à função objetivo e à utilização dos recursos, e finalmente, recombina as melhores soluções.

A melhor programação possível é obtida após a execução repetitiva (até que o critério de parada tenha sido atingido) dos estágios três e quatro. A melhor solução possível é aquela que apresenta a menor duração com o menor índice de flutuação de utilização dos principais recursos.

Nas seções a seguir, os conceitos acima apresentados são discutidos com maiores detalhes.

3.3.1 Função Objetivo

Para os propósitos deste trabalho, a função objetivo é a minimização da duração de um projeto de construção nas bases expostas na seção 2.9.4

3.3.2 Representação do Problema

De forma a usar a abordagem de Algoritmos Genéticos como heurística de solução do problema em discussão, foi indispensável definir uma representação para o problema única e apropriada, como também foi importante que esta representação permitisse a aplicação amigável dos operadores próprios do algoritmo. Por outro lado, especificamente para o problema aqui tratado, procurou-se que a própria estrutura escolhida funcionasse diretamente, como regra de priorização das atividades, a ser empregada na resolução de conflitos de alocação de recursos.

A configuração escolhida, explora a semelhança entre a representação em forma de caracteres concatenados - "string", frequentemente empregados pelas abordagem de Algoritmos Genéticos nos problemas de otimização, e o procedimento de programação serial usado no problema de alocação de recursos limitados.

Na abordagem serial para o problema de alocação de recursos, todas as atividades são ordenadas através de uma heurística qualquer, em ordem de prioridade num único grupo. A seguir, as atividades são programadas uma de cada vez, isto é, em série. Por exemplo, no grupo de atividades CDBA a atividade C é executada primeiro, D segundo, seguidas por B e A.

Na abordagem paralela, as prioridades das atividades são determinadas durante a execução da programação, ao contrário do que antes, como no procedimento serial. Por exemplo, quando uma atividade não pode ser programada num dado período de tempo pela carência de recursos, ela é transferida para o próximo período onde nova ordem de prioridade para as atividades é estabelecida.

No escopo deste trabalho, a abordagem serial foi considerada mais apropriada à implementação do algoritmo.

De acordo com Falkernauer and Bouffouix (1991), para o problema de programação, o esquema de representação mais apropriado é aquele apresentado na forma de um string simples, expressando a sucessão de operações como elas acontecem no espaço de tempo. Este tipo de representação reduz o problema de programação à busca da melhor permutação da operação a ser realizada.

Particularmente, para o problema de programação de projetos, se cada cromossomo é representado como um vetor que apresenta o resultado ao usuário como uma sequência de atividades a serem executadas no qual, a ordem relativa na qual elas aparecem determinam a prioridade de realização, então um projeto de n-atividades pode ser representado como:

Início

Atividade 1

Atividade 2

....

Atividade n

Fim

Onde os valores, representados em cada uma das celas, são os próprios códigos das atividades, como aparecem no diagrama de precedências do projeto. Na implementação computacional do modelo, por facilidade de manuseio, estes códigos são representados por números inteiros.

É obvio que a estrutura proposta deve representar sequências legais. Para o problema de programação de projetos com restrição de recursos, uma sequência legal ou programação viável, é aquela que satisfaz:

1. a unitaridade, isto é, cada atividade aparece uma única vez no vetor solução, e
2. a integridade das relações de precedência entre tarefas.

Neste aspecto, a programação de projetos é comprovadamente difícil de representar, devido, principalmente, a manutenção da integridade nas relações de precedência.

A figura 3.5 apresenta o diagrama de precedência para um dado projeto. Cabe destacar que a implementação do modelo proposto, exige que todos os projetos a serem tratados possuam uma única atividade de início e uma de fim. Se houver mais de uma atividade inicial ou final, deverá ser adicionada um atividade artificial (dummy) no início ou no final do projeto, onde ela for requerida. Atividades artificiais, são atividades que não consomem recursos nem tempo, tendo a função única de auxiliar à construção das relações de precedência.

A figura 3.6 mostra a solução A que representa uma programação legal para o projeto ilustrado na figura 3.5 Da mesma forma, uma programação inviável é ilustrada pela solução B, onde a relação de precedência é quebrada uma vez, com a atividade 2 sendo programada para ser executada após a sua imediata sucessora 5.

Como cada sub-lista contém os vários modos com que uma atividade pode ser realizada, então, o comprimento de cada uma delas é igual ao número de modos de execução para a atividade considerada.

Por outro lado, já que é pressuposto que cada atividade é executada empregando um, e somente um único modo, logo, cada sub-lista é considerada como sendo uma string formada por zeros e um único um. A posição na sub-lista representa o modo de execução associado à atividade, enquanto que o valor zero ou um indica se o modo associado ao valor foi atribuído para executar a atividade (valor um) ou não (valor zero). Por exemplo, se uma dada atividade pode ser executada empregando três combinações diferentes de recursos-durações, então, o tamanho da sub-lista é 3. Se o valor um aparece na segunda posição isto significa que a atividade será executada empregando o modo dois.

A figura 3.7 ilustra como o problema de programação de projetos para o caso de múltiplos modos é representado na implementação do modelo desenvolvido. A lista representa as atividades de um projeto e a ordem em que a atividade aparece na lista representa a ordem da sua execução, empregando para tanto, o modo representado pelo número um.

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

O modelo implementado, baseado nos conceitos dos Algoritmos Genéticos, torna indispensável definir um único e apropriado mecanismo que permita a geração aleatória da população inicial. Esta população é composta de indivíduos, cada um deles representando uma solução viável ao problema em discussão.

O mecanismo para a geração de cada elemento da população é baseado na metodologia proposta por Jones (1984). Neste paradigma é introduzido uma pequena alteração de forma a acomodar o caso de execução de atividades com múltiplos modos.

A figura 3.8 mostra o diagrama de fluxo para o algoritmo de geração de soluções iniciais utilizados pelo modelo. A descrição de cada um dos passos envolvidos é detalhado através de um exemplo.

O algoritmo de Jones permite produzir soluções viáveis para o problema de programação de projetos da forma descrita a seguir.

Ao término da execução de uma atividade, a qualquer instante de tempo, é possível definir um conjunto de atividades cujas relações de precedências tenham sidos satisfeitas e, portanto, podem ser consideradas prontas ou elegíveis para a alocação de recursos.

O conjunto de atividades, a partir do qual é feita a escolha da próxima atividade a ser programada, é definido como sendo o vetor decisão.

A escolha de uma atividade pertencente ao vetor decisão é realizada aleatoriamente, assumindo-se que o vetor é dividido em celas. O limite superior para cada cela é dada por uma probabilidade, obtida pela divisão da unidade pelo número de atividades elegíveis. Um número fracionário entre 0 e 1, sorteado aleatoriamente, define a cela a ser escolhida, e por conseguinte, a atividade que será programada. A atividade sorteada é então, incorporada a um vetor denominado vetor solução, que representa uma solução viável para o projeto em consideração.

A seguir, todas as atividades sucessoras da atividade sorteada, cujas relações de precedência tenham sido cumpridas e que ainda não estejam no vetor decisão, são incorporadas a ele.

O procedimento é repetido sucessivamente até que todas as atividades tenham sido incorporadas, numa sequência arbitrária, ao vetor solução.

A ordem de aparecimento das atividades no vetor solução, estabelece uma prioridade implícita para a alocação dos recursos do projeto.

O algoritmo de Jones Modificado é executado de acordo aos seguintes passos:

Passo 1. Selecione a atividade inicial do projeto de construção.

Passo 2. Coloque a atividade inicial no vetor solução (VS) e coloque todas as suas atividades sucessoras no vetor decisão (VD). O número total de atividades no vetor decisão representa o número de celas em que ele é dividido.

Passo 3. Calcule o limite probabilístico de cada cela, dividindo 1 entre o número de celas e, começando pela primeira cela, adicionando para as celas subsequentes o valor calculado.

Passo 4. Usando um gerador de números aleatórios, sorteie um número entre 0 e 1 e selecione a atividade correspondente no vetor decisão.

Passo 5. Rotule a atividade selecionada aleatoriamente no passo 4 como CAND, que a identifica como candidata ao vetor solução.

Passo 6. Inclua CAND no Vetor Solução (VS).

Passo 7. Coloque todas as atividades sucessoras de CAND na lista de atividades candidatas CLISTA, de onde a atividade a ser incorporada no vetor decisão (VD) deve ser escolhida.

Passo 8. Selecione uma atividade de CLISTA. Rotule a atividade escolhida como ATUAL.

Passo 9. Verifique se todas as atividades precedentes de ATUAL já foram incorporadas ao Vetor Solução (VS). Se verdadeiro, então coloque ATUAL no Vetor Decisão (VD). Uma atividade somente pode ser incorporada ao Vetor Decisão, se todas as suas relações de precedência foram satisfeitas, isto é, se todas as suas atividades antecessoras já foram programadas.

Repita os passos 8 e 9 sucessivamente até que CLISTA fique vazia.

Passo 10. Para a atividade CAND, escolha aleatoriamente, um e somente um único modo, entre os diferentes modos de execução. Atribua ao modo selecionado o número 1 e faça os modos restantes iguais a zero. No caso da atividade inicial do projeto, o sorteio do modo de execução é efetuado diretamente no passo 1.

Passo 11. Retire CAND do Vetor Decisão (VD).

Repetir o procedimento sucessivamente do passo 3 até o passo 10, até que todas as atividades tenham sido selecionadas numa sequência arbitrária. Esta sequência representa uma solução viável para o problema de programação de projetos.

O procedimento é ilustrado usando o projeto cujo diagrama de precedências é mostrado na Figura 3.5 que, por questão de simplificação, é empregado considerando-se somente um único modo de execução.

Inicialmente, selecione a atividade 1 (Inicial) e coloque-a diretamente na Vetor Solução.

VS = [1].

Todas as atividades sucessoras de 1, são incorporadas ao Vetor Decisão, pois as suas relações de precedências são satisfeitas (Atividade 1 já está no Vetor Solução).

VD = [2, 3, 4].

Desta forma, a escolha da próxima atividade a ser incluída no Vetor Decisão será feita entre estas três atividades.

Para a escolha da próxima atividade, os limites de probabilidade de cada cela são determinados. Neste caso, os valores óbvios são: de 0 a 0.33, de 0.33 a 0.67, e de 0.67 a 1.0.

Digamos que o número fracionário (gerado entre 0 e 1) 0.75 foi sorteado. Isto determina que a atividade selecionada é a tarefa 4. A atividade sorteada é retirada de VD e colocada em VS.

VD = [2, 3].

VS = [1, 4].

Todas as atividades sucessoras de 4 são incorporadas na lista de atividades candidatas, CLISTA.

CLISTA = [7].

Particularmente, como CLISTA contém uma única atividade, a atividade de código número 7 é sorteada para ser incorporada ao Vetor Decisão (VD).

Desta forma, a escolha da próxima atividade para o Vetor Solução será feita entre as atividades 2,3 e 7.

VD = [2, 3, 7].

Este mesmo procedimento é repetido até que todas as atividades tenham sido colocadas no Vetor Solução.

Deve ser observado que a escolha de uma atividade do Vetor Decisão não determina a programação atual, mas estabelece a ordem de prioridade para a alocação de recursos para aquela atividade.

3.3.4 Avaliação das Soluções Geradas

Na abordagem quantitativa do problema da programação de projetos, a avaliação das soluções geradas pelo Algoritmo Genético permite quantificar a aptidão destas soluções. A função objetivo e a função de aptidão ("fitness function") são as formas tradicionais de avaliar a busca da solução ótima e de controlar os operadores genéticos.

Função Objetivo e Função "Fitness"

O problema de programação de projetos é um problema de otimização onde o objetivo final, no caso do modelo proposto, é a redução total da duração do projeto.

A função objetivo típica para este tipo de problema é definida como:

Min d_i CC (3.1)

Onde:

CC = Caminho Crítico

d_i = duração da atividade i (i = 1, 2, ... , n).

ou, alternativamente:

Min (x_n - x₁) (3.2)

Onde:

x_n = Última Data de Término da atividade final,

x₁ = Primeira Data de Início da atividade inicial.

A avaliação das soluções, geradas inicialmente pelo gerador das soluções da população inicial e, posteriormente, pela aplicação dos operadores do Algoritmo Genético, é simplesmente, a execução do cálculo da Primeira Data de Início (PDI) e Primeira Data de Término (PDT) para cada atividade.

Como já explicado em seções anteriores, a representação proposta para o problema é a heurística empregada na determinação da ordem de prioridades para a alocação dos recursos às atividades. Se a representação proposta para o problema é vista como uma fila de processamento, então, as atividades são selecionadas da fila de processamento em ordem de prioridade, começando pela primeira tarefa da fila. Quando a fila ficar vazia o processo de alocação termina.

A Primeira Data de Início (PDI) para uma atividade é determinada pela maior Primeira Data de Término (PDT) das suas atividades antecessoras, que dentro do modelo proposto, já foram programadas, tornando elegível a atividade em questão.

PDI = PDTmax + 1, (3.3)

PDT = PDI + duração - 1. (3.4)

Neste ponto, uma avaliação dos diferentes tipos de recursos solicitados pela atividade corrente, é feita em relação a todas as outras atividades já programadas, e que tenham influência na programação da tarefa em questão.

A Figura 3.9 apresenta a representação esquemática para o processo de alocação dos recursos às atividades e cálculo da duração do projeto.

No caso de alocação de múltiplos recursos, este é um processo iterativo e demorado. Imagine, por exemplo, que hoje um dado tipo de recurso não é crítico e que a atividade necessita, por força de restrição de um outro recurso, ser adiada até uma data onde o nível para o recurso com problemas seja suficiente. Nesta data, o recurso em questão poderá se tornar crítico, solicitando nova e similar avaliação. O processo só termina, quando todos os tipos de recursos envolvidos forem suficientes para atender a demanda de todas as atividades ativas para o intervalo de tempo em consideração.

Ao final deste processo de alocação, a Última Data de Término (UDT), que para a atividade final é igual à Primeira Data de Término (PDT), representa a duração total do projeto. Esta simplificação no cálculo da função objetivo será verdadeira somente, se for convencionado que a Primeira Data de Início da atividade inicial do projeto é o dia 1. Caso contrário, será necessário aplicar a fórmula 3.2 .

A função "fitness" ou função de aptidão ("fitness function)" nos Algoritmos Genéticos é uma medida da qualidade de uma solução para a função objetivo.

Portanto, no caso da função objetivo escolhida para o modelo, a função "fitness" terá uma correlação inversa com a duração do projeto. Isto quer dizer que as programações com durações grandes, terão menor aptidão de reprodução para a próxima geração.

Atualmente, a função de aptidão é um fator de escala, empregado para determinar a qualidade relativa dos elementos (programações) de uma população. A seleção dos elementos dependerá da amplitude da duração esperada e da taxa de mudança nos valores de aptidão.

A função de aptidão escolhida para a implementação do modelo é:

(3.5)

Onde, no paradigma aqui desenvolvido, x é a duração calculada para cada elemento (programação) da população atual.

O coeficiente C_max é escolhido como sendo o maior valor x da população atual.

Um fenômeno frequentemente observado é que a medida que o algoritmo é executado, a população converge para um conjunto de soluções muito similares ou iguais, entre os quais é difícil discriminar o mais apto se for usada uma função pouco apropriada. Foi observado que, devido ao grande número de combinações, muitas vezes no problema de programação de projetos, diferentes programações das atividades levam ao mesmo resultado para a função objetivo. A probabilidade de ocorrência desta situação fica mais evidente no caso de múltiplos modos.

Neste contexto, foi introduzido o conceito do nivelamento dos perfis finais dos diferentes tipos de recursos empregados como um procedimento que permite discriminar soluções igualmente aptas, ou soluções muito próximas da aptidão do melhor elemento.

Estes conceitos são discutidos com maior profundidade a seguir.

Medição da Importância dos Recursos

Desenvolver um procedimento, que leve em consideração a importância relativa dos diferentes tipos de recursos envolvidos num projeto, pode ser útil como um meio de obter valores mais próximos da realidade quando se mede a eficiência da utilização destes recursos.

Na implementação do modelo proposto, duas distintas aplicações são identificadas para um procedimento deste tipo. Em primeiro lugar, o procedimento é introduzido como um mecanismo que estabelece os diferentes níveis de importância para os perfis de recursos empregados, obtidos após a aplicação da estratégia de programação.

A segunda situação, onde o procedimento proposto é aplicado, está relacionada com a possibilidade de seleção de estratégias que levem a um mesmo valor para a função objetivo. Neste caso, o conceito do nivelamento de recursos é utilizado como regra de desempate. No contexto do paradigma proposto, esta premissa é generalizada para permitir decidir entre estratégias que possuam valores diferentes para a função objetivo.

Este procedimento proposto, associado com a abordagem de Algortimos Genéticos empregada para a otimização da função objetivo, é considerado como um meio útil para reduzir a flutuação no emprego dos recursos do projeto. Em outras palavras, o procedimento possibilita levar em consideração o problema de nivelamento de recursos, ao mesmo tempo que é procurada uma solução para o problema de otimização da duração de um projeto com restrição de recursos.

A situação acima exposta pode ser ilustrada da seguinte maneira:

Inicialmente, considere um projeto que emprega um único recurso R₁ na execução de cada atividade. Suponha que, a aplicação de duas estratégias de programação diferentes E₁ e E₂, levem a um mesmo resultado (t₁ = t₂). Suponha que a utilização do recurso para cada uma das estratégias seja representada por uma função f_i (f₁ e f₂).

A Figura 3.10 mostra a situação hipotética onde a estratégia E₁ possui uma utilização mais eficiente do recurso do que a estratégia E₂, i.e. f₁ > f₂ . Aplicando o conceito de nivelamento de recursos para esta situação, verifica-se que a estratégia E₁ é melhor do que E₂.

Suponha que as mesmas duas estratégias, E₁ e E₂, apresentem a mesma duração (t₁ = t₂) e gráficos de utilização dos recursos como os mostrados na Figura 3.11. A figura superior ilustra a situação onde, ainda que o gráfico (f₂) do recurso 2 não apresente grande variabilidade, não pode ser considerado como tendo a mesma influência (w₁ > w₂) do perfil (f₁) apresentado pelo recurso 1 na seleção desta alternativa (i.e. w₁f₁ > w₂ f₂). A situação oposta é ilustrada na parte inferior da figura.

Se assumir w₁ = w₂, então E₁ = E₂, levando a escolha de qualquer uma das alternativas. Entretanto se assumir w₁ > w₂, isto implica na escolha da estratégia E₂ que apresenta um melhor nivelamento para o recurso mais importante.

Fator Ponderado de Utilização dos Recursos

Para a implementação da abordagem proposta é criado o denominado Fator Ponderado de Utilização dos Recursos - FPUR definido como:

FPUR_k = Sw_i f_i, FPUR_k [0,1], k = 1,2,...,m (3.6)

Onde:

w_i = peso atribuído para a importância relativa do recurso do tipo i, Sw_i = 1;

f_i, = função que mede o índice de nivelamento para o recurso do tipo i, f_i, [0,1];

k = elemento (programação) da população atual.

A função que mede o índice de nivelamento final de cada recurso empregado pelo projeto é dado por:

(3.7)

onde:

V(X) = Variância dos recursos empregados.

Para calcular a Variância, teremos:

(3.8)

onde:

T = Duração do Projeto para a programação atual;

X _t = Soma da necessidade do recurso para todas as atividades do projeto para o período t ;

E(X_t) = Soma da necessidade do recurso para todas as atividades do projeto para o período t, dividido pela Duração do Projeto para a programação atual.

A função de nivelamento de recursos, tem como propriedade:

(3.9)

(3.10)

As relações 3.9 e 3.10 simplesmente significam que, se um recurso for eficientemente empregado, o padrão final dos recursos empregados terá um comportamento constante, tendendo no limite a ficar totalmente plano. Analogamente, quando o recurso tiver uma utilização ineficiente, ou seja, com uma variância muito grande, este comportamento será refletido por um valor pequeno na função, tendendo para zero no limite.

Este comportamento na função de nivelamento do recurso é refletido, finalmente, no valor fornecido pelo Fator Ponderado de Utilização dos Recursos.

Intuitivamente é evidente, para o caso extremo, que se todos os tipos de recursos são eficientemente empregados, f_i = 1, teremos:

FPUR = Sw_i = 1. (3.11)

ou, se todos os recursos são pobremente utilizados, no caso se f_i = 0, teremos:

FPUR = 0, (3.12)

Como mostrado no capítulo anterior, a abordagem de Algoritmos Genéticos usa uma probabilidade controlada para aceitar os elementos da população atual que irão gerar a próxima população.

Neste contexto, o modelo implementado propõe o emprego do Fator Ponderado de Utilização dos Recursos (FPRU) como um peso que incrementa ou reduz a probabilidade de aceitação de uma dada solução.

Esta premissa é aprofundada na seção a seguir.

Mudança na Função de Aptidão

O procedimento acima exposto funciona, indiretamente, como um processo de mudança de escala na aptidão, controlando o número de descendentes, evitando que elementos de alta qualidade se reproduzam excessivamente.

Introduzindo o nivelamento de recursos, a Função de Aptidão (3.5) escolhida para a implementação do modelo, foi modificada para:

(3.13)

Onde FPUR é o Fator Ponderado de Utilização dos Recursos com valores no intervalo [0, 1].

Para ilustrar este conceito, imagine uma população de 5 elementos (soluções) com as características mostradas na tabela 3.3.

Aplicando a Função de Aptidão originalmente proposta (3.5), os elementos possuiriam as aptidões e probabilidades de reprodução mostradas na tabela 3.4.

Entretanto, se o Fator Ponderado de Utilização dos Recursos (FPUR) é introduzido, os valores de aptidão são modificados, levando a uma diferenciação na qualidade das soluções produzidas. No caso da presente ilustração, a probabilidade de reprodução para elementos igualmente aptos desde o ponto de vista da função objetivo, é menor para soluções com uma pobre utilização de recursos, como mostrado na Tabela 3.5 (comparar as soluções 1,2 e 3, 4).

O procedimento permite encurtar a distância entre a probabilidade de reprodução de elementos de aptidão inferior, porém, com um uso eficiente dos recursos, dos elementos de aptidão superior e com ineficiente emprego destes recursos.

Por exemplo, no caso das soluções 2 e 3, embora a situação ilustrada na Tabela 3.4 apresente a solução 2 com uma probabilidade bem maior (devido ao valor da função objetivo) do que a solução 3, isto não é considerado como um fator definitivo de decisão se o conceito de nivelamentos de recursos é aplicado. Neste caso, o FPUR é aplicado como um fator de redução da probabilidade de aceitação da solução 2 e de aumento da probabilidade de reprodução da solução 3, como mostrado na Tabela 3.5.

Seguindo esta abordagem, o problema puro de Programação de Projetos com Restrição de Recursos, pode ser considerado como um caso especial (fazendo FPUR = 1 em 3.13) do problema de Programação de Projetos com Restrição e Nivelamento de Recursos.

Desta forma, com a introdução deste conceito espera-se obter ao final do procedimento, a sobrevivência de elementos com solução ótima (global ou local) para a função objetivo, e que possuam perfis finais de utilização de recursos de certa forma nivelados.

3.3.5 Operadores Genéticos do Modelo

Como já salientado anteriormente, do ponto de vista da Pesquisa Operacional, a idéia de um Algoritmo Genético pode ser entendida como a exploração inteligente de uma busca aleatória.

Os Algoritmos Genéticos combinam as noções de evolução e sobrevivência, busca aleatória e estruturada e, geração e avaliação paralela dos nós no espaço de busca.

Como já visto no Capítulo 2, a geração de novos nós de busca de uma geração para outra é realizada usando três operadores básicos clássicos: reprodução, cruzamento e mutação.

Reprodução

A reprodução é um processo de seleção empregado para determinar qual elemento da população atual sobrevirá para gerar novos indivíduos para a próxima geração.

Na implementação do modelo proposto, foi utilizada a técnica de reprodução denominada elitismo. O emprego desta técnica assegura que um certo número dos melhores indivíduos da população atual farão parte da nova população.

A função primordial da reprodução elitista é a preservação do melhor material genético presente na população, assegurando muitas vezes a melhoria do desempenho do algoritmo. A segunda função é de servir como um mecanismo de registro ou armazenamento das melhores soluções encontradas ao longo do processo.

A operação de reprodução é uma implementação algarítmica da Teoria de Sobrevivência de Darwin. Através desta teoria sabe-se que a tendência de sobrevivência dos indivíduos mais aptos de uma geração para outra é controlada por alguma regra. Esta é uma regra probabilistica. Ou seja, nem todos os indivíduos mais aptos são automaticamente escolhidos para formar a próxima geração.

No modelo proposto, a geração dos indivíduos da próxima população é feita pelo cruzamento par a par, de elementos da população atual selecionados probabilisticamente.

Para a implementação computacional da seleção dos pais, optou-se pelo processo de seleção conhecido como roleta. Neste procedimento, cada setor da roleta representa a aptidão de um individuo da população. A área de uma casa da roleta é proporcional ao valor da aptidão do elemento: quanto maior a aptidão, maior a área que a casa ocupa proporcionalmente às outras casas.

A estrutura básica para a implementação da seleção dos pais usando o mecanismo da roleta é resumida nos seguintes passos:

1. Some os valores de aptidão de todos os membros da população atual;
2. Gere as probabilidades de reprodução de cada individuo da população. Divida a soma calculada no passo 1 pelo valor de aptidão de cada elemento, normalizando desta forma, a área total da roleta.
3. Gere n, um número aleatório entre 0 e 1;
4. Retorne o primeiro membro da população cuja probabilidade de reprodução, somada às probabilidades dos membros precedentes (na população), seja maior ou igual a n.

O mecanismo foi escolhido por ser esta a forma mais simples, eficiente e direta de escolher os pais dos elementos da futura geração, porém, com certeza não é a única maneira, nem a mais rápida.

Cruzamento

O operador de cruzamento pode ser considerado como o operador mais importante na abordagem de algoritmos genéticos. O cruzamento é uma operação complementar da operação de reprodução. A simples cópia de estruturas velhas sem nenhuma mudança, nunca levará a nada novo. É aqui que entra o papel do cruzamento.

O cruzamento é o operador de casamento que permite a produção de novos indivíduos através da troca parcial de informação entre pares de indivíduos. O cruzamento somente acontece com alguma probabilidade P_c , denominada probabilidade de cruzamento ou taxa de cruzamento.

Como já salientado no Capítulo 2, duas características são essenciais nos algoritmos genéticos no processo de otimização de uma função. A primeira, é a capacidade de convergir para um ótimo (local ou global) após ter localizado a região contendo este ótimo. A segunda característica é a capacidade de explorar novas regiões do espaço de soluções na busca do ótimo global. O equilíbrio entre estas características é ditado pelos valores atribuídos à P_c e à probabilidade de mutação P_m , e pelo tipo de cruzamento empregado.

A escolha dos valores de P_c e P_m para o modelo proposto foi baseada nos valores típicos sugeridos na literatura. É bem estabelecido na literatura de algoritmos genéticos que valores moderadamente grandes para P_c (0.5 < P_c < 1), e valores pequenos para P_m (0.001 < P_m < 0.005) são essenciais para um desempenho satisfatório do algoritmo genético. Valores moderadamente grandes de P_c promovem a recombinação extensiva dos esquemas. Valores pequenos para P_m são necessários para prevenir o desordenamento de uma solução.

Para o modelo desenvolvido, dentre os operadores clássicos de cruzamento investigados, o operador CX ou operador cíclico foi o que apresentou melhor desempenho. O operador CX realiza as recombinações no sentido em que cada gene dos descendentes vem da posição correspondente de qualquer um dos pais.

Para ilustrar como o operador CX funciona, usaremos duas soluções (S₁ e S₂) quaisquer para o projeto mostrado da Figura 3.5.

S₁ 1 - 2 - 5 - 4 - 7 - 8 - 10 - 3 - 6 - 9 - 11 e

S₂ 1 - 3 - 2 - 5 - 8 - 6 - 9 - 4 - 7 - 10 - 11

Neste tipo de cruzamento não ha necessidade de escolher pontos de cruzamento, como os usados no operador de Goldberg - PMX ou no operador de ordem - OX.

Originalmente este procedimento é iniciado da primeira posição mais a esquerda. Na implementação do operador para a representação utilizada no problema em pauta, as duas posições extremas são omitidas, já que representam as datas de início e término do projeto.

Neste sentido, o procedimento é iniciado a partir da segunda posição mais a esquerda, escolhendo um gene (atividade) do primeiro pai (S₁).

S₁^' 1 - 2 - ? - ? - ? - ? - ? - ? - ? - ? - ?

Já que por este operador cada gene vem da mesma localização de um dos pais, a escolha da atividade 2 do pai 1 significa que a atividade 3 da oitava posição deve ser escolhida, porque 3 ocupa a segunda posição de S₂ (segundo pai).

S₁^' 1 - 2 - ? - ? - ? - ? - ? - 3 - ? - ? - ?

Esta seleção implica que a atividade 4 seja escolhida de S_1,

S₁^' 1 - 2 - ? - 4 - ? - ? - ? - 3 - ? - ? - ?

que por sua vez leva a escolher a atividade 5 de S₁, porque 5 está na quarta posição de S₂.

S₁^' 1 - 2 - 5 - 4 - ? - ? - ? - 3 - ? - ? - ?

Neste ponto, se continuar com o processo, a escolha da atividade 5 significa ter que selecionar a atividade 2 de S₁. Entretanto, isto não é possível porque 2 já foi selecionado como o segundo gene da solução.

A posição destes genes é dita de formar um ciclo que, eventualmente, retorna ao primeiro gene selecionado. O procedimento para.

Para completar a operação, os espaços vazios são preenchidos com os genes do segundo pai S₂ (mostrados em algarismos itálicos):

S₁^' 1 - 2 - 5 - 4 - 8 - 6 - 9 - 3 - 7 - 10 - 11

O segundo filho S₂^' é obtido realizando o cruzamento complementar:

S₂^' 1 - 3 - 2 - 5 - 7 - 8 - 10 - 4 - 6 - 9 - 11

Observando as soluções produzidas, verifica-se que não são soluções legais, pois relações de precedência foram quebradas em S₁ e S₂:

S₁^' 1 - 2 - 5 - 4 - 8 - 6 - 9 - 3 - 7 - 10 - 11

S₂^' 1 - 3 - 2 - 5 - 7 - 8 - 10 - 4 - 6 - 9 - 11

No modelo implementado, quando um problema deste tipo ocorre, ele é resolvido hibridizando o operador CX, introduzindo a operação de inversão.

Esta operação é discutida mais amplamente na seguinte seção.

Inversão

O papel desempenhado pela operação de inversão, no caso do paradigma proposto, é de permitir a recomposição das solução ilegais eventualmente produzidas na operação de cruzamento.

A operação de inversão proposta é um procedimento que envolve duas ações distintas: troca de posições e movida, sempre realizadas com pares de genes (atividades).

Inicialmente, o procedimento determina a posição da primeira atividade em conflito. A seguir, uma segunda atividade é selecionada. Esta segunda atividade, ou é a última antecessora, ou é a primeira sucessora da atividade considerada, dependendo se a relação de precedência foi quebrada a esquerda ou a direita respectivamente da atividade em questão.

Neste ponto, uma das seguintes ações é executada:

Troca de posições: ocorre quando a posição que ocupa a primeira atividade passa a ser ocupada pela segunda atividade e vice-versa. Para realizar esta operação é necessário que nenhuma relação de precedência da segunda atividade seja quebrada. Isto quer dizer que não pode haver atividades, antecessoras ou sucessoras da atividade em questão, entre a posição atual e a posição destino (posição ocupada pela primeira atividade).

Movida: acontece quando existe algum impedimento de precedência para realizar uma troca de posições. Neste caso, a primeira atividade é deslocada da posição atual para a posição ocupada pela segunda atividade ou vice-versa. A seguir, todas as atividades localizadas entre as duas posições são movidas uma posição para frente ou para atrás.

O procedimento é repetido até que todas as relações de precedência para todas as atividades sejam recompostas.

No caso das soluções S₁^' e S₂^', em ambas situações teremos o caso da execução de uma movida para gerar soluções viáveis:

S₁^' 1 - 2 - 5 - 4 - 8 - 3 - 6 - 9 - 7 - 10 - 11

S₂^' 1 - 3 - 2 - 5 - 4 - 7 - 8 - 10 - 6 - 9 - 11

Mutação

O operador de mutação é empregado com a finalidade de mudar parte da solução para criar uma nova.

O operador de mutação clássico, ou seja, a modificação aleatória pura e simples de um gene, não é aplicável ao problema aqui tratado, devido, principalmente, à destruição das relações de precedência.

No modelo proposto, o operador de mutação implementado segue basicamente o mesmo procedimento usado na inversão, diferenciado por dois aspectos. A primeira diferença reside na probabilidade de mutação P_m que controla a frequência da aplicação do operador.

A segunda diferença está no procedimento empregado para escolher as atividades a serem mudadas. O esquema de perturbação é definido da seguinte maneira:

Dada uma solução viável na população atual, é gerado um número aleatório, a, entre 0 e N, onde N é o número de atividades do projeto. Este número representa a posição da atividade i a ser mudada. A seguir, um segundo número aleatório, b, é sorteado entre LI e LS. LI representa a posição ocupada pela última antecessora da atividade i e, similarmente, LS representa a posição da primeira sucessora de i, enquanto que b designa a nova posição que a atividade i passará a ocupar.

Neste ponto, as mesmas duas ações executadas na operação de inversão se aplicam, ou seja, a troca de posições ou a movida.

3.4 Implementação Computacional do Modelo

O Modelo Evolutivo Para a Programação de Projetos proposto, implementado a nível de protótipo para testes, utiliza a técnica de programação orientada para objetos - OOP (OOP = Object-Oriented Programming).

A programação orientada para objetos, tem se mostrado superior em muitos aspectos às abordagens tradicionais usadas para modelar sistemas mais complicados. Uma das mais importantes vantagens da OOP é a de facilitar uma direta e natural correspondência entre o mundo e a sua modelagem. Especificamente na área do gerenciamento de projetos, a filosofia orientada para objetos tem sido comprovadamente de grande ajuda na administração da complexidade dos problemas e tem ganho vários defensores para a representação da engenharia de conhecimento no planejamento e programação da construção (Mosheli, 1993a, 1993b).

A programação orientada para objetos centra a sua base conceitual em quatro principais conceitos: abstração, encapsulamento, herança e polimorfismo.

A abstração permite delinear as características essenciais das entidades envolvidas na definição de um problema. Estas entidades são denominadas de objetos. Na programação orientada para objetos, um objeto é uma entidade abstrata que incorpora as características de um objeto do mundo real. Por exemplo, no presente estudo, distintas características de um projeto, como as atividades e os recursos são representadas como objetos.

O encapsulamento é considerado o conceito central da OOP. O encapsulamento representa a união e o ocultamento de dados ou informações e procedimentos ou métodos dos objetos em estruturas denominadas classes. Os dados e os procedimentos descrevem as características e o comportamento de cada objeto.

A herança permite a organização das abstrações em classes de hierarquias nas quais, cada classe tem uma ou mais superclasses imediatas e cada superclasse pode ter várias subclasses imediatas. A herança é provavelmente o conceito que fornece maior poder ao conceito de classes. O emprego desta filosofia fornece grande flexibilidade a baixo custo - em termos de codificação, evitando principalmente a duplicação, limitação ou eliminação e, finalmente, a expansão ou melhora das características da(s) classe(s) ascendente(s).

Por exemplo, no programa desenvolvido, a função objetivo do algoritmo genético é representado por um objeto denominado CPM. Este objeto herda características dos objetos atividades e recursos e adiciona procedimentos próprios que permitem o cálculo da duração do projeto.

Polimorfismo é uma palavra formada por dois termos gregos poly (muitos), e morphos (formas) significando múltiplas formas. O polimorfismo simplesmente descreve a capacidade da codificação da programação orientada para objetos de se comportar diferentemente, dependendo da situação encontrada no tempo de processamento.

O polimorfismo não é uma característica muito associada aos objetos quanto o é aos procedimentos que compõem o objeto. Embora o polimorfismo seja implementado através da arquitetura da classe, somente os procedimentos ou funções membros da classe podem ser polimorfas.

Para ilustrar este conceito usaremos a explanação usada por Faison (1994).

Segundo Faison, este tipo de implementação é similar ao emprego dos verbos na linguagem natural, que é equivalente as funções membros de uma classe. Considere as várias formas que um objeto pode ser empregado na vida real. Considere o verbo mover, o qual denota somente uma ação genérica, porque não é sabido qual o objeto que atuará sobre ele. Por exemplo, mover um lápis requer ações completamente diferentes do que mover um "container", embora os dois conceitos sejam similares. O verbo mover pode ser associado com um conjunto particular de ações somente após conhecer o objeto que atua sobre ele.

Na implementação computacional do modelo, foi utilizado como linguagem de programação o C++ da Borland Inc. (Borland, 1993).

O C++ foi projetado para ser uma melhoria e uma extensão mais poderosa da linguagem C. A extensão mais notável foi a construção de classe. As classes são estruturas que permitem criar tipos definidos pelo usuário, que não somente representam dados, mas também as operações a serem executadas em tais dados (Flamig, 1992). As variáveis criadas pelas classes são chamadas objetos e é o que classifica o C++ como uma linguagem de programação orientada para objetos.

As razões para a escolha do C++ são fundamentadas na colocação do Faison. Segundo ele, o C++ representa um excelente balanceamento entre o poder de expressão, velocidade de execução, e tamanho de código. Mais ainda, o C++ da Borland, utiliza o Ambiente de Desenvolvimento Integrado Borland C++ - IDE (IDE = Integrated Development Environment) que permite a conexão automática das quatro fases envolvidas num ciclo de desenvolvimento de um programa: edição, compilação, "linkagem", e execução, aumentando a velocidade deste ciclo dramaticamente.

3.5 Planejamento dos Experimentos

De forma a explorar o desempenho do modelo proposto, o estudo do comportamento do algoritmo foi dividido em duas fases: fase de testes preliminares e fase de testes finais.

A etapa de testes preliminares oferece a oportunidade de determinar o desempenho relativo dos diversos parâmetros do algoritmo, fase às diferentes características dos problemas considerados. Neste estágio, uma execução piloto do modelo é realizada com a finalidade de ajustar os valores dos diferentes parâmetros em relação aos seus valores pré-estabelecidos.

Na fase de testes finais o comportamento e desempenho do modelo, via busca exaustiva, é avaliado por comparação direta, utilizando problemas disponíveis na literatura para os quais existem resultados registrados da aplicação de outras heurísticas.

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

É bem sabido que os parâmetros que controlam um algoritmo genético podem ter um impacto significativo no seu desempenho e que, muitas vezes, são singulares para cada problema abordado. Os três operadores definidos no algoritmo genético: reprodução, crossover e mutação, determinam os três parâmetros mais importantes para os quais devem ser atribuídos valores. Estes são:

1. Tamanho da população,
2. Probabilidade de cruzamento, e
3. Probabilidade de mutação.

Três outros parâmetros complementares cujos valores devem ser determinados são: número de gerações, taxa de elitismo e probabilidade de mudança de modo.

A determinação dos valores apropriados, ou ajuste fino, dos parâmetros do algoritmo genético é um processo de tentativa e erro, entediante e sem regras formais definidas para a sua realização.

Este processo de tentativa e erro é, ele mesmo, de natureza combinatorial. O objetivo do presente estudo não é determinar a influência destes parâmetros na busca genética, nem fazer um estudo empírico sobre o assunto e sim, demonstrar a viabilidade de utilizar uma abordagem deste tipo para o problema em pauta. Neste sentido, a determinação dos valores dos parâmetros a serem usados na implementação do modelo limitou-se ao ajuste de valores consagrados na literatura especializada.

Vários estudos, como os de De Jong (1975), Grefenstette (1986), Schaffer et al. (1989), Davis (1989), Goldberg (1989), Jog et al. (1989), Smith et al. (1993), Srinivas e Patnaik 1994), Chan e Tansri (1994) entre outros, determinam que os seguintes valores podem ser apropriados:

1. Tamanho da população: de 30 à 200,
2. Probabilidade de cruzamento: de 0.5 à 1.0,
3. Probabilidade de mutação: de 0.001 à 0.005,

A combinação do número de gerações e o tamanho da população determinam o número máximo de soluções tentadas dentro do espaço total de soluções viáveis. A determinação do tamanho do espaço de soluções para o problema de programação de tarefas com restrição de recursos, por si só, já é um problema que envolve a análise matemática do número de sequências possíveis e de explosão combinatorial.

Para ilustrar este conceito será usado o exemplo, extraído de Elmaghraby e Herroelen (1980) para o caso do problema clássico de 1-máquina, n-tarefas, descrito a seguir.

Seja (J, R) uma rede de N nós, onde J é o conjunto de tarefas e R representa as relações de precedência, a qual pode ser particionada em m redes paralelas não relacionadas (J₁, R₁), (J₂, R₂), ..., (J_m, R_m). Seja S_i o número de sequências possíveis para a sub rede (J_i, R_i), e que S_i,max represente o correspondente número máximo de sequências se R_i = 0.

Então o número total de sequências possíveis para a rede (J, R) é dada por:

(3.14)

Segundo estes autores, esta relação pode ser usada recursivamente para determinar o número de sequências possíveis em estruturas mais complexas.

Por exemplo, para a rede mostrada na Figura 3.12 representando cinco tarefas e um processador, tem-se S = 15.

Entretanto, Elmaghraby e Herroelen ressaltam que para o caso da programação de projetos com restrição de recursos, a análise é muito mais complicada e a fórmula (3.14) não é mais totalmente válida.

Por exemplo, para o problema mostrado na figura 3.13 envolvendo 3 atividades e dois recursos, a aplicação de 3.14, leva a S = 3. Porém, considerando os dois recursos, o número de sequências possíveis é S = 5.

O exemplo tem como objetivo, fundamentar a decisão de descartar a possibilidade de usar uma abordagem algumas vezes empregada na determinação do número total de iterações realizadas pelo algoritmo. A abordagem consiste em fixar o limite máximo para o espaço de soluções a serem testadas, como uma percentagem do espaço total de soluções.

Considerando a variabilidade das características de um projeto de construção em termos do número de atividades, número de tipos de recursos e ainda, número de modos de execução envolvidos, o cálculo de um número máximo de iterações a serem intentadas como percentual do espaço total, acreditamos não ser uma tarefa muito viável.

Por exemplo, se o problema fosse simplificado para o caso de 1 processador e n tarefas independentes, o número de sequências possíveis seria reduzido para o valor máximo de n!. Se considerar um problema com 9 tarefas e se for especificado que o espaço de soluções a serem intentadas não exceda 3% do espaço total de soluções viáveis, estes 3% de 9! representam, aproximadamente, 10.000 interações.

Cabe salientar entretanto, que se o espaço de busca for muito pequeno em relação ao tamanho do problema, o algoritmo genético irá convergir muito rapidamente para um sub-ótimo, dado o processamento insuficiente de esquemas. Por outro lado, se o espaço de soluções a serem intentadas é muito grande, o tempo de processamento computacional é demasiadamente grande para se obter uma melhora significante.

Neste sentido, optou-se por escolher uma combinação do número de gerações e do tamanho da população de modo que o número de iterações não exceda 8.000, que representa o emprego de uma população de 200 elementos e um número de gerações de 40. Estes são valores limites bastante observados na literatura especializada.

O número máximo de indivíduos mais aptos transferido para a próxima geração, que representa a taxa de elitismo, foi de 10% do tamanho da população, outro valor tradicionalmente empregado.

A probabilidade utilizada para a escolha dos modos de execução das atividades foi de 100%. Esta probabilidade determina se uma atividade (gene) de um individuo da próxima geração deve ou não mudar de modo. No presente estudo é assumido que sempre os descendentes podem trocar de modo. A escolha do modo de execução de cada atividade é outra seleção feita probabilisticamente. Dado que o número de modos por atividade, nos problemas testados, é pequeno, a probabilidade de escolher o mesmo modo é grande. Este conceito reforça a decisão de utilizar o valor 100% na probabilidade de mudança de modo.

3.5.2 Eficiência do Modelo

De maneira a gerar os diferentes conjuntos de problemas para a realização do experimento, as características mais importantes dos problemas empregados devem ser examinadas. Estas características afetam o desempenho dos paradigmas de programação e, portanto, devem fazer parte do planejamento dos testes.

Vários estudos, encontrados na literatura, tratam dos efeitos da estrutura dos problemas no desempenho de modelos para problemas de programação de projetos com limitação de recursos. Entre eles podem ser citados Patterson (1976), Elmaghraby e Herroelen (1980), Kurtulus e Narula (1985), Badiru (1988).

Davis (1973b), classifica as principais medidas das características, para o problema aqui tratado, em três classes gerais:

1. Medidas que caracterizam tamanho, forma e lógica (estrutura de precedências) da rede:

O tamanho da rede é representado pelo número total de nós da rede;

A forma da rede é especificada em termos:

- do comprimento da rede que representa o número máximo de nós consecutivos desde o início até o fim;

- da largura da rede especificada em termos do número máximo de nós em paralelo, e

- A relação de comprimento e largura.

A lógica da rede que representa a complexidade da rede;

2. Características de tempo da rede:

medidas calculadas antes da análise do caminho crítico:

- soma das durações de todas as atividades;

- duração média das atividades, e

- variância na duração das atividades.

medidas calculadas após a análise do caminho crítico:

- duração do caminho crítico;

- folga total;

- folga livre total;

- densidade = (soma da duração da atividade) / (soma da duração da atividade + folga livre total).

3. Características relativas aos recursos:

medidas da demanda dos recursos:

- demanda total média por atividade;

- demanda média por período;

- variância por período;

- nível máximo de recursos solicitados;

- número de tipos diferentes de recursos.

Relação entre demanda e disponibilidade:

- ociosidade de recursos;

- fator de utilização de recursos.

Maiores detalhes sobre as medidas acima relacionadas podem ser encontradas em Davis (1973).

Além das medidas já relacionadas, outra medida simples que pode ser considerada é o número de modos por atividade. De acordo com Patterson et al. (1990), a relação que existe entre a duração de uma atividade e o consumo de recursos em projetos multi-modos, faz o problema inerentemente mais difícil de ser resolvido.

De maneira similar, outra medida simples que pode influenciar a complexidade de um problema é certamente, o número de projetos executados em paralelo, especificamente quando o caso de múltiplos projetos é considerado.

Das medidas acima descritas, aquelas que representam o tamanho e a complexidade da rede, a duração do caminho crítico sem restrição de recursos, o número de diferentes tipos de recursos e o número de modos por atividade foram empregadas com propósitos comparativos no planejamento do experimento.

Uma das medidas mais importantes e polêmicas é a que representa a complexidade das redes. Parece claro que é necessário medir a complexidade das redes de atividades de forma a estimar os requisitos computacionais e/ou validar procedimentos heurísticos alternativos. Evidentemente, a escolha entre dois algoritmos propostos, ou a determinação da eficiência de um algoritmo particular, será bastante facilitado se existir uma medida (robusta) da complexidade do problema (Elmaghraby e Herroelen, 1980).

A tabela 3.6 apresenta algumas medidas propostas na literatura para a medir a complexidade de redes em problemas de programação de projetos, linha de balanço e programação da produção.

Entretanto, Elmaghraby e Herroelen ressaltam que para o problema de programação de projetos sob restrição de recursos, não se conhece uma medida exata (robusta) que represente a complexidade deste tipo de problema. Segundo eles, parece evidente que a estrutura da rede não é suficiente para refletir a dificuldade encontrada na resolução de tais problemas.

Em particular, a disponibilidade de recursos deve ter um papel importante, e conjectura-se que a relação entre a complexidade da rede e a disponibilidade de recursos deve ser como a ilustrada na Figura 3.14.

Por exemplo, se os recursos estão disponíveis em pequenas quantidades, haverá relativamente pequeno grau de liberdade para programar as atividades, e portanto a complexidade será pequena. Se, por outro lado, os recursos são fartos, as atividades podem ser facilmente programadas em paralelo, levando a uma complexidade igual a zero, para o caso em que a duração obtida seja igual ao comprimento do caminho crítico. O problema é obter a forma exata que a curva da complexidade assume na região entre estes dois pontos extremos. Segundo Elmaghraby e Herroelen, não se conhece nenhuma medida que permita resolver este problema.

Neste contexto, na implementação do modelo proposto, optou-se pela proposta de Badiru (1988), que define a medida de complexidade de um projeto como:

(3.15)

onde,

= complexidade do projeto,

L = número de atividades do projeto,

t_i = duração da atividade i,

R = número de tipos de recursos,

x_ij = quantidade do recurso do tipo j solicitado pela atividade i,

Z_j = quantidade máxima disponível para o recurso do tipo j,

p = número máximo de atividades predecessoras na rede,

d = duração do projeto sem restrição de recursos.

Segundo este autor, qualquer medida para a complexidade de um projeto deveria ser usada como uma medida relativa de comparação mais do que um indicativo absoluto da dificuldade envolvida na programação de um dado projeto.

Para testar uma metodologia, é apropriado comparar o modelo que é proposto contra outras abordagens desenvolvidas para o mesmo problema. Existem hoje, literalmente, centenas de heurísticas diferentes para o problema de programação de projetos sob restrição de recursos e um único modo de execução. Poucas referências são encontradas para o caso de múltiplos modos e, infelizmente, não se tem referências de algoritmos que, explicitamente, reconheça a eficiência da utilização de recursos ao mesmo tempo que a duração do projeto é otimizada. Portanto, o experimento é planejado de forma tal que o caso de um único modo sirva como referencial de comparação do modelo.

Cabe no entanto destacar, que o objetivo final dos testes é demonstrar que a abordagem de algoritmos genéticos pode ser usada combinada com um apropriado mecanismo de nivelamento de recursos, para obter eventualmente (se houver), uma solução ótima, melhorada sob este critério.

Neste sentido, um total de 25 projetos diferentes foram utilizados para testar a eficiência do modelo proposto. Nove projetos foram selecionados de um conjunto de 18 redes, gentilmente fornecidas pelo Professor Raymond Li do Department of Bussiness Systems of the Monash University, Clayton, Austrália, usados no trabalho de Li e Willis (1992). Os outros 16 projetos foram selecionados de um conjunto de 30 redes, fornecidas graciosamente pelo Professor Adedeji B. Badiru, diretor do Expert Systems Laboratory, School of Industrial Engineeering, University of Oklahoma, Norman OK, USA.

Os projetos não utilizados foram rejeitados por empregarem um único recurso para a sua execução, ou por serem muito pequenos (poucas atividades).

Estes projetos foram escolhidos porque, ou a solução ótima é conhecida, ou se tem uma referência do melhor valor fornecido por uma heurística alternativa.

No trabalho de Badiru (1988) o conjunto de 30 projetos foi empregado para comparar o desempenho de 13 heurísticas. Por outro lado, o segundo conjunto de 18 projetos foi empregado no trabalho de Li e Willis onde, o modelo por eles proposto, é confrontado contra 8 procedimentos heurísticos alternativos. Sete destas 8 heurísticas são diferentes das 13 heurísticas testadas por Badiru.

Entretanto, todos estes projetos consideram um único modo de execução para as atividades. Dado que o modelo proposto trata o modo único como um caso especial do problema de múltiplos modos, as redes tiveram que ser adaptadas para poder realizar a análise da efetividade do modelo para este caso mais geral.

As principais adaptações realizadas foram:

• Modos M de execução adicionais para as atividades foram aleatoriamente gerados de acordo com 1 M 3;
• Nesta fase de implementação do modelo, os pesos para os diferentes tipos de recursos foram diretamente atribuídos pelo decisor ().

Em geral, a intenção de gerar no máximo três modos de execução para cada atividade vêm da idéia de que cada atividade possa ser executada de três formas diferentes: usando o modo de menor duração, o mais provável ou o de maior duração. Por outro lado, os modos foram gerados de tal maneira que os limites dos recursos originalmente impostos aos projetos sejam mantidos inalterados.

O modo de execução original de cada um dos projetos, foi selecionado como sendo o de menor duração. O objetivo está na intenção de realizar uma comparação do resultado obtido pelo modelo para o caso de modo único com o resultado obtido introduzindo múltiplos modos.

Tentar-se-á com isto mostrar que a abordagem proposta pode ser útil também para tratar o problema de compressão de projetos. Este problema tem como premissa básica, similarmente à questão do nivelamento, a não limitação dos recursos empregados. Deverá ser mostrado, na prática, que é possível empregar a abordagem de múltiplos modos para reduzir a duração de um projeto com limitação de recursos.

As abordagens tradicionais para tratar o problema de compressão de projetos fundamentam-se na redução da duração das atividades com o objetivo de reduzir a duração total do projeto. Estes processos usam uma estimativa da variável tempo-custo para cada atividade para determinar qual duração a ser usada de modo a minimizar economicamente a duração do projeto. Estas premissas são válidas quando os recursos são considerados ilimitados.

O problema de compressão de projetos com restrição de recursos para o caso de modo único é tratado em Deckro e Hebert (1989). Entretanto, no presente trabalho é proposto usar múltiplos modos como abordagem ao problema de compressão. Sob condições de restrição de recursos, a redução da duração de uma atividade não sempre levará a uma redução da duração total do projeto. Obviamente, executar uma atividade com a menor duração viável parece ser a escolha mais apropriada se o desejo é minimizar a duração do projeto. Entretanto, esta regra pode ter também um efeito oposto. Executar uma atividade com menor duração possível requer um alto consumo de recursos, isto pode forçar a retardar atividades que poderiam ser executadas em paralelo. Consequentemente, prolongaria a duração total do projeto.

Neste sentido, para mostrar este conceito, o modelo é executado assumindo que o caso de um único modo representa a menor duração economicamente viável. O resultado obtido nesta execução é comparado com o resultado obtido considerando outras combinações de custo-duração.

Para realizar todos os propósitos acima delineados, foi planejado a execução de dois conjuntos de teste:

1. Conjunto 1: projetos com atividades executadas em uma única forma (modo) predefinida, levando em consideração o nivelamento de recursos e,

1. Conjunto 2: projetos onde cada atividade pode ser executada de um e somente um único modo, selecionado dentre os M modos, considerando a eficiência na utilização dos recursos.
   

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

O principal critério de avaliação utilizado foi a percentagem média acima ou abaixo do resultado da melhor heurística alternativa reportada.

Um segundo critério usado foi a percentagem média no atraso total do projeto. O atraso de um projeto é a diferença entre o resultado obtido e a duração alcançada na análise do caminho crítico sem restrição de recursos. Esta medida dá uma indicação do atraso introduzido como resultado da limitação na disponibilidade dos recursos e o resultado da heurística empregada. Para o caso de múltiplos modos, o comprimento do caminho crítico é calculado usando o modo de menor duração sem restrição de recursos.

Como terceiro critério, quando a solução ótima para o projeto é conhecida, foi utilizada a percentagem média acima do ótimo.

O critério tempo de processamento computacional foi empregado com limitações. Dado o fato de não ter havido a necessidade de implementar computacionalmente nenhuma heurística alternativa, não foi possível realizar uma comparação direta do tempo de processamento empregado. O tempo obtido pela aplicação do modelo, não pode ser comparado com o tempo reportado nos estudos usados como pontos de referência, dado a diversidade de fatores envolvidos numa programação (equipamento empregado, eficiência de código, maneira e vícios de programação, linguagem empregada, etc.). As heurísticas teriam que ter sido implementadas no mesmo ambiente em que se desenvolveu a pesquisa para que os tempos computacionais significassem alguma coisa. O principal objetivo deste critério é dar uma idéia do desempenho e limitação do modelo em diferentes condições de teste ou quanto ao tamanho dos problemas tratados.

Outros critérios usados foram: o número de vezes que o algoritmo foi capaz de encontrar a melhor solução, o número de vezes que foi a única heurística a obter a melhor solução, o número de vezes que encontrou a pior solução e o número de vezes que foi a única a obter a pior solução.