CAPÍTULO 2

REVISÃO DA LITERATURA

2.1 O Problema de Programação

O problema de programação pode ser definido, de um modo geral, como a alocação de recursos no tempo de forma a executar um conjunto de tarefas (Maccarthy and Liu, 1993). Este conceito é de vital importância para várias atividades industriais, particularmente nos ambientes de manufatura e de projetos de construção.

A maioria dos problemas de programação envolvem diversos fatores, tais como a priorização de tarefas, requisitos de data de realização, restrições de custos, precedência de operações, demanda, disponibilidade e capacidade de recursos, etc. Por tudo isto, é bem sabido que, frequentemente, muitos destes problemas não são facilmente resolvidos, e que a determinação da melhor solução requer a solução de um problema de otimização combinatorial. Qualquer abordagem que busque uma solução para um determinado problema de programação é, na realidade, uma forma diferente de formular e resolver um problema de otimização. Desta forma, diferentes problemas de programação levam, naturalmente, a modelos diferentes. Assim, uma grande variedade de resultados existe para um vasto conjunto de problemas.

Neste capítulo serão discutidos alguns dos problemas fundamentais da teoria de programação e alguns dos métodos fundamentais e/ou utilizados na sua resolução. Para os propósitos deste trabalho, não haverá necessidade de definições matematicamente rigorosas da maioria dos conceitos envolvidos no problema de programação, na otimização combinatorial e na teoria de complexidade.

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

O campo da teoria de programação é muito dinâmico e reconhecidamente, começou no início dos anos 50 com o trabalho pioneiro de Johnson (1954) sobre programação flowshop de duas máquinas. Este trabalho, junto com os trabalhos de Jackson e Smith, formam a base da teoria clássica do sequenciamento de máquinas. (MacCarthy e Liu, 1993). Desde então, a literatura tem crescido explosivamente. Vários livros tem sido publicados sobre o tema, entre os quais, Baker (1974), Coffman (1976), Lenstra (1977), Bellman et al. (1982), French (1986), Ibaraki (1987).

Por outro lado, as técnicas padrões da administração de projetos, como o PERT (Program Evaluation Review) e o CPM (Critical Path Method), vem sendo largamente empregadas desde meados da década de 50. Este métodos objetivam principalmente, minimizar a duração do projeto, assumindo que recursos de vários tipos necessários a sua execução, estão suficientemente disponíveis. Entretanto, na prática, estes recursos são disponíveis em quantidades limitadas. Como resultado, tem havido uma atenção crescente para o problema de alocação de recursos associado com o planejamento e a programação de projetos. Boas referências sobre estas técnicas básicas são Moodier and Phillips (1968), Lockyer, K.G. (1981); Callahan, M. T et al. (1992).

Embora os problemas de programação da produção e os problemas de programação de projetos tenham sido abordados através de modelos próprios, as similaridades conceituais entre ambos tem estimulado interesses de aplicabilidade recíproca dos métodos de solução (Davis, 1973).

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

A otimização combinatorial é um dos campos da programação matemática, cuja aplicação é encontrada numa ampla gama de áreas, tais como, engenharia, economia, ciências sociais e outras. Um problema de otimização combinatorial intenta encontrar uma solução, maximizando (ou minimizando) uma função objetivo definida sobre um conjunto combinatorial (ou discreto) (Ibaraki, 1988).

Segundo Ibaraki, um problema de otimização é geralmente definido como:

P: Maximizar (minimizar) f(x) (1.1)

sujeito a x S,

ou por conveniência de notação, como

(1.2)

ou

P: Max {f(x) | x S} (1.3)

onde S X denota a região viável no espaço X. Em outras palavras, S é o conjunto de soluções viáveis que satisfaz as restrições impostas. A função f:S R, onde R é o conjunto dos números reais, é chamada função objetivo. Uma solução viável xS é ótima se nenhuma outra solução viável satisfaz f(y)>f(x) para o caso de maximização ou (f(y)<f(x) no caso de minimização.

Um problema de otimização P é denominado de problema combinatorial de otimização se X e S são de alguma forma combinatoriais ou discretos. X e/ou S é combinatorial se eles são conjuntos discretos de elementos finitos ou elementos infinitos contáveis.

De acordo com Ibaraki, são considerados como conjuntos combinatoriais típicos o conjunto dos inteiros Z, o conjuntos dos n-vetores de inteiros Zn, o conjunto de políticas * geradas a partir de um conjunto finito de decisões , qualquer conjunto finito e seus sub-conjuntos tais como o conjunto de vetores 0-1 n-dimensional, contendo 2n elementos, o conjunto de permutações de n objetos, contendo n! elementos, e a família de todos os sub-conjuntos de um conjunto finito de n-objetos, contendo 2n elementos. Um grafo de vértices e arcos finitos é outro exemplo de um objeto combinatorial.

Entre os exemplos típicos de otimização, Ibaraki menciona os problemas relacionados com grafos e redes: maximum matching problem, maximum clique problem, maximum vertex packing problem, minimum vertex cover problem, mínima cobertura de arestas, problema do caminho mínimo, problema de fluxo máximo, expansão de árvore de custo mínimo, expansão de árvore de custo mínimo direcionado, problema de atribuição e o problema do caixeiro viajante; problemas relativos à seleção de sub-conjuntos ótimos de conjuntos finitos: cobertura de conjuntos, partição de conjuntos, set packing problem; e problemas relativos à localização ótima de n objetos, denominado problemas de localização: problema dos p-centros, problema das p-medianas e plant location problem.

Para Ibaraki, a Programação Linear (PL) e a Programação Inteira (PI) e seus casos especiais como a PI pura, problema PI misto, problema 0-1, problema 0-1 misto, problema da mochila, problema da mochila 0-1 e problema da mochila multi-restrito, são também importantes membros do conjunto dos problemas de otimização combinatorial.

De acordo com este autor, a programação ou a teoria de sequenciamento é outra fonte importante de problemas de otimização. Entre estes podem ser citados, o problema de sequenciamento de uma máquina, programação de máquinas em paralelo, programação de múltiplos processadores, bin packing problem, o problema da programação flow-shop e job-shop. A Figura 2.1 mostra a classificação dos problemas combinatoriais segundo Ibaraki.

Por outro lado, Müller-Merbach (1981), divide os problemas combinatoriais em três tipos puros: (1) problemas de atribuição, onde há dois (ou mais) conjuntos de objetos discretos com os quais pares de elementos unitários de cada conjunto devem ser formados, (2) o problema de sequenciamento, onde existe um conjunto de objetos discretos (ou um sub-conjunto deles) que tem que ser ordenado em sequência e, (3) o problema de seleção onde, dado um conjunto de objetos discretos um sub-conjunto deve ser escolhido.

Exemplos da segunda classe de problemas são: problema do caminho de mínimo custo, currency arbitrage problem, o problema do caixeiro viajante e o problema do carteiro chinês.

Nos problemas de seleção, na terceira classe de problemas combinatoriais, o número de exemplos é grande. Alguns deles são: problema de expansão de árvore, cobertura de aresta, cobertura de nó, cobertura de conjunto, problema da mochila, edge matching problem, node packing problem, set packing problem, partição de conjunto, entre outros.

De acordo com Müller-Merbach, alguns tipos padrões da maioria dos problemas combinatoriais do mundo real, consistem de atribuição, seleção e sequenciamento de componentes, recebendo nomes próprios. Entre os quais tem-se: programação de alocação de veículos, problemas do tipo job shop e flow shop, o problema de balanceamento de linha de montagem, alocação de horários e problemas de alocação de equipes. A Figura 2.2 mostra a classificação baseada em Müller-Merbach.

2.4 Um Modelo Geral de Programação

A seguir, baseado em Coffman (1976), é brevemente descrito um modelo geral para os problemas de programação, considerando os recursos, sistemas de tarefas, restrições de sequenciamento e medidas de desempenho.

Na maioria dos modelos de programação, os recursos consistem de um conjunto P = {P₁,...,P_m} de processadores. Há também, um conjunto adicional de tipos de recursos R = {R₁,...,R_s} solicitados durante a execução de uma tarefa em algum processador. O total dos tipos de recursos R_j é dado por um número positivo m_j. Um sistema geral de tarefas para um dado conjunto pode ser definido como o sistema ( T, , [_ij], {R_j}, {w_j}) onde:

1. T = {T₁,...,T_n} é o conjunto de tarefas a serem executadas,
2. é uma (irreflexiva) ordem parcial definida sobre T, que especifica restrições de precedência operacionais, isto é, T_i T_j significa que T_i deve ser completada antes de que T_j possa começar,
3. [_ij] é uma matriz m x n de tempos de execução, onde _ij > 0 é o tempo requerido para executar T_j, 1 j n , no processador P_i, 1 i m,
4. R_j = [R₁(T₁),..., R_s(T_j)], 1 j n, especifica para o i-éssimo componente, o montante de recursos do tipo R_i requeridos ao longo da execução de T_j.
5. w_j , 1 i n, é interpretado como a taxa de custo. Isto é, o custo de terminar T_i no tempo t é w_it.
   
   FIGURA 2 2 CLASSIFICAÇÃO DOS PROBLEMAS DE OTIMIZAÇÃO COMBINATORIAL (MÜLLER -MERBACH, 1981)
   

Por restrições de sequenciamento entende-se uma restrição do algoritmo de programação à uma determinada classe, por exemplo, programação com ou sem interrupção na execução das tarefas. Por outro lado, considera duas principais medidas de desempenho da programação, quais sejam, comprimento da programação ou tempo máximo de término e o tempo médio ponderado de término.

De acordo com Coffman, os problemas estudados na literatura (de programação da produção) podem ser representados como casos especiais deste modelo.

2.5 Complexidade dos Problemas de Programação

Dois principais conceitos vem a tona na discussão da complexidade de um problema de otimização, quando é considerada a classe ao qual ele pertence, a saber classe P e classe NP.

P identifica a classe de problemas para os quais um bom ou eficiente algoritmo, polinomialmente limitado existe, a onde todos os problemas em NP podem ser resolvidos usando uma busca recursiva de profundidade polinomial (Lenstra, 1977).

A seguir, algumas idéias e definições são introduzidas para um melhor entendimento dos conceitos de classe de problemas P e NP.

No campo da teoria da programação, é muito comum encontrar vários problemas que podem ser facilmente resolvidos, enquanto que outros, parecem ser muito difíceis. Antes de discutir se um problema combinatorial é fácil ou difícil, deve-se primeiro definir a fronteira destes dois conceitos.

De acordo com Ibaraki (1988), comumente um problema é dito ser fácil se existe um algoritmo com complexidade de tempo O(N^k) para uma constante k, onde N é o tamanho do problema. Tal complexidade é dita ser de ordem polinomial, e o algoritmo é denominado algoritmo de tempo polinomial. Por outro lado, se qualquer algoritmo requer uma complexidade não limitada superiormente em N, ele é considerado difícil ou intratável. Por exemplo, ordens típicas não polinomiais são O(N^{log N}) e O(k^N).

Como ponto de partida para a discussão desses problemas e suas dificuldades, primeiramente deve-se definir o que, formalmente, é denominado de um problema de decisão dentro da teoria de otimização combinatorial.

Ullman (1976), define um problema de decisão como uma questão que tem uma resposta sim ou não para uma dada instância do problema. Instância é a seleção de valores para os parâmetros de um problema, isto é, são variáveis livres da questão (Ibaraki, 1987).

A complexidade das instâncias de um problema devem ser medidas em relação ao tamanho delas, isto porque a comparação direta dos resultados computacionais para instâncias grandes ou pequenas não fornecerá nenhuma informação importante. O tamanho da instância de um problema é geralmente definido pelo comprimento dos dados de entrada necessários a sua especificação. Por exemplo, para um grafo G = (V, E) com n vértices e m arestas, o comprimento dos dados de entrada de G é O(n + m). Aqui O(f(n,m)) lê-se ordem f(n,m) e diferentes esquemas de codificação podem ter diferentes comprimentos de entrada, isto é, se o grafo anterior G é representado por uma matriz n x m, o comprimento da entrada requerida é O(n²) ao invés de O(n+ m) (para maiores detalhes ver Ibaraki,1987).

Agora os conceitos de problemas P e NP podem ser melhor entendidos após a apresentação destas idéias introdutórias.

Ullman (1976) define a classe NP (abreviação de nondeterministic polynomial-time) como o conjunto de todos os problemas que podem ser resolvidos por um computador não determinístico num tempo polinomial. Define P como a classe de problemas resolvidos por um computador determinístico num tempo polinomial. Em outras palavras, um problema é dito pertencer à classe NP se uma instância de tamanho N tem um caminho de cálculo cujo comprimento é limitado superiormente por um polinômio em N, que responde sim se, e somente se, a instância tem resposta sim (Ibaraki, 1987).

Como NP é uma classe de problemas combinatoriais muito ampla, aquele problema de complexidade mais alta, poderia ser realmente difícil de resolver. Neste contexto, os conceitos de completação NP e redutibilidade são chaves importantes na identificação destes problemas.

De acordo com Lenstra (1977), um problema P' é redutível para um problema P, escrito P' P, se para qualquer instância de P' uma instância de P pode ser construída num tempo polinomialmente limitado, tal que resolvendo a instância de P resolve também a instância de P'.

Por outro lado, um problema P é denominado de NP-pesado, se qualquer P' na classe NP é redutível para P, isto é, não é mais fácil que qualquer problema em NP. Então, se um problema NP-pesado pertence a NP, então P é denominado NP-completo (Ibaraki, 1977) ou mais formalmente definido como: P é NP-completo se P NP e P' P para cada P' NP (Lenstra, 1977).

Como conclusão pode ser dito que, reconhecidamente, um problema NP-completo é o mais difícil de NP e, portanto, se um problema NP-completo tem uma solução em tempo polinomial determinístico, então todos os problemas em NP também tem (Ullman, 1976). A Tabela 2.1, baseada em Lenstra, apresenta alguns problemas NP-completos.

2.6 Abordagens Para o Problema de Programação

Muitas vezes, não é simples encontrar uma classificação exata para os problemas de programação, não somente porque existem diferentes versões para um dado problema, mas, porque vários procedimentos para uma questão particular, são caracterizados por premissas diferentes e limitações de aplicação dos modelos desenvolvidos.

A grande maioria de procedimentos de programação, podem ser categorizados em dois principais grupos, baseados nas abordagens empregadas. o primeiro, e de longe a maior categoria, denominado de procedimentos heurísticos objetiva produzir programações viáveis boas. O segundo grupo consiste dos procedimentos que procuram produzir a programação melhor ou ótima. Estes são denominados de procedimentos ótimos, também chamados exatos ou analíticos porque geralmente envolvem alguma forma de programação matemática ou outro procedimento analítico mais rigoroso.

Dentro de cada um destes grupos há possíveis esquemas de sub-categorização. Os procedimentos heurísticos por exemplo, podem ser divididos em duas classes (Storer, Wu e Vaccari, 1992):

1. heurísticas específicas, desenvolvidas para cada tipo de problema, baseadas nas especificações da questão tratada (ex. regras de dispatching e sequênciamento e abordagens de Sistemas Especialistas) e,
2. heurísticas de busca local, que são formas alternativas de busca do espaço de soluções baseadas no princípio da vizinhança, como por exemplo: hill climbing, steepest descent, Simulated Annealing (SA), Algoritmos Genéticos (AG) e Tabu Search.

Em relação aos procedimentos ótimos, outras duas classes principais podem ser identificadas (MacCarthy and Liu, 1993):

1. métodos ótimos eficientes: são métodos que geram programações ótimas em tempo polinomial, e
2. métodos ótimos enumerativos: são métodos que envolvem uma enumeração parcial do conjunto de todas as programações possíveis. Esta abordagem é desenvolvida baseada em dois conceitos principais (Day and Hottenstein, 1970): a) o uso de uma técnica de enumeração controlada para considerar todas as soluções potenciais e, b) a eliminação de potenciais soluções inaceitáveis. As mais gerais são formulações de programação matemática, métodos de branch and bound e métodos de eliminação.
   

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

De acordo com Bellman et al. (1982), os problemas de programação podem ser agrupados em três classes básicas:

1. problemas de sequenciamento ou problemas de programação da produção,
2. problema de programação de projetos e,
3. problema de linha de montagem

A seguir cada um dos problemas são brevemente descritos.

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

Tipicamente, o problema de programação da produção envolve um conjunto de produtos que devem ser completados, onde cada produto utiliza um conjunto de operações para ser executado. As operações necessitam de máquinas e recursos materiais e devem ser realizadas seguindo alguma sequência tecnológica. Desenvolver uma programação da produção envolve a seleção de uma sequência de operações (ou rotas de processo) que resultará na realização do produto. Envolve também, a determinação dos recursos necessários para executar cada operação da rota, bem como a determinação das datas em que cada operação da rota começará e terminará (Rodammer e White, 1988). Portanto, a programação da produção é um problema que decide a ordem de execução de todos os produtos em cada máquina e que determina a data de início de cada operação de forma a otimizar uma função objetivo (Bellman et al. 1982).

O problema geral de programação da produção pode ser definida como (MacCarthy e Liu, 1993):

Um conjunto de n produtos {J₁, J₂, ..., J_n } deve ser processado em m máquinas {M₁, M₂, ..., M_m } disponíveis. Um sub-conjunto destas máquinas é requerido para completar o processamento de cada produto. O padrão de fluxo nas máquinas pode ou não ser fixado para algum ou todos os produtos. O processamento do produto J_i na máquina M_i é denominado de uma operação, denotado por O_ij. Para cada operação O_ij, existe um tempo de processamento t_ij. associado. O problema consiste em encontrar uma programação que otimize alguma medida de desempenho.

Está bem estabelecido que a maioria do problemas de programação da produção pertencem a classe dos NP-completos. Trabalhos relativos à complexidade e provas da NP-dureza de novos e velhos e já sedimentados modelos de programação da produção podem ser encontrados em Ullman (1975), Rinnooy Kan (1976); Ullman (1976), Garey et al. (1976), Lenstra et al. (1977), Lenstra (1977), Ibaraki (1977), Lenstra e Rinnooy Kan (1978), King e Spachi (1980), Goyal e Sriskandarajah (1988), Monma e Potts (1989), Kamoun e Sriskandarajah (1993), Chen e Bulfin (1993). A Tabela 2.2 resume alguns dos problemas de programação de máquinas NP-completos (Ibaraki, 1977; Lenstra, 1977; MacCarthy e Liu, 1993; Kamoun and Sriskandarajah, 1993).

Classificação dos Problemas de Programação da Produção

A intenção desta seção não é dar um levantamento exaustivo da literatura de programação da produção, que pode ser encontrado em vários trabalhos de revisão, tais como, Elmaghraby (1968), Bakshi e Arora (1969), Day e Hottenstein (1970), Lenstra et al. (1977), Panwalker e Iskander (1977), Godin (1978), Graham et al. (1979), King e Spachis (1980), Graves (1981), Frost (1984), Rodammer e White Jr. (1988), Buxey (1989), Hendry e Kingsman (1989), Baker e Scudder (1990) e MacCarthy B.L. e Liu J. (1993). O objetivo aqui é delinear uma classificação ampla que permita estabelecer o sentido, direção e perspectiva de pesquisas conduzidas na área, assim como oferecer um resumo das principais abordagens e paradigmas desenvolvidas.

Diversos esquemas tem sido propostos para a categorização dos problemas de programação da produção. Conway et al. 1967 (in: MacCarthy B.L. e Liu J. 1993) sugere um esquema de classificação baseado em quatro descritores A/B/C/D, onde A representa o número de produtos, B representa o número de máquinas, C representa o padrão de fluxo e futuras restrições tecnológicas e de administração e, D representa o critério a ser otimizado Por exemplo, n/m/J/Cmax refere-se ao problema job shop com n produtos e m máquinas que objetiva minimizar o tempo total de processamento (makespan).

Lenstra (1977) introduz um parâmetro l ao terceiro elemento desse esquema tradicional, para representar algumas variações relevantes. A notação n/m/l,llk, é utlizada para representar nos dois primeiros parâmetros o número de produtos e de máquinas respectivamente, I assume um valor de acordo com o padrão de fluxo e o quarto elemento indica o critério de otimalidade.

Lenstra e Rinnooy Kan (1978) caracteriza cada problema de programação em outra classificação de quatro parâmetros a/b/g/d, onde a indica o número de máquinas, b indica ou o tipo de restrições de precedências (prec ou tree) ou a ausência delas, g indica ou a restrição que o tempo de processamento p_i {g} para todo i I, ou a ausência da mesma, d representa o critério de otimalidade.

Graham et al. (1979) apresenta uma notação baseada em três parâmetros a/b/g onde o primeiro elemento define o número de máquinas e o padrão de fluxo, b indica alguma restrição sobre os produtos e g define o critério de programação.

O esquema aqui proposto para a classificação dos problemas de programação é baseado nas características gerais dos problemas e as hipóteses usuais feitas sobre os produtos, máquinas e tempos de processamento. Esta categorização pode ser considerada como uma macro-divisão dos problemas de programação da produção.

De acordo com King e Spachis (1980), Bellman et al. (1982) e Forst (1984) as premissas básicas para os produtos, máquinas e tempos de processamento geralmente assumidas na literatura são:

1. Premissas para os produtos

• Todos os n produtos a serem realizados estão simultaneamente disponíveis na data zero.
• As operações não podem ser interrompidas. Qualquer operação, uma vez começada deve continuar até a sua completa realização.
• Cada produto consiste de m operações que devem ser processadas em m máquinas.
• O processamento de qualquer operação não pode ser feito por mais do que uma máquina por vez.
• Não há ordem de prioridade entre os produtos e cada um tem o mesmo grau de importância
• É permitido estoques ilimitados de produtos em processo ou tempos de espera intermediários
• Uma data final (due-date) pode ser atribuídas a cada produto.
• Cada produto pode ser processado em cada máquina uma única vez

2. Premissas para as máquinas

• A capacidade das máquinas e da mão-de-obra é fixa
• Todas as m máquinas estão disponíveis no início. Quebras e reparações não são permitidas durante o processo.
• Qualquer máquina pode processar qualquer produto.
• Existe uma máquina de cada tipo ou são arranjadas para trabalhar em paralelo uma independentemente da outra.
• Uma máquina não pode executar mais do que uma operação por vez
• Não é possível o intercâmbio de máquinas (flexibilidade).

3. Premissas para os tempos de processamento

• O tempo de processamento de cada operação é dado no início e permanece constante, independentemente da ordem de execução.
• O tempo de preparação e de transporte é incluído no tempo de processamento de uma operação.

Vários problemas de programação da produção são caracterizados relaxando ou restringindo algumas destas premissas. Uma grande gama de resultados e variações existem para um vasto conjunto de especificações ou restrições dos problemas. Por exemplo, restrições de precedências comuns entre produtos (J_i precede J_j ), restrições de precedências entre produtos do tipo árvore (o grafo de precedência pode ser como ramificações), possíveis datas de liberação não iguais para os produtos, não tem datas de espera (no wait) para os produtos entre o seu início e o tempo de realização, um limite superior constante para o número de operações por produtos, um limite superior constante para o tempo de processamento, rotas de processo estáticas, onde cada produto é executado em cada máquina exatamente um vez em estrita sequência tecnológica (entre produtos) ou, rotas de processamento dinâmicas, onde a rota de processamento pode mudar dinamicamente pelo estado da planta (ex. disponibilidade de recursos) ou pelas condições do trabalho (ex. necessidade de retrabalho).

Consequentemente, com isto em mente, um esquema para classificar os problemas de produção é ilustrado na Figura 2.3. Este esquema mostra que os problemas de programação podem ser classificados de acordo com:

1. As restrições tecnológicas dos produtos (Coffman Jr. 1976)

• O caso de processamento sem interrupção: cada operação uma vez iniciada deve ser executada até o seu término;
• O caso com interrupção: uma tarefa pode ser interrompida e removida do processador sob a hipótese de que, eventualmente, todo o tempo de processamento será realizado, e que não há perda do tempo já empregado devido à interrupção, ou seja, as tarefas interrompidas reiniciam a suas execuções no ponto que foram interrompidas.

2. O critério de programação (Graves 1970, Rodammer e White 1988 e MacCarthy e Liu, 1993)

O critério indica a medida sobre a qual as programações, sob qualquer conjunto de premissas, são avaliadas. Neste sentido, duas classes de problemas podem ser identificadas:

• Problemas de único critério: as formulações tradicionais de programação da produção, geralmente especificam um único critério, usualmente associados com custos ou desempenhos das programações. Critérios associados aos custos incluem custos de permanência de estoques, produção variável e custo de atrasos etc. Medidas comuns do desempenho da programação estão relacionados com a utilização eficiente dos níveis dos recursos de produção (makespan, Cmax), rápida resposta à demanda (tempo médio de processamento C, tempo médio de fluxo F, tempo médio de espera W) e cumprimento de datas limites (atraso médio T, atraso máximo T_max, número de produtos atrasados N_T ).
• Múltiplos critérios: ambientes atuais de produção abrangem múltiplas, conflitantes e algumas vezes não comensuráveis restrições e objetivos de desempenho, como minimizar stresses operacionais, melhorar a estabilidade da programação, redução da ociosidade de máquinas para diminuir filas e estoques ou para assegurar a confiabilidade.
  

• open shop: todas as ordens de produção são solicitações dos clientes e não há estoques finais
• closed shop: todas as solicitações dos clientes são atendidas pelos estoques e as tarefas de produção são geralmente, resultados de decisões de reposição de estoques. Este problema é mais conhecido como problema de tamanho de lote.

Outros nomes empregados para esta divisão são: sistemas Make-to-Order e Make-to-Stock respectivamente (Hendry e Kingsman, 1989).

4. O ambiente de programação (Rodammer e White 1988; Graves 1970; Bellman et al. 1982)

• Determinístico: o problema de programação é definido com respeito a um conjunto finito de solicitações totalmente especificadas, isto é, tempos de processamentos, tempos de liberação e datas de entrega são determinísticos. Produtos, máquinas, mão-de-obra e recursos materiais estão disponíveis para todos ao longo do processo.
• Estocásticos: o problema estocástico é definido levando em consideração eventos e distúrbios aleatórios, tais como: quebras de máquinas, indisponibilidade de operador e de material, tempos variáveis de processamento, de liberação e de entrega.

5. A natureza da chegada do produto (Day e Hottenstein 1970)

• Caso estático: todos os produtos são simultaneamente iniciados.
• Caso dinâmico: os produtos estão constantemente entrando e saindo da fila, de acordo com algum processo estocástico

6. A complexidade de processamento (Graves 1970, MacCarthy e Liu 1993)

A complexidade de processamento está relacionada com o número de passos associados com cada tarefa de produção

• Um estágio com um processador: todas as tarefas requerem um passo de processamento que deve ser executado em um elemento de produção. este problema é comumente denominado de problema de uma máquina.
• Um estágio com processadores paralelos: as tarefas podem ser executadas em k processadores idênticos ou não idênticos num único estágio. Cada produto necessita uma, e somente uma destas máquinas
• Múltiplos estágios, flow shop: para um problema de múltiplos estágios, cada tarefa requer ser processada num conjunto de máquinas distintas. Nos problemas flow shop, cada produto tem um padrão de fluxo idêntico. Um problema flow shop no qual a ordem de processamento dos produtos em todas as máquinas é restrito de forma a ser a mesma é denominado de flow shop de permutação.
• Múltiplos estágios, job shop: aqui cada produto tem o seu próprio padrão de fluxo ou rota específica através das máquinas. Isto quer dizer que não há restrição no passos de processamento para as tarefas, e que rotas alternativas para os produtos são permitidas.
• Múltiplos estágios, flow shop com máquinas paralelas: é um problema flow shop onde há k_i máquinas idênticas ou não idênticas, em um ou em todos os estágios (i = 1,2,...,m), e qualquer produto requerendo este estágio deve ser processado em uma, e somente uma, destas máquinas.
• múltiplos estágios, job shop com máquinas paralelas: é um problema job shop onde há k_i máquinas idênticas ou não idênticas, em um ou em todos os estágios (i = 1,2,...,m), e qualquer produto requerendo este estágio deve ser processado em uma, e somente uma, destas máquinas. A situação mais geral é o problema job shop em máquinas paralelas não idênticas.

Como resumo do esquema proposto para a categorização dos problemas de programação da produção, alguns trabalhos são listados nas tabelas 2.3 à 2.6. Deve ser observado que a presença de restrições adicionais foram omitidas dada a grande variedade de problemas. As referências citadas tem a intenção de ser exemplos e não são necessariamente exaustivas.

2.7.2 Problema de Programação de Projetos

O problema de programação de projetos tem sido objeto de interesse desde o advento das técnicas PERT e CPM. A questão básica desta área é encontrar uma programação viável tal que algum objetivo de administração seja otimizado. O problema surge quando as quantidades dos recursos solicitados pelas atividades são limitados. Devido a isto, decisões sobre o sequenciamento das atividades são requeridas, resultando em incremento da duração do projeto além daquela determinada sem a consideração deste tipo de limitação. O objetivo é tomar as decisões de sequenciamento, sujeito a restrições de recursos e precedência, de modo a minimizar este incremento da duração. (Bell and Han, 1991). Este tipo de problema é denominado programação de projetos com restrição de recursos.

Porém, sob restrição de recursos, obter uma programação ótima ou viável para a maioria dos problemas práticos de programação é NP-pesado. (Lenstra e Rinnooy Kan 1978; Boctor 1990). Segundo Karp (in: Norbis e Smith 1986), no problema de programação com restrição de recursos, a forma como as restrições de precedência interagem com as restrições nos recursos, derivando para conjuntos desconexos, caracteriza o problema como combinatorial NP-completo.

De acordo com Bennington e McGinnis (1973) e Talbot (1982), pode-se assumir, sem perda de generalidade, que o problema geral de programação de projetos pode ser representado como um grafo acíclico (de atividades no nó) G = (N,P), onde N representa o conjunto de atividades e P, o conjunto de arcos, corresponde às relações de precedência. Associado a cada atividade iN (i = 1,..,n) existe um conjunto de possíveis durações d_i e as correspondentes quantidades demandadas r_ij do recurso tipo j (j = 1,...,m). A disponibilidade do recurso j no período t pode ser escrita como a_j(t). Cada combinação duração-recursos é denominada modo. Por exemplo, suponha que é possível completar uma dada atividade A em 5 dias empregando uma pessoa experiente (modo 1) ou em 7 dias usando uma pessoa inexperiente (modo 2).

Uma solução viável para o problema em questão é aquela que satisfaz, em primeiro lugar a limitação dos recursos e, em segundo as restrições tecnológicas de execução das tarefas (Mohanthy e Siddiq, 1989). Neste contexto, o problema geral de programação de projetos com restrição de recursos pode ser estabelecido como: dado um conjunto de atividades interrelacionadas (relações de precedência), onde cada atividade pode ser executada de um, entre vários modos, cada um caracterizado por uma duração e requerimento de recursos. Pergunta-se: quando cada atividade deve começar e qual modo deve ser adotado de forma a otimizar algum objetivo determinado pela administração? (Boctor, 1990).

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

A partir da literatura especializada, pode-se estabelecer que não somente existem diferentes versões para os problemas, como também há vários procedimentos propostos para uma topologia particular, as quais são caracterizadas por premissas e limitações diversas. Vários trabalhos de revisão bibliográfica relacionados ao problema em questão estão disponíveis na literatura (Herroelen 1972, Davis 1973, Bennington e McGinnis 1973, Davis 1974, Mohanty e Siddiq 1989, Boctor 1990), assim como, trabalhos que comparam desempenhos de algoritmos ótimos e/ou heurísticos (Patterson 1973, Davis e Patterson 1975, Cooper 1976, Holloway et al. 1979, Kurtulus e Davis 1982, Patterson 1984, Dumond e Mabert 1988, Badiru 1988, Boctor 1993, Oguz e Bala 1994)

Similarmente ao esquema proposto para classificar os problemas de programação da produção, a Figura 2.4 ilustra uma categorização do problema aqui tratado, fundamentado na descrição das premissas básicas assumidas para as atividades e os recursos durante a formulação dos modelos.

As seguintes suposições são frequentemente assumidas na formulação dos paradigmas de programação de projetos:

1. Suposições sobre as atividades

• Cada atividade pode acontecer somente em um intervalo de tempo ao longo do horizonte do projeto.
• Nenhuma atividade pode iniciar, a menos que todas as suas antecessoras tenham sido completadas.
• As atividades uma vez iniciadas não podem ser interrompidas.
• As durações das atividades são inteiras e conhecidas.
• As atividades devem ser executadas de um único modo j = 1, ..., M_i e uma vez iniciada neste modo, não pode mais ser mudado.

2. Suposições sobre os recursos

• Somente um tipo de recurso renovável é requerido pelo projeto.
• A disponibilidade dos recursos é constante ao longo da realização do projeto.
• A demanda dos recursos de uma atividade é conhecida e constante ao longo da duração da mesma.
• Não é permitida a substituição entre recursos.

O relaxamento de algumas das hipóteses básicas acima citadas, leva à versões diferentes o problema de programação de projetos.

A representação esquemática da Figura 2.4 mostra que o problema em questão pode ser classificado de acordo com:

1. O tipo de problema de alocação de recursos abordado (Herroelen 1972, Davis 1973)

• Problema de compressão ou "Time/cost trade-off problem": não há restrição imposta à disponibilidade dos meios. O problema consiste em reduzir o tempo de execução do projeto, adicionando recursos à determinadas atividades, de forma que a duração de cada uma delas possa ser acelerada. O objetivo é determinar a programação de menor custo.
• Problema de nivelamento de recursos: este problema surge quando existem suficientes recursos para completar o projeto, mas deseja-se manter a utilização dos mesmos a uma taxa constante.
• Problema de alocação de recursos limitados: o problema acontece quando a utilização dos recursos é restrita a um certo limite. Neste caso, a meta é alocar os diversos meios as atividades de forma a minimizar alguma função objetivo. (comumente minimizar a duração do projeto).

2. O número de projetos simultaneamente programados (Mohanthy e Siddiq 1989, Boctor 1990)

• Projeto único: somente atividades de um mesmo projeto competem pelos recursos disponíveis.
• Projetos múltiplos: a competição por recursos disponíveis é realizada entre atividades do mesmo projeto e entre projetos diferentes. Duas situações distintas podem ser identificadas: a) situação estática onde é assumido que todos os projetos são conhecidos inicialmente e, b) situação dinâmica onde novos projetos estão iniciando continuamente no tempo.

3. A condição de interrupção (Boctor 1990)

• Interrupção permitida: a interrupção da execução das atividades é permitida.
• Sem interrupção. uma vez começadas as atividades, não é permitido interrupções.

4. O nível de incerteza da informação do projeto

• Caso determinístico: onde existe um completo conhecimento das durações e demanda de recursos das atividades.
• Caso estocástico: onde assume-se durações variáveis para as atividades e/ou variação nos requerimentos dos recursos das mesmas.
  

• Modo único: onde cada atividade pode ser realizada em exatamente uma única forma.
• Múltiplos modos: quando cada atividade pode ser realizada com uma das várias formas disponíveis, isto é, as durações das atividades são funções dos recursos consumidos.

6. O número de recursos requeridos (Mohanthy e Siddiq, 1989)

• Recurso único: somente um tipo de recurso é requerido pelo projeto.
• Múltiplos recursos. Onde mais de um tipo de recurso é necessário para a realização do projeto.

7. A natureza do recurso empregado (Werglarz 1979, Slowinski 1980, Boctor 1990)

• Renováveis: quando os recursos estão disponíveis em quantidades limitadas a cada período, ex. mão-de-obra.
• Não renováveis: quando o total de consumo de recursos ao longo ou em parte do projeto é restrito, ex. dinheiro
• Duplamente restritos: quando a disponibilidade de recursos é limitada por períodos e para o total do projeto, ex. dinheiro.

A classificação segundo o número de critérios de otimização não foi incluída no esquema proposto, dado que a grande maioria dos trabalhos publicados utilizam uma única função objetivo, como por exemplo, minimização da duração do projeto ou maximização da utilização dos recursos. Outros objetivos frequentemente reportados são minimização do custo total do projeto e maximização do valor presente.

Outra suposição importante frequentemente feita, está relacionada com o tipo de relação de dependência entre atividades, ou seja, a utilização ou não de sobreposição de atividades. A grande maioria dos trabalhos publicados tratam da relação do tipo fim-início, isto é, sem sobreposição de atividades.

A seguir, como resumo do esquema proposto para a categorização dos problemas de programação de projetos, alguns trabalhos e resultados estão ilustrados na Tabela 2.7. Estas referências não tem a intenção (nem poderia, dada a extensão da literatura) de ser exaustivas.

2.7.3 Problema de Linha de Montagem

O objetivo deste tipo de problema, é decidir o número mínimo de estações de trabalho que são atribuídas a elementos de trabalho com alguma relação de precedência, ou minimizar o tempo de ciclo, isto é, a quantidade máxima de tempo de processamento em cada estação, para um dado conjunto de estações de trabalho (Bellman et al. 1982).

De uma maneira mais formal, o problema da linha de montagem é definida como sendo o seguinte problema de decisão (ver Falkenauer e Delchambre, 1992):

Dado um grafo acíclico direcionado G=(T,P) (os nós T representando as tarefas, e os arcos as relações de precedência) com uma constante L_i (extensão da tarefa) atribuída a cada nó T_i, uma constante C (o tempo de ciclo) e uma constante N, pergunta-se: podem os nós T serem divididos em N ou menos subconjuntos S_j (a j-éssima tarefa da estação) de tal forma que (1) para cada subconjunto, a soma de L_i associada com os nós no subconjunto não exceda C, e (2) exista uma ordenação do subconjunto tal que, sempre que dois nós em subconjuntos distintos são unidos por um arco em G, o arco vai do subconjunto de mais alta ordem (cedos) para um de mais baixa ordem (tardes).

Não foi aprofundado o estudo neste deste tipo de problema devido ao, relativamente fraco interesse entre a questão abordada pelo trabalho e este problema.

Embora o problema de linha de montagem e o de programação de projetos com restrição de recursos possam ser formulados de tal maneira a enfatizar as suas aparente similaridades, como Wilson e Mandeville (in: Davis 1973) sugerem, ambos diferem consideravelmente do ponto de vista administrativo. Enquanto o problema de linha de montagem está preocupado com um grande número de operações repetitivas e um grande número de produtos, o de programação de projetos geralmente é do tipo: um produto, uma operação por vez (Weist in: Davis 1973).

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

Como Davis (1973) colocou, há fortes similaridades entre alguns problemas de programação da produção, programação de projetos com restrição de recursos e linha de balanço, ao ponto que procedimentos originalmente desenvolvidos para um tipo de problema tenham sido aplicados nos outros, com considerável sucesso.

O problema de programação de projetos sujeito a restrição de recursos, tem similaridades conceituais com a programação de máquinas que tem estimulado interesses de aplicação recíproca de modelos de solução (Davis, 1973).

Contudo, "o paradigma de programação de projetos com limitação de recursos é fundamentalmente mais pragmático que a programação de máquinas, e leva em consideração muito mais das complexidades do ambiente de programação. São consideradas relações tecnológicas mais complexas e requerimento de múltiplos recursos" (Rodammer e White, 1988).

Na prática, uma das maiores diferenças entre a programação job shop e a programação de projetos, é a natureza contínua do trabalho e do fluxo no ambiente job shop e a formação de filas de produtos entre operações de processamento (Davis, 1973).

A programação de projetos e de múltiplos projetos com restrição de recursos, é considerada generalização da programação job shop tradicional e job shop com várias máquinas do mesmo tipo respectivamente (Bennington e McGinnis 1973; Bellman et al. 1982 e Rodammer e White 1988). Segundo Patterson et al. (1990), o problema de programação de projetos sujeito a restrição de recursos subjuga os problemas de programação job shop, flow shop, linha de montagem e problemas de programação análogos.

A Tabela 2.8 ilustra relações mútuas básicas entre estes três tipos de problema.

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

Nas seções seguintes, será discutida e formalmente definida a natureza do problema da programação de projetos com restrição de recursos. Também, as publicações consideradas mais relevantes ao desenvolvimento deste trabalho são brevemente descritas.

2.9.1 Noções Fundamentais

O principal objetivo durante um processo de construção é completar o projeto em tempo, dentro do orçamento, paralelamente a outros requisitos e especificações de qualidade estabelecidos (Rasdorf e Abudayyeh 1991).

Uma administração com sucesso de um projeto de construção, requer a elaboração de um plano mestre completo, definido no tempo, realístico e prático (Prentis 1989). Normalmente, no desenvolvimento de um projeto, todas as operações envolvidas na construção são divididas em quatro fases funcionais: planejamento, programação, monitoramento e controle, como mostra-se na Figura 2.5. Estas quatro fases são separadas em dois estágios diferentes: estágio de preparação (planejamento de programação), e estágio de implementação (monitoramento e controle).

O planejamento é aquilo que deve ser realizado no futuro para atingir os objetivos, sendo executado em vários níveis e em vários períodos de tempo ao longo do projeto.

Na implementação do presente trabalho, o interesse maior é no nível aqui denominado planejamento para a programação. Este nível está relacionado com as suposições assumidas sobre os modos, relações de precedência, relações de dependência (sobreposição ou não), representação lógica (tarefas nos nós ou nos arcos) das atividades, bem como informações relativas aos recursos (demanda, disponibilidade, tipo e classe), custos e critérios de decisão.

A programação é a determinação do tempo e da sequência de execução das atividades do projeto de forma a atingir algum objetivo administrativo. A programação determina como cada atividade deve ser realizada, isto é, qual opção recurso-duração deve ser empregada e quando cada tarefa deve ser iniciada e terminada (Talbot 1982). Esta fase específica é denominada Programação Planejada.

O monitoramento é a identificação daquilo que atualmente está sendo realizado. É a coleta de informações sobre o desempenho no tempo do projeto e o confronto do progresso do projeto contra a programação planejada. Esta fase denomina-se Atualização da Programação e diz respeito aos efeitos que as mudanças do plano de trabalho tem sobre a porção do projeto ainda não realizado. (Callahan et al. 1992).

O controle usa os dados obtidos através do monitoramento para trazer o trabalho de volta à programação planejada. Esta parte da administração de projetos de construção é denominada reprogramação. A reprogramação normalmente é realizada para adaptar a programação original às situações de campo.

Finalmente, para completar o ciclo existe um quinto elemento denominado de realimentação (feedback) que permite fazer alterações, tanto na fase de planejamento quanto na fase de execução.

O estudo de cada uma desta fases leva à identificação de várias linhas de pesquisas, agrupadas em três grandes correntes.

Primeira Corrente de Pesquisa

A primeira corrente de estudos está focalizada no desenvolvimento de métodos e abordagens para o planejamento para a programação, anteriormente citado. Esta corrente está principalmente preocupada com a definição das relações e a representação lógica das tarefas de construção.

Segunda Corrente de Pesquisa

A segunda corrente objetiva desenvolver modelos de programação que assumem que as informações básicas de entrada como duração, dependências, modos, custos, recursos, etc. já foram determinados. Esta corrente lida com a elaboração de procedimentos que levam em consideração três principais restrições: tempo, recursos e desempenho.

Esta corrente por sua vez, pode ser subdividida em dois grandes grupos. O primeiro grupo é formado por aqueles procedimentos que tipicamente pressupõem a não restrição de recursos, que são fundamentalmente diferentes daqueles que levam em consideração a limitação dos meios. Neste contexto três tipos diferentes de problemas são identificados: os problemas de compressão de projetos tempo/custo e os problemas de restrição de tempo que formam o corpo do primeiro grupo e os problemas de restrição de recursos formando o segundo grupo.

Problemas de Compressão de Projetos Tempo/Custo

Os problemas tratados por este grupo são caracterizados pela suposição de que o desempenho de algumas ou de todas as atividades de um projeto pode ser melhorado alocando mais recursos a elas, a despeito de um custo direto maior (Davis 1973).

O processo de redução da programação para diminuir o tempo de realização do projeto é denominado compressão e os problemas deste tipo são conhecidos como Compressão de Projetos Tempo/Custo (Time/Cost Trade-Off problems). Este tipo de problemas surge quando é imperativo para o administrador ajustar as durações e o sequenciamento das atividade para atender requisitos contratuais, ainda que ajustes ineficientes, como múltiplas contratação e demissões, horas extras, ou equipes grandes sejam empregados. (Callaham et al. 1992)

Os procedimentos de compressão usam uma avaliação do tempo e custo variável das atividades para determinar qual duração dever ser reduzida para minimizar economicamente a duração total do projeto, tradicionalmente sob a premissa de recursos ilimitados.

Muitos trabalhos podem ser encontrados na literatura como Elmaghraby e Pulat (1979), Moder et al. (1983), Mustafa e Murphree (1989), Johnson e Schou (1990), Callaham at al. (1992) entre outros, que abordam o problema de compressão de projetos através de algoritmos exatos e/ou heurísticos.

Elmaghraby e Pulat (1979) propõem um abordagem exata ao problema em questão levando em conta o custo de compressão do projeto, bem como penalidades para a realização de um conjunto de marcos referenciais do mesmo.

Moder, Philips e Davis (1983) discutem a implicação sócio-econômica da compressão de projetos. Eles concluem que a duração ótima de um projeto é aquela onde o custo marginal da compressão é igual aos seus benefícios marginais.

Mustafa e Murphree (1989), modelam este problema como uma metodologia de tomada de decisão de múltiplos critérios que denominaram de processo de hierarquia analítica - AHP (analytic hierarchy process). Esta abordagem permite considerar critérios subjetivos e não subjetivos durante o processo da escolha do esquema de compressão mais apropriado.

Johnson e Schou (1990), exploram regras efetivas de aceleração de projetos quando redes estocásticas são empregadas

Callaham at al. (1992), usa uma abordagem matemática baseada na relação custo-duração para tratar o problema em questão. Esta relação é representada como uma série de segmentos usados de forma a aproximar a curva para o custo de compressão e os pontos de duração normal. É a inclinação destes segmentos que é empregada para determinar o impacto sobre o custo do projeto quando a sua duração é reduzida.

Problemas Com Limitação de Tempo ou De Nivelamento de Recursos

É bastante frequente que, para muitos projetos e por razões diversas, existam datas de início e término que não podem ser mudadas. Neste contexto, são alocados tantos recursos quantos sejam necessários para assegurar a realização em tempo. Por outro lado, existem instâncias onde os custos de contratação e dispensa de mão-de-obra ou recursos materiais a curto prazo podem ser substanciais.

Neste sentido, o problema de nivelamento de recursos surge quando há recursos suficientes e o projeto deve ser concluído numa data específica, porém é desejado ou necessário reduzir a variação nos padrões de utilização dos recursos ao longo da duração do projeto. (Moder et al. 1983).

A principal hipótese assumida no desenvolvimento de qualquer procedimento para tratar este tipo de problema é que não é permitido aumentar a duração do projeto além da data pré-estabelecida. A idéia central dos procedimentos usados neste problema fundamentam-se na reprogramação das atividades dentro dos limites determinados pelas suas folgas de modo a obter uma melhor distribuição dos recursos (isto é, assume-se que existe uma programação básica que fornece o conjunto de datas de início e término das atividades)

Este tipo de problema, para o qual vários procedimentos heurísticos e exatos existem, como por exemplo Burgess e Killebrew in: Moder et al. (1983 p.205), Chang (1987), Harris (1990), Seibert e Evans (1991), Harris in: Callahan at al. (1992 p.283), para citar os mais recentes, será abordado paralelamente ao problema central do trabalho.

Problemas com Restrição de Recursos

Segundo Moder et al. (1983), esta categoria de problemas, que é muito mais comum na indústria da construção, surgem quando há limitações na quantidade disponível dos recursos necessários à execução do projeto (ou projetos). Quando a utilização dos recursos é restrita a uma dado limite, o objetivo pode ser a alocação deles às atividades de modo a que a duração do projeto seja minimizada. Outros objetivos, como minimização dos custos, minimização do atraso, etc. não são inusuais (Davis 1973).

O problema de programação de projetos com restrição de recursos forma o escopo do presente trabalho e, neste sentido, será tratado em maiores detalhes nas seções posteriores.

Terceira Corrente de Pesquisa

A terceira corrente de pesquisa, uma extensão da segunda corrente, diz respeito à monitoração e ao controle do progresso do projeto de construção. No desenvolvimento de procedimentos para estes problemas, a maioria das vezes assume-se como entrada do sistema, que a melhor programação possível já foi determinada através de qualquer modelo. Paradigmas tradicionais de monitoramento e controle recompilam custos e durações utilizando dados atuais do desempenho de campo do projeto.

2.9.2 Tipo de Problema Abordado

O Método do Caminho Crítico (CPM) e o Program Evaluation and Review Technique (PERT) são as ferramentas mais comumente utilizadas nas últimas três décadas na administração de projetos de construção. Entretanto, é bem reconhecido que os procedimentos PERT/CPM básicos são limitados, no sentido de não levar em consideração a disponibilidade de recursos no processo de programação. Como resultado, muitos trabalhos que tem sido desenvolvidos desde que estas técnicas foram introduzidas, corrigem esta deficiência.

Sob condições de limitação de recursos, são necessárias decisões de sequenciamento de forma a satisfazer a demanda das atividades concorrentes e a minimizar o aumento da duração do projeto além da data determinada desconsiderando esta restrição.

O problema de programar um conjunto de atividades sem que as suas relações de precedência e os limites imposto aos recursos sejam violados, não é uma tarefa fácil. Esta dificuldade aumenta quando, simultaneamente, algum critério de otimização deve ser cumprido (Moder et al. 1983).

Em geral, o objetivo maior deste tipo de problema, comumente conhecido como problema de programação com restrição de recursos, é encontrar uma programação viável que minimize a duração do projeto (Davis e Patterson 1975, Boctor 1990, Khattab e Choobineh 1991).

2.9.3 Abordagens para o Problema

O problema de programação de projetos com restrição de recursos tem sido fonte de investigação desde os anos 60 (Ver seção 2.7.2) e um grande número de publicações e paradigmas heurísticos e exatos tem sido propostos para uma infinidade de versões do problema, assim como trabalhos de comparação entre abordagens diferentes. (Patterson 1973, Davis e Patterson 1975, Cooper 1976, Holloway et al. 1979, Kurtulus e Davis 1982, Patterson 1984, Elsayed and Nasr 1986, Dumond and Mabert 1988, Mohanthy e Siddiq 1989, Boctor 1990, Boctor 1993, Oguz e Bala 1994).

Entretanto, a maioria dos problemas práticos desta área são representativos dos problemas combinatoriais NP-pesados (Wiest 1967, Lenstra e Rinnooy Kan 1978, Blazewicz et al. 1983, Boctor 1990).

Devido ao crescimento exponencial do tempo computacional em função do tamanho do problema, a geração de soluções ótimas globais, ainda para problemas reais de tamanho modesto, permanece em princípio, computacionalmente impraticável através de métodos de enumeração completa. (Wiest 1967, Davis e Patterson 1975, Patterson 1984, Moder et al. 1983, Davis et al. 1992).

Neste sentido, dado que os procedimentos baseados em abordagens ótimas não tem se mostrado favoráveis, procedimentos baseados em heurísticas tem sido extensivamente utilizados como abordagens de solução ao problema em questão. Estes tipos de abordagem são hoje, as formas mais eficientes de obter uma solução boa e satisfatória para o problema, em tempo cumputacional razoável (Davis e Patterson 1975, Moder et al. Boctor 1990, Khattab e Choobineh 1990).

A Figura 2.6 mostra o esquema para uma abordagem heurística básica para o problema aqui abordado.

Neste contexto, na implementação do modelo proposto, uma abordagem heurística é utilizada para a solução do problema.

Tipicamente, as premissas básicas da maioria das heurísticas utilizadas na alocação de recursos, empregam regras de prioridade para selecionar quais as atividades que devem ser executadas ou retrasadas. Infinidade de regras tem sido propostas e utilizadas por pesquisadores e usuários. Em Patterson (1973), Davis e Patterson (1975), Kurtulus e Davis (1982), Dumond e Mabert (1988), Boctor (1990), Khattab e Choobineh (1991), e Boctor (1993) podem ser encontradas as fundamentações básicas das regras mais comuns resumidas na Tabela 2.9.

2.9.4 Formulação Geral do Problema Abordado

O problema de programação de projetos com limitação de recursos pode ser formalmente caracterizado pelas seguintes premissas (Slowinski 1981, Drexel e Gruenewald 1993):

• Um projeto composto de um conjunto A de n atividades, {A₁, ..., A_n}.
• As atividades não podem ser interrompidas durante a sua execução.
• Um conjunto de critérios de otimalidade Q para o desempenho do conjunto A composto de: (1) critério de tempo, como minimização da duração do projeto, T = min [t_i], onde t_i é o tempo de realização de A_i; a minimização do atraso L = min[t_i - d_i], onde d_i é a data (due date) de realização ideal de A_i., e (2) critérios de custo.
• A atividade A_i pode ser executada em um dos diferentes modos m = 1, 2, ..., M. Toda atividade, uma vez iniciada num determinado modo, deve ser concluída sem possibilidade de mudança.

Programar a atividade A_i no modo m implica numa duração d_im. Um conjunto R de recursos renováveis {R, ..., R} classificados em p tipos, cada um disponível em B unidades no período t, k = 1,2, ..., p. Programar uma atividade A_i no modo m, usa r unidades por período do recurso R.

Baseado nas premissas acima citadas, o problema de programação de projetos com restrição de recursos é definido da seguinte maneira:

Definição (Sampson e Weiss 1993, Demeulemeester e Herroelen 1992): Determinar as datas de início das atividades de um projeto que maximize alguma determinada função objetivo, sujeito à restrições de precedência e alguma definição determinística viável.

maximizar f(T) f Q (2.1)

sujeito a:

restrições de precedência

f_j - f_i d_jm (i, j) H, H A, (2.2)

disponibilidade de recursos

r B r R, (3.3)

m = 1, ..., M

k = 1,2, ..., K (K = p)

onde:

f_i = data de término da atividade i, i A ,

H = conjunto de pares de atividades indicando restrições de precedência,

d_im = tempo de processamento da atividade i no modo m,

r = quantidade do recurso renovável e tipo k, requerido pela atividade i no modo m.

S_t = conjunto de atividades em execução no intervalo ]t - 1, t],

B = disponibilidade total do recurso renovável do tipo k.

2.9.5 Trabalhos Prévios

A seguir é apresentada uma revisão sucinta da literatura, considerada mais relevante ao desenvolvimento do trabalho.

Como já foi ressaltado em seções anteriores, o problema de programação de projetos com restrição de recursos é relativamente um dos que maior atenção tem recebido na literatura. Porém, a maioria dos algoritmos atualmente disponíveis não atendem completamente as situações reais, devido principalmente, às limitações impostas nas premissas básicas sob as quais eles são desenvolvidos. Diferentes maneiras de abordar o problema leva a diferentes versões para o problema em questão.

Medidas de desempenho para os projetos

A maioria das versões estudadas na literatura utilizam a minimização da duração do projeto como critério de otimalidade, entretanto várias abordagens tratam outros objetivos ou múltiplos objetivos diferentes, como por exemplo Talbot (1982), Deckro e Hebert (1989), Patterson et al. (1990), Sampson e Weiss (1993), Rascoe et al. (1992).

Talbot (1982), introduz métodos para formular e resolver o problema de programação de projetos onde a duração é função dos recursos. Ele desenvolveu uma metodologia de dois estágios que usa regras heurísticas no primeiro estágio e um algoritmo de enumeração implícita no segundo estágio, objetivando minimizar a duração do projeto. Este mesmo algoritmo básico é utilizado para abordar o problema de compressão de projetos com limitação de recursos.

Deckro e Herbert (1989), desenvolveram modelos ótimos para dois casos específicos, a compressão de recursos críticos e a compressão da duração das atividades, estendendo modelos de programação tradicionais para tratar a compressão de projetos com restrição de recursos. O primeiro modelo desenvolvido está baseado no modelo proposto por Pritsker, Watters e Wolfe (1969). O algoritmo que trata do segundo caso está fundamentado no modelo de Bowman (1959).

Patterson et al. (1990), reporta uma experiência computacional para resolver a versão de múltiplos modos do problema de programação com restrição de recursos para as funções objetivos de minimização da duração do projeto e maximização do valor presente. Um procedimento de busca em profundidade baseada no algoritmo de branch and bound é utilizado como metodologia de solução. Este modelo consiste de duas fases: inicialização do problema de enumeração e geração do espaço de solução. Na fase de inicialização é realizada a priorização heurística das atividades e a seleção do modo de execução das atividades. Este procedimento guia a busca da solução inicial, afetando a ordem na qual as atividades e os modos serão considerados na atribuição dos recursos durante a fase de enumeração. Esta segunda fase é utilizada para gerar o espaço de solução e para avaliar, implícita ou explicitamente, todas as soluções parciais que podem ser estendidas para uma solução ótima.

Sampson e Weiss (1993), apresentam um algoritmo de busca local para a minimização da duração do projeto sob restrição de recursos. Esta heurística é baseada na definição da solução, numa estrutura de vizinhança, que indica como mover-se de uma solução para outra possivelmente melhor, e numa condição de parada.

Davis et al. (1992), finalmente, abordam o caso de múltiplos objetivos para progamação de projetos com limitação de recursos. Eles empregam um método de programação linear multi-objetivos para desenvolver um procedimento de decisão que permita ao decisor avaliar a relação entre vários objetivos e determinar a programação de melhor preferência. O primeiro objetivo do modelo é a minimização da duração do projeto. Os objetivos remanescentes, minimizam a excessiva utilização dos vários recursos individuais ao longo do horizonte de planejamento.

O caso de interrupção de atividades

Slowinski (1981), Leachman e Kim (1992), entre outros, tratam o caso onde a interrupção e/ou a sobreposição de atividades é permitida.

As duas abordagens apresentadas por Slowinski (1981), baseadas na programação linear multi-objetivos, tratam do caso de múltiplos modos com utilização de diferentes categorias de recursos (renováveis, não renováveis e duplamente restritos) e múltiplos critérios de otimização, levando em consideração a interrupção de atividades.

Leachman e Kim (1992) por outro lado, propõem uma abordagem para lidar com relações que consideram sobreposição entre as atividades, baseada na medição do progresso das atividades em termo da aplicação acumulativa dos recursos, ao invés do modelo tradicional baseado na duração. O modelo leva ainda em consideração durações variáveis para as atividades.

O caso múltiplos modos

São poucos os trabalhos que abordam o caso de múltiplos modos. Além dos trabalhos já citados de Slowinski (1981) e Talbot (1982), esforços recentes vem sendo realizados para formular e resolver este tipo de problema, entre os quais podem ser citados Boctor (1990) e Drexel e Gruenewald (1993).

Boctor (1990) desenvolveu um esquema geral para resolver problemas de tamanho grande, para os quais a duração das atividades é função dos recursos alocados a sua execução, objetivando minimizar a duração total do projeto. Foi realizado um estudo comparativo do desempenho de 21 regras heurísticas. O modelo emprega os conceitos tradicionais de priorização de atividades e seleção de modos.

Drexel e Gruenewald (1993) apresentam um método de programação estocástico para formular e resolver o caso de programação com múltiplos modos e restrição de recursos, bem como a compressão de projetos com múltiplos modos. A contribuição do modelo é generalizar regras de programação determinísticas apropriadas incorporando uma técnica de seleção aleatória ponderada.

Outros modelos interessantes para o problema abordado, são os desenvolvidos por Jones (1984), Li e Willis (1992) e Moselhi and Lorterapong (1993).

Jones (1992) usou uma abordagem de Monte Carlo para aleatoriamente gerar um grande conjunto de programações viáveis para então selecionar a de melhor desempenho.

Li e Willis (1992) apresentam um procedimento heurístico onde um projeto é programado do início para o fim e do fim para o início iterativamente até que não sejam obtidas melhoras na duração do projeto. Esta programação iterativa aborda diferentes categorias e tipos de recursos, com diferentes níveis de utilização, tais como: recursos renováveis constantes no tempo, recursos renováveis variáveis no tempo, recursos não renováveis e duplamente restritos constantes no tempo, recursos não renováveis e duplamente restritos variáveis no tempo.

Moselhi e Lorterapong (1993) desenvolveram um algoritmo heurístico que objetiva incrementar a consistência do desempenho da tradicional regra da folga total mínima. O modelo é baseado na alocação de recursos por grupo. Os conjuntos de atividades são geradas considerando primeiramente todas as possíveis combinações das atividades ativas em conflito e então reduzindo para aquelas viáveis, priorizadas pelo menor impacto sobre a duração do projeto.

Múltiplos projetos

Todas as abordagens acima mencionadas tratam com a alocação de múltiplos recursos para um único projeto. Entretanto, o impacto na programação quando se considera múltiplos projetos é muito maior. Entre os esforços mais recentes neste campo podem ser citados os trabalhos de Dumond e Mabert (1988), Mohanty e Siddiq (1989), Tsubakitani e Deckros (1990), Kim e Leachman (1993).

Dumond e Mabert (1988), abordam o problema de estabelecer datas de entrega num ambiente onde os projetos chegam constante e aleatoriamente no tempo. Cinco regras heurísticas e quatro procedimentos de atribuição de due dates foram testados usando um modelo de simulação de duas fases. Na primeira fase as regras heurísticas controlam a alocação dos recursos. Na segunda fase é demostrado o desempenho dos procedimentos de atribuição de "due dates".

Mohanty e Siddiq (1989) fizeram uma análise do problema de múltiplos projetos e restrição de recursos com due dates individuais. A análise é executada usando Programação Inteira por Objetivos - IGP (Integer Goal Programming) e simulação. O IGP é usado para gerar as programações. O modelo de simulação é empregado para testar algumas regras heurísticas em diferentes situações de limitação de recursos. Finalmente o modelo compara as programações geradas por ambos modos e decide pela melhor opção.

Um modelo de programação e controle foi desenvolvido por Tsubakitani e Deckros (1990) para o problema em questão. O paradigma, desenvolvido a partir de dados reais de uma firma, usa as abordagens propostas por Kurtulus e Davis (1982) para a seleção das regras heurísticas apropriadas.

Kim e Leachman (1993), consideram o problema de programação de multi-projetos com custos de atraso. Eles desenvolveram um algoritmo heurístico baseado no conceito dos perfis e objetivos acumulativos dos recursos para minimizar o custo total de atraso.

Herroelen (1972) apresenta estudos anteriores sobre o tema, tais como os desenvolvidos por McGee e Markarian, Wiest, Combe, Frere et al., Oshima, Fendley, e traz um comentário sobre a técnica de RAMPS.

Monitoração e controle

Como já salientado anteriormente, são dois os estágios envolvidos no horizonte de realização de um projeto, o estágio de preparação e o estágio de implementação.

A grande maioria dos modelos acima citados são desenvolvidos para resolver o problema de programação no estágio de preparação. As decisões nesta etapa são feitas baseadas em suposições e julgamentos a priori da disponibilidade e demanda dos recursos.

Contudo na prática, na fase de execução do projeto ao tempo de construção por várias razões operacionais, a disponibilidade de recursos pode não ser suficiente para realizar todas as atividades programadas na fase de planejamento. Sob estas circunstâncias, decisões de campo devem ser tomadas sobre quais atividades devem ser executadas e quais adiadas.

Por outro lado, um modelo efetivo deve incorporar a variabilidade do projeto devido as situações de campo, desempenho da mão-de-obra, condições dos equipamentos, fornecimento de material, condições climatológicas e desempenho administrativo. Segundo Chang (1987), a maior razão para o espaço existente entre a aplicação e a pesquisa, além da dificuldade inerente à natureza combinatorial do problema, é que a maioria dos modelos desenvolvidos não possuem a capacidade de resolver o impacto das várias forças externas, como chuva, atrasos de fornecimento, disponibilidade de recursos, etc. que são inevitáveis nos projetos reais.

Recentemente, várias abordagens para a programação de projetos levam em consideração as incertezas das condições de canteiro, como Levitt e Kunz 1985, Chang 1987, 1990, Mosheli e Nicholas 1990, Hassan e Ayyub 1993, Wu e Hadipriono 1994. Muitos destes modelos são desenvolvidos usando ferramentas de inteligência artificial como os Sistemas Especialistas. Para uma revisão mais detalhada sobre Sistemas Especialistas na administração da construção referir-se a Kostem e Maher (1986), Ashley e Levitt (1987), Quinlan (1987), Adeli (1988), Pham and Pham (1988), Formoso e Brandon (1989), Minkarah e Ahmad (1989), Mohan (1990), CIB-90 (1990), Noronha e Sarma (1991).

Levitt e Kunz (1985) desenvolveram um protótipo baseado em conhecimento que permite programar as atividades a medida que o projeto avança, baseado nos dados e o conhecimento do término das atividades. O modelo recopila a duração do projeto e o caminho crítico substituindo as durações esperadas originalmente para as atividades completadas pelas durações atuais, fornecidas pelo usuário. As durações das atividades restantes são substituídas por valores revisados. Este valores são estimados usando regras heurísticas e representam os efeitos potenciais que os fatores de risco tem sobre as durações e o consumo de recursos das atividades a serem executadas.

Chang (1987), (1990), apresenta uma abordagem de Inteligência Artificial para resolver o problema de prioridade que surge na alocação de recursos em projetos de construção. O modelo por ele proposto, usa as saídas de um sistema especialista, com regras de inferência difusas, para resolver o problema de ordenação.

Um modelo de simulação Monte Carlo é usado por Mosheli e Nicholas (1990) para abordar o problema de progresso e custo de projetos de construção sob incerteza. O modelo usa os dados obtidos no avanço do projeto para prever as durações e os custos das atividades remanescentes, bem como para atualizar a ordem de prioridade de execução das atividades ainda não iniciadas.

Hassan e Ayyub (1993), propõem uma estratégia de controle de atividades baseado em conhecimento com auto-aprendizado difuso que, segundo eles, pode permitir detectar e corrigir variáveis que podem ser reponsáveis por falhas futuras.

Um modelo desenvolvido por Wu e Hadipriono (1994) emprega conceitos de lógica difusa angular para avaliar os impactos de diferentes fatores (como condições de canteiro, desempenho de equipamentos e mão-de-obra, etc) sobre a duração da atividade. O sistema utiliza um software comercial para calcular a programação inicial, e mais tarde, para reprogramar as atividades que tenham os valores das suas durações sido modificadas pelo modelo.

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

Como conclusão da breve revisão bibliográfica acima apresentada, o seguinte pode ser estabelecido:

1. Nenhum dos modelos estudados, aborda a alocação de recursos limitados e o nivelamento deles ao mesmo tempo. Ambos os problemas são tratados em separado. A razão principal para isto, talvez sejam as premissas antagônicas sob as quais eles são fundamentados, pois, se para o problema com limitação de recursos é permitido estender a duração do projeto isto não é aceitável no nivelamento de recursos. Entretanto, pode ser desvantajoso obter programações ótimas, desde o ponto de vista da duração do projeto, a expensas de custos excessivos causados por uma má utilização dos recursos. Por outro lado, muitas vezes é irreal assumir que ao considerar o nivelamento dos recursos, estes são ilimitados. Sempre é possível assumir que, a partir de um certo nível, o custo de obtenção de recursos torna-se infinito, logo estaria-se limitando de alguma forma a sua utilização.

O modelo multi-objetivo proposto por Davis et al. (1992) citado anteriormente, embora considere o nivelamento de recursos em cenários com limitação de recursos, ainda trata o problema da maneira tradicional, ou seja, admite que a restrição dos recursos pode ser relaxada para permitir acelerar atividades. Neste sentido, assume-se que recursos podem ser obtidos até um limite onde o excesso na utilização de cada um deles seja mínima e que reduza a duração do projeto a uma data administrativamente preferível, menor que a ótima calculada considerando as restrições originais.

• Os modelos pesquisados, ao executar uma programação, não levam em consideração a importância relativa dos diferentes tipos de recursos. Tradicionalmente, assume-se que todos os recursos tem igual importância, logo tem a mesma influência na programação resultante.
• Nenhum dos paradigmas desenvolvidos para o problema de programação de projetos com restrição de recursos, estabelece a importância, ou não, de considerar a eficiência da utilização dos recursos como um fator que afeta a qualidade da programação obtida. Comumente os procedimentos desenvolvidos, produzem soluções viáveis gerando sistematicamente o espaço de soluções, avaliando uma função objetivo e escolhendo a melhor. Entretanto, durante qualquer processo de busca, é possível encontrar ordenações diferentes para as atividades que resultem num valor igual para a duração do projeto. Estas soluções são consideradas programações equivalentes em relação a este objetivo, porém, eventualmente com diferentes perfis de utilização de recursos.

Neste sentido, propõe-se um modelo que tenta preencher, na medida do possível, estas lacunas. O modelo heurístico desenvolvido, incorpora características que permitem resolver o problema de programação de projetos com restrição de recursos e múltiplos modos, ao mesmo tempo que a utilização dos recursos empregados é nivelada.

2.10 Conceitos Fundamentais de Algoritmos Genéticos

Segundo Reeves (1993), desde a perspectiva 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 (AG) são uma heurística de busca e técnicas de otimização que imitam a seleção natural e o processo evolutivo biológico. Os AG foram inicialmente desenvolvidos por Holland nas décadas de 60 e 70 e formalmente introduzidos no seu livro Adaptation in Natural and Artificial Systems (Holland 1975). Outros trabalhos pioneiros que complementam estas idéias são os desenvolvidos por De Jong (1975) e Goldberg (1989).

Basicamente, os algoritmos genéticos empregam uma solução candidata (um ponto no espaço de busca) propriamente codificada, denominada cromossomo. Estes cromossomos são agrupados em conjuntos denominados populações. Uma população definida num dado intervalo de tempo é denominada uma geração. Neste contexto, os algoritmos genéticos funcionam através da combinação de pedaços de soluções de uma população, cujas aptidões são determinadas por uma apropriada função de avaliação, de modo que soluções melhores sejam obtidas a cada geração. A manipulação de soluções é feita por elementos, denominados operadores genéticos.

Os algoritmos genéticos diferem das técnicas tradicionais em duas características importantes:

1. a propriedade de paralelismo implícito, que permite analisar e avaliar um conjunto de soluções simultaneamente e não somente, estimar e melhorar uma única solução, e
2. a utilização da codificação de um conjunto de parâmetros ao invés dos próprios parâmetros.

A essas duas características, pode ser adicionado a propriedade de utilização de regras de transição probabilísticas.

Essas propriedades fornecem aos algoritmos genéticos a habilidade de mitigar o problema de mínimos locais e ainda, tratar com sucesso problemas combinatoriais NP-pesados.

A estrutura básica do funcionamento dos algoritmos genéticos pode ser descrita pela seguinte representação em pseudocódigo:

Procedimento ALGORITMO GENÉTICO

começa

Inicializa população P(0);

Avalia P(0);

t = 1;

repete

Seleciona P(t) de P(t-1);

Recombina P(t);

Avalia P(t);

até que a condição de parada seja verdadeira.

termina

A construção de um algoritmo genético para qualquer problema pode ser separado nas seguintes tarefas (Chan e Tansri, 1994):

1. determinação da estrutura de representação,
2. determinação da função de avaliação,
3. determinação do tamanho da população e número de gerações, e
4. determinação dos operadores genéticos e suas probabilidades associadas

Essas tarefas, bem como o conceito esquema, são brevemente descritos a seguir. Ver Goldberg (1989) para uma discussão mais profunda destes conceitos.

2.10.1 Esquema

O principal conceito da teoria dos algoritmos genéticos são os esquemas, os quais podem ser imaginados como a definição de subconjuntos de cromossomos similares, ou hiperplanos no espaço n-dimensional (Reeves, 1993).

Por outro lado, os esquemas contém pontos com valores robustos de aptidão, onde cada ponto (cromossomo) representa uma amostra de numerosos hiperplanos que o contém. O problema é que os hiperplanos corretos, isto é, aqueles que contém boas soluções, não são conhecidos durante a busca, porque senão a solução ótima poderia ser conhecida de antemão. Portanto, os bons hiperplanos devem ser adivinhados a partir das soluções mais aptas, dadas pela amostragem de esquemas durante a busca. (Falkenauer e Bouffouix, 1991).

Os detalhes dos fundamentos matemáticos, comportamentos e principais conclusões sobre os esquemas podem ser encontrados em Holland (1975). Goldberg (1989) e Reeves (1993).

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

Para resolver qualquer problema de otimização usando algoritmos genéticos, é necessário a codificação dos parâmetros do problema numa estrutura que permita representar, de maneira apropriada, as soluções do problema.

A representação depende do problema abordado e não é única, no sentido de que existem muitas formas de codificar soluções. Porém uma vez definida a estrutura mais apropriada para representar a solução do problema, esta codificação deve conter todos os nós de busca e ser única (não empregar mais do que uma).

Tradicionalmente, dois tipos de estruturas de codificação são empregadas:

1. Codificação binária: que representa a solução do problema como uma cadeia de caracteres composta de 0 e 1.
2. Codificação de ordem: onde a solução do problema é representada como uma cadeia de caracteres que guardam uma relação de ordem entre si.

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

Como já salientado, uma das vantagens dos algoritmos genéticos sobre as técnicas tradicionais de otimização é a busca em paralelo de vários nós definidos no espaço de busca. O tamanho da busca em paralelo é denominado tamanho da população, que é igual ao número de representações de soluções do problema a cada geração. O tamanho da população, por ser um problema dependente, necessita ser determinado experimentalmente. Em princípio, se usar populações pequenas corre-se o sério risco de se obter soluções sub-ótimas, enquanto se usar populações grandes incorre-se em severas penalidades computacionais.

Por outro lado, o algoritmo evolui para soluções cada vez melhores, convergindo para algum ponto ótimo após um certo número de gerações. O número de gerações usadas para um problema também é um elemento que necessita ser determinado experimentalmente.

2.10.4 Operadores Genéticos

O papel dos operadores genéticos é criar novos nós de busca no espaço de soluções baseado nos elementos da população atual. Três tipos de operadores podem ser identificados: reprodução, cruzamento e mutação.

Reprodução

A reprodução é um processo de seleção empregado para determinar quais os cromossomos (elementos de uma população) gerarão descendentes que formarão parte da próxima população. Elementos com alto valor de aptidão terão maiores chances de ser selecionados do que aqueles de valores baixos. Portanto, analogamente à seleção biológica natural, os fortes continuarão a viver, os fracos morrerão.

Cruzamento

O operador de cruzamento é considerado o mais importante dos algoritmos genéticos. Ele permite a produção de novas estruturas através do intercâmbio parcial de informações (genes) entre pares de elementos.

Na literatura da área, vários operadores de cruzamento tem sido propostos, entre os quais, três são objetos de maior destaque devido a quantidade de aplicações em que são empregados.

Operador OX (Order Crossover). Este operador começa pela escolha aleatória de dois pontos de corte em cada um dos elementos selecionados. A seção definida entre estes dois pontos é copiada integralmente no descendente. Os lugares restantes são preenchidos usando as informações não repetidas na seção de cruzamento, começando do segundo ponto de corte. Por exemplo, considere os seguintes cromossomos:

Pai 1

h

k

c

e

f

d

b

l

a

i

g

j

Pai 2

a

b

c

d

e

f

g

h

i

j

k

l

que gerarão os seguinte descendentes:

Filho 1

d

e

f

g

h

i

b

l

a

j

k

c

Filho 2

e

f

d

b

l

a

g

h

i

j

k

c

A sequência j, k, c (volta ao início) d, e, f, g, h, i, é o gene contido no segundo pai, começando no segundo ponto de corte. De maneira similar, obtem-se a seqência j, k, c, e, f, d, b, l, a, do segundo filho.

Operador PMX (Partially Mapped Crossover). Este operador também é executado escolhendo aleatoriamente dois pontos de corte. O processo pode ser ilustrado utilizando os mesmos cromossomos do exemplo anterior.

Pai 1

h

k

c

e

f

d

b

l

a

i

g

j

Pai 2

a

b

c

d

e

f

g

h

i

j

k

l

As informações contidas entre estes dois pontos, |b, l, a | e |g,h,i |, são intercambiadas obtendo-se as seguintes representações:

Filho 1'

a

b

c

d

e

f

b

l

a

j

k

l

Filho 2'

h

k

c

e

f

d

g

h

i

i

g

j

Porém, estas duas representações intermediárias são estruturas ilegais porque possuem informações repetidas e algumas outras perdidas. Assim, o passo final é substituir estes genes repetidos mapeando (g, h, i) para (b, l, a) e vice-versa, obtendo as seguintes duas novas estruturas:

Filho 1

i

g

c

d

e

f

b

l

a

j

k

h

Filho 2

l

k

c

e

f

d

g

h

i

a

b

j

Operador CX (Cycle Crossover). O esquema do operador CX é muito diferente dos esquemas OX e PMX mostrados anteriormente. O operador CX executa recombinações de forma que cada gene dos descendentes venham da posição correspondente de qualquer um dos pais.

Dado que este é o operador a ser utilizado na implementação do modelo proposto, o mesmo será mais profundamente discutido na seção 3.3.5 do capítulo seguinte.

Resultados teóricos e empíricos comparando o desempenho dos operadores OX, PMX e CX podem ser encontrados em Goldberg (1989), Oliver et al. (1987) e Chan e Tansri (1994).

Mutação

O papel principal do operador de mutação, é mudar aleatoriamente parte das informações codificadas de um cromossomo para criar novos elementos. Por outro lado, a operação de mutação pode ser empregada para reordenar codificações ilegais, obtendo novas soluções viáveis e legais.

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

Os algoritmos genéticos desde a introdução dos conceitos básicos realizados por Holland vem sendo aplicados a diversas áreas de pesquisa e a situações do mundo real com ótimos resultados.

Segundo Blanchard (1994), a última conferência WCCI'94 (World Congress on Computational Intelligence) acontecida em Orlando FL, USA, apresentou uma série de soluções promissoras a situações reais usando algoritmos genéticos. Blanchard relata o caso da US West, uma companhia regional de telecomunicações do estado do Colorado, que vem utilizando um sistema baseado em AG que permite projetar, em duas horas, redes óticas especializadas, tarefa que levaria seis meses usando especialistas humanos. O sistema produz soluções 10% melhores que os produzidos pelo homem. A companhia estima que o sistema permitirá uma economia de 100 milhões de dólares até o final do século.

AIS (Barcelona, Espanha) usou um sistema baseado em AG e sistemas especialistas para programar os Jogos Paralímpicos de 1992. Enquanto que nas Olimpíadas os atletas são agrupados em duas grandes classes, masculino e feminino, os competidores Paralímpicos são classificados em mais de 100 classes, de acordo às restrições médicas.

Um sistema em desenvolvimento na New Mexico State University deriva imagens faciais de criminosos a partir de testemunhas do crime, usando AG. O sistema tem se mostrado mais efetivo na produção de imagens acuradas de criminosos do que qualquer outra técnica de obtenção de informação de imagens.

No campo de programação de tarefas e de máquina, as aplicações vem crescendo e apresentando um desempenho muito satisfatório. A seguir, algumas publicações mais recentes e relevantes ao desenvolvimento do presente trabalho são brevemente apresentados.

Sponsler (1989), apresenta um sistema protótipo desenvolvido para avaliar a aplicabilidade dos algoritmos genéticos na otimização da programação do telescópio espacial Hubble. Vários operadores genéticos foram testados e o melhor AG foi comparado com um otimizador baseado em Redes Neuronais (RN). Neste caso específico os AG não se mostraram tão eficientes quanto as RN.

Syswerda e Palmucci (1991) reportam a construção de um otimizador para uma aplicação prática de progamação de recursos no laboratório SITS (System Integration Test Station Laboratory) da Marinha Americana para o desenvolvimento do jato F-14.

Falkenauer e Bouffouix (1991), introduzem a técnica de AG para tratar o problema de job shop, apresentando uma codificação apropriada para a questão, e demonstrando o seu desempenho com exemplos de tamanhos como encontrados na realidade.

Lawton (1992), apresenta idéias muito gerais de como usar os algoritmos genéticos ao problema de programação, com tendência para a programação de projeto.

Gupta et al. (1993) abordam o problema n-produtos, uma máquina com o objetivo de minimizar a variância do tempo de fluxo.

Bruns (1993), apresenta um algoritmo genético avançado para a solução de problemas reais de produção. A abordagem é baseada no incremento dos AG com conhecimentos do domínio específico.

Fang, Ross e Corne (1993), descrevem uma abordagem de AG que produz resultados, para problemas de programação job-shop padrão, melhores do que esforços prévios usando esta técnica no mesmo problema. A abordagem também é viável de ser aplicada para tratar o problema de programação do tipo open-shop e reprogramação job-shop.

Gauthier (1993), desenvolveu uma abordagem baseada em AG para o problema de programação da produção em ambiente de flow-shop. Introduz um procedimento de calibração dos parâmetros do algoritmo utilizando raciocínio difuso e sistemas especialistas.

Kim e Lee (1994), desenvolveram uma metodologia para o problema de programação em ambiente job-shop baseada na utilização de AG. A metodologia é empregada como um procedimento iterativo de melhoramento de programações. O algoritmo mostrou-se eficiente para várias instâncias do problema, chegando ao ótimo diversas vezes em tempo computacional razoável.

Finalmente, cabe salientar que ainda é incipiente a pesquisa sobre a aplicabilidade dos algoritmos genéticos ao problema de programação de projetos em geral e, particularmente, muito escassa (insignificante) na área de projetos de construção.