Home   |   Structure   |   Research   |   Resources   |   Members   |   Training   |   Activities   |   Contact

EN | PT

EuPTCEEx0874-51612003000200005

EuPTCEEx0874-51612003000200005

variedadeEu
Country of publicationPT
colégioEx-Tech-Multi Sciences
Great areaExact-Earth Sciences
ISSN0874-5161
ano2003
Issue0002
Article number00005

O script do Java parece estar desligado, ou então houve um erro de comunicação. Ligue o script do Java para mais opções de representação.

Um algoritmo genético para o problema do sequenciamento de projectos com recursos limitados

Introdução

O problema do sequenciamento de projectos com recursos limitados RCPSP pode ser descrito da seguinte forma: um projecto consiste num conjunto de actividades J = {0, 1, 2, ..., n, n+1} a sequenciar. As actividades 0 e n + 1 são fictı́cias, têm duração nula e correspondem ao inı́cio e fim do projecto. As actividades estão interrelacionadas por dois tipos de restrições: Restrições de precedência que implicam que cada actividade j só pode ser sequenciada após todas as suas actividades precedentes, Pj , terem sido concluı́das.

Restrições de capacidade que implicam que uma actividade só pode ser sequenciada se houverem recursos disponı́veis.

No problema RCPSP existem K tipos de recursos, representados pelo conjunto K ={1,...,k}.

Cada actividade tem uma duração definida por p j . Entre os instantes de inı́cio e de fim, cada actividade j necessita de r j,k de cada recurso k e não pode ser interrompida. Cada tipo de recurso dispõe de uma capacidade limitada R k em qualquer instante. Os parâmetros p j , r j,k e Rk são determinı́sticos; para as actividades de inı́cio e fim do projecto p 0 = p n+1 =0 e r 0,k = r n+1,k =0 para qualquer recurso k . A resolução do problema do RCPSP consiste em determinar os tempos de conclusão de cada actividade respeitando as relações de precedência e capacidade disponı́vel de cada recurso, por forma a que a duração total do projecto makespan seja minimizada.

Para ilustrar o problema RCPSP, descreve-se na Figura 1, um exemplo com K =2 recursos e n=6 actividades. Os limites de capacidade dos recursos 1 e 2 são respectivamente 4 e 2.

Para este problema foi obtida uma duração total de 15 unidades de tempo. A Figura 2 ilustra a utilização dos dois recursos para o plano final obtido.

Considere-se que F j representa o tempo de fim da actividade j . Um plano pode ser representado por um vector de tempos de fim das actividades (F1 , F2 , ... , Fn ). O conjunto de actividades que estão em processamento no instante t designam-se por actividades activas em t , A(t).

A função objectivo (1) minimiza o tempo de fim da última actividade, designada pela actividade n + 1, do projecto, minimizando a duração total do projecto. As restrições (2) impõem as relações de precedência entre actividades e as restrições (3) limitam para cada recurso k que as actividades em processamento não excedem a capacidade disponı́vel. Finalmente (4) define as variáveis de decisão.

2

Revisão da Literatura

Na área dos algoritmos óptimos tem sido proposto por vários autores um vasto conjunto de abordagens utilizando a técnica do Branch and Bound, salientam-se as contribuições de Demeulemeester e Herroelen (1997), Sprecher (1997), Brucker et al. (1998), Klein e Scholl (1998 a,b), e Mingozzi et al. (1998).

Blazewicz et al. (1983) demonstram que o problema RCPSP, uma generalização do problema clássico do jobshop o qual pertence classe de problemas tipo NP-hard, justificando assim o indispensável recurso a procedimentos baseados em heurı́sticas para a resolução de problemas reais em tempo útil.

As heurı́sticas que têm vindo a ser utilizadas para a resolução do problema do RCPSP pertencem a uma das duas classes: a classe dos métodos baseados em regras de prioridade ou a classe das abordagens baseadas em meta heurı́sticas, Kolisch e Hartmann (1999).

Os métodos baseados em regras de prioridade vão construindo um plano seleccionando sucessivamente actividades de um conjunto de actividades disponı́veis até que todas as actividades estejam sequenciadas. Estes métodos são controlados tanto pelos esquemas de sequenciamento como pelas regras de prioridade. As regras de prioridade são utilizadas para estabelecerem a ordem pela qual as actividades são seleccionadas e sequenciadas. Nesta classe salientam-se as contribuições de Alvarez-Valdes e Tamarit (1989), Boctor (1990), Cooper (1976, 1977), Davis e Patterson (1975), Lawrence (1985), Kolisch (1996) e Kolisch e Hartmann (1999).

Os métodos baseados em meta-heurı́sticas começam com uma solução inicial e tentam melhorá-la. A melhoria de uma solução obtida transformando uma ou várias soluções noutras.

Os métodos que têm vindo a ser utilizados são os algoritmos genéticos, simulated annealing e o pesquisa tabu. Nesta classe salientam-se as contribuições de Baar et al. (1998), Bouleimen e Lecocq (1998, 2002), Hartmann (1998), Kolisch e Hartmann (1999). De referir ainda as revisões de literatura nos trabalhos de Herroelen et al. (1998), Brucker et al. (1999), Klein (1999) e Kolisch e Padman (2001).

3

Tipos de Sequenciamento

Existem os seguintes tipos de sequenciamentos:

Sequenciamento Semi-activo: um sequenciamento admissı́vel que assegura que cada actividade iniciada o mais cedo possı́vel (isto , não existem tempos de inactividade desnecessários).

Sequenciamento Activo: um sequenciamento admissı́vel que assegura que nenhuma actividade pode ser iniciada mais cedo sem provocar um atraso noutras actividades ou violar as restrições tecnológicas ou de recursos. Os sequenciamentos activos formam um subconjunto dos semi-activos, isto , um sequenciamento activo necessariamente semi-activo. De notar que a solução óptima pertence ao subconjunto dos activos.

Sequenciamento Não-Atrasado: um sequenciamento admissı́vel que assegura que nenhum recurso fica inactivo quando pode iniciar o processamento de alguma actividade.

Estes sequenciamentos fazem parte do conjunto dos activos, logo, também são semiactivos.

Neste artigo utilizam-se sequenciamentos activos parametrizados de acordo com Gonçalves e Beirão (1999). Este tipo de sequenciamentos permite apenas considerar sequenciamentos na qual as actividades são atrasadas no máximo até um valor prédefinido.

Esquemas de Geração de Planos

Os esquemas de geração de planos (Schedule Generation Schemes, SGS) são a parte nuclear das heurı́sticas para a geração de soluções do problema do RCPSP. O SGS constrói um plano baseado numa estratégia de programação para a frente (forward planning), isto , cada actividade só sequenciada após todas as suas predecessoras estarem concluı́das.

Existem dois tipos de SGS: SGS Série - baseado no incremento do número de actividades programadas.

SGS Paralelo - baseado no incremento do tempo; Seguidamente descrevem-se estes dois tipos de sistemas de geração de planos.

4.1

SGS Série

O SGS Série consiste em 1 ,...,n estágios, em cada um dos quais sequenciada uma actividade tendo em conta as relações de precedência das actividades e a capacidade dos recursos.

Cada estágio tem associado dois conjuntos. O conjunto das actividades sequenciadas S g , e o conjunto das actividades disponı́veis para sequenciamento Dg = {j J \ Sg | Pj Sg } .

Note-se que a reunião dos conjuntos Sg e Dg não representa todas as actividades J do problema dado que existem actividades que ainda não estão disponı́veis, designadas por actividades nãodisponı́veis, que não podem ser sequenciadas no estágio g porque nem todas as suas actividades predecessoras foram sequenciadas. Seja RDk (t) = Rk (t)

X

rj,k

j A((t))

a capacidade disponı́vel do recurso k no instante t e seja CFg = {Fj | j Sg } o conjunto de todos os tempos de fim das actividades já sequenciadas.

O pseudo-código do procedimento SGS Série pode ser descrito da seguinte forma:

Inicialização : F0 = 0, S0 ={0}, Para g=1 até n Repetir { Calcular Dg , Fg , RD k (t) (para todos os recursos k e todos os tempos de fim em CF g ) Seleccionar uma actividade j Dg Determinar o tempo de fim mais cedo da actividade j ignorando a disponibilidade de recursos F M Cj = M axl Pj {Fl } + pl Determinar o tempo de fim da actividade j considerando a disponibilidade de recursos Fj = M in { t [F M Cj pj , ] CFg | rj,k RDk (τ ) , k K, τ [t , t + pj [ CFg } + pj Actualizar o conjunto das actividades já sequenciadas Sg = Sg−1 { j} }

O makespan do projecto será dado pelo maior dos tempos de fim das actividades predecessoras da actividade n + 1 , isto , Fn+1 = M axl Pn+1 {Fl } .

A inicialização do algoritmo começa por atribuir actividade j=0 um tempo de conclusão igual a zero. No inı́cio de cada estágio, o conjunto das actividades disponı́veis D g , o conjunto dos tempos de fim Fg , e as capacidades disponı́veis RD k (t), para cada tempo de fim t são calculados. De seguida seleccionada uma actividade j do conjunto das actividades disponı́veis Dg .

O tempo de fim de cada actividade j calculado considerando o tempo de fim mais cedo - FMC j -, das suas actividades predecessoras e a disponibilidade de recursos.

Com vista a ilustrar a aplicação do SGS Série apresenta-se na tabela 1 o plano obtido pelos sucessivos estágios.

4.2

SGS Paralelo

O esquema de geração de planos baseado no SGS paralelo, que apenas constrói sequenciamentos nãoatrasados (Kolisch (1996)), utiliza o incremento de tempo. Para cada estágio g, existe um tempo de sequenciamento tg . As actividades que já foram sequenciadas até ao estágio g, pertencem ao conjunto Cg ou ao conjunto Ag . O conjunto Cg representa todas as actividades que foram concluı́das até tg Cg = {j J|Fj tg }. O conjunto das actividades activas (actividades em curso) representado por Ag .

As actividades que estão disponı́veis para serem seleccionadas e sequenciadas estão representadas no conjunto de actividades Dg . A capacidade disponı́vel de cada recurso k no instante tg dada por RD k (tg ).

O pseudo-código do procedimento SGS Paralelo pode ser descrito da seguinte forma:

Inicialização: g=0, tg =0, A0 ={0}, C0 ={0}, RD k (0)= Rk Enquanto |Ag U Cg

|

<= n Repetir

{ Passo 1: g := g + 1 tg = M inj Ag {Fj } Calcular Cg , Ag , RD k (tg ), Dg Passo 2: Enquanto Dg

6= {} Repetir

{ Seleccionar j

Dg

Fj = t g + p j Calcular Ag , RD k (tg ), Dg } }

O makespan do projecto será dado pelo maior dos tempos de fim das actividades predecessoras da actividade n + 1, isto , Fn+1 = M axl Pn+1 {Fl } .

Na inicialização do SGS Paralelo o tempo de sequenciamento tg 0, atribui-se a actividade de inı́cio aos conjuntos C0 e A0 e calcula-se a capacidade disponı́vel para cada recurso k. Cada estágio, consiste em dois passos: 1. Determinação do próximo tempo de sequenciamento tg e dos conjuntos associados Cg , Ag , Dg e RD k (tg ).

2. Sequenciamento das actividades disponı́veis para as quais existem recursos k necessários.

De observar que este esquema de geração de planos pode ter menos de n estágios, mas tem exactamente n actividades a seleccionar e sequenciar.

A tabela 2 ilustra a aplicação do SGS paralelo ao exemplo da Figura 1. A Figura 2 representa a respectiva utilização de recursos.

5

Nova Abordagem

A nova abordagem apresentada neste artigo combina um algoritmo genético com um procedimento que gera sequenciamentos activos parametrizados. Em termos gerais a abordagem consiste nas seguintes duas fases: A atribuição de prioridades e tempos de espera às actividades. Esta fase realizada com recurso ao algoritmo genético que define e faz evoluir (melhorar) as respectivas prioridades e tempos de espera; A construção do plano. Esta fase faz uso das prioridades e tempos de espera definidas na primeira fase e recorrem a um esquema de geração de planos do tipo paralelo modificado para construir planos activos parametrizados.

Nas secções seguintes serão apresentados detalhes da abordagem.

5.1

Sequenciamentos Activos Parametrizados

Dado que o conjunto dos planos activos extremamente elevado e que inclui um elevado número de soluções de má qualidade (devido aos grandes tempos de espera permitidos), optou-se por reduzir o número de planos activos considerados na pesquisa, limitando apenas àqueles que não excedem determinado valor do tempo de espera, designados planos activos parametrizados.

Embora a utilização de planos activos parametrizados seja vantajosa na eliminação de soluções de má qualidade poderá eventualmente excluir o espaço que contém a solução óptima.

Activos Parametrizados Semi-Activos Activos NãoAtrasados

1 × Factor de Espera

Semi-Activos Activos NãoAtrasados

2 × Factor de Espera

Figura 3: Espaço de soluções do algoritmo de geração de sequenciamentos.

Com vista a reduzir a possibilidade de exclusão da solução óptima do espaço de soluções, optouse por escolher tempos de espera máximos relativamente elevados, isto , 1.5 × duração da actividade mais longa (ver §5.2.1) .

A Figura 3 mostra onde se situa, relativamente às classes de sequenciamentos Semi-Activos, Activos e Não-Atrasados, o espaço de soluções que o algoritmo desenvolvido permite gerar.

O espaço de soluções que o algoritmo permite gerar, pode ser mais ou menos abrangente, dependendo de um factor (tempo) de espera.

Na geração de sequenciamentos não-atrasados são consideradas disponı́veis para sequenciamento no instante t todas as actividades que possam ser iniciadas nesse instante. No sequenciamento activo parametrizado foi incorporado um factor de espera que permite considerar como disponı́veis para sequenciamento no instante t, todas as operações que possam ser iniciadas até t + factor espera.

variação do factor de espera corresponde uma diminuição ou aumento do espaço de soluções (ver Figura 3). Um valor nulo para o factor de espera significa que o espaço de soluções está restrito aos sequenciamentos não-atrasados.

5.2

Algoritmo Genético

Os algoritmos genéticos são baseados nos mecanismos de selecção natural e da genética e foram introduzidos por Holland (1975). Os algoritmos genéticos são normalmente usados para resolver problemas de pesquisa e optimização.

Na teoria da evolução natural sobrevivem os indivı́duos mais aptos. A cada indivı́duo (cromossoma) de uma população está associado um conjunto de genes, que representa o seu valor ou mérito. Quanto mais apto estiver um indivı́duo para a sobrevivência maior será o seu mérito.

Os mecanismos naturais de preservação e evolução de uma população são a sua reprodução e mutação. A reprodução tem por base o cruzamento (crossover) genético. Através de mutação dos indivı́duos possı́vel incluir diversidade numa espécie.

Os algoritmos genéticos utilizam os seguintes mecanismos: Selecção: consiste em seleccionar alguns dos melhores cromossomas para a população seguinte; Cruzamento: consiste no cruzamento de cromossomas preferencialmente de elevado mérito; Mutação: consiste em incluir diversidade numa população através da alteração dos genes de alguns cromossomas.

Seguidamente apresenta-se o pseudo-código utilizado no algoritmo genético:

Algoritmo Genético { Gerar população inicial S t Avaliar população S t Enquanto critério de paragem não satisfeito Repetir { Seleccionar elementos de S t a colocar em S t+l Cruzar elementos de S t e colocar em S t+l Mutação de novos elementos e colocar em S t+l Avaliar nova população S t+l St = S t+l } }

5.2.1

Representação Cromossómica e Descodificação

O algoritmo genético utilizado usa chaves aleatórias (random keys) como método de representação (codificação) de soluções em vez da codificação binária tradicional. Esta metodologia foi proposta por Bean (1994) e consiste na atribuição de números aleatórios, compreendidos entre 0 e 1, aos genes que constituem os cromossomas.

Na abordagem apresentada neste artigo cada cromossoma (solução) composto por 2n genes onde n representa o número de actividades.

Cromossoma = ( gene1, ... , genen , genen+1, ... , gene2n )

Prioridades

Tempos de Espera

Os primeiros n genes são usados para obter as prioridades de cada actividade de acordo a seguinte expressão: Prioridade j = Gene j .

Os genes de n+1 até 2n são usados para determinar os factores de espera de cada actividade jsegundo a seguinte expressão: fEspera j =Gene n+j × 1.5 × MaxTempoProc na qual MaxTempoProc o maior tempo de processamento das actividades.

5.3

Estratégia Evolutiva

Inicialmente gerada aleatoriamente uma população de cromossomas. Esta população será posteriormente transformada através da aplicação dos operadores genéticos. A reprodução conseguida usando uma estratégia elitista, Goldberg (1989) na qual os melhores indivı́duos de uma população são copiados para a geração seguinte. A vantagem desta estratégia garantir que a melhor solução vá melhorando monotonicamente de geração para geração.

O operador de cruzamento adoptado do tipo uniforme parametrizado, Spears e DeJong (1991), em vez dos tradicionais cruzamentos simples, duplo ou multi-ponto. Neste tipo de cruzamento são escolhidos aleatoriamente dois cromossomas da população (incluindo os cromossomas que foram seleccionados para pertencerem geração seguinte) para darem origem a um cromossoma filho, e para cada gene determinado qual o progenitor que contribuirá com o seu valor para o gene do filho. definida uma probabilidade de escolha, e para cada gene gerado um número aleatório entre 0 e 1. Se o número gerado for inferior ou igual probabilidade de escolha, escolhido o gene do primeiro progenitor, caso contrário será escolhido o do segundo progenitor. Suponhamos que a probabilidade de escolha 0.8, a Figura 4 exemplifica o processo de cruzamento de dois cromossomas: O operador de mutação, em vez da mutação gene a gene com baixa probabilidade, emprega o conceito de imigração. Em cada geração são gerados novos membros a partir da mesma distribuição utilizada para a geração da população inicial. Este processo evita a convergência prematura de uma população.

A Figura 5 exemplifica o processo de transição de uma geração para a seguinte.

Cromossoma Progenitor 1 Cromossoma Progenitor 2 Valores gerados

0,32 0,77 0,53 0,85 0,26 0,15 0,91 0,44 0,58 0,89 0,72 0,25 < 0.8 > 0.8 < 0.8 < 0.8 0,32 0,15 0,53 0,85

Cromossoma Filho

Figura 4: Exemplo de um cruzamento.

Geração Actual

Geração Seguinte Copia Melhores

Cruzamento

Gerados Aleatóriamente

Figura 5: Transição de geração.

Slide - 12

Testes de Desempenho

Este capı́tulo apresenta os resultados obtidos pelo algoritmo GAPS (Genetic Algorithm for Project S cheduling). Na tabela 3 apresentam-se os resultados comparativos com as heurı́sticas apresentadas em Hartmann e Kolisch (2000).

No estudo comparativo são utilizados os conjuntos de problemas J30, J60 e J120 de Kolisch et al. (1998). Os conjuntos J30 e J60 consistem cada em 480 problemas e o conjunto J120 consiste em 600 problemas. Cada problema constituı́do por um projecto que tem 30, 60 e 120 actividades respectivamente para os conjuntos de problemas J30, J60 e J120.

Na resolução destes problemas o algoritmo genético usou a seguinte configuração: População = 2 x número de actividades do problema 10% de selecção elitista 20% de mutação 0.7 para a probabilidade de cruzamento 10 sementes Critério de minimização: makespan Critério de paragem: 1000 gerações A tabela 3 apresenta os resultados experimentais obtidos para os problemas dos conjuntos J30, J60 J120. Nos problemas do conjunto J30 a medida utilizada foi o desvio médio percentual do makespan em relação ao valor óptimo (DOP T ). Nos problemas dos conjuntos J60 e J120 foram utilizados o desvio médio percentual em relação melhor solução obtida pelas outras heurı́sticas (DM S ) e o desvio médio percentual em relação a um limite inferior calculado por Hartmann e Kolisch (2000) (DLI ).

Para os problemas do conjunto J30 o algoritmo GAPS obteve DOP T = 0.10. Este valor inferior em cerca de 57% relativamente ao valor DOP T = 0.23 obtido pelo algoritmo que mais se aproxima (SA-activity list).

Para os problemas do conjunto J60, o algoritmo GAPS obteve DM S = 0.26 e DLI = 11.62. De notar que estes valores são inferiores em 21% e em 2% respectivamente em relação aos valores DM S = 0.33 e DLI = 11.89, obtidos pelo algoritmo que mais se aproxima (GAactivity list).

Para os problemas do conjunto J120, o algoritmo GAPS obteve DM S = 0.58 e DLI = 36.10. De notar que estes valores são inferiores em 13% e em 2% respectivamente em relação aos valores DM S = 0.67 e DLI = 36.74, obtidos pelo algoritmo que mais se aproxima (GAactivity list).

O algoritmo foi implementado em Visual Basic 6.0 e os testes computacionais foram realizados num computador com sistema operativo Windows Me e um processador AMD a 1.33 GHz. Os tempos médios para 1000 gerações por tipo de problema foram:

Tabela 4: Tempo Médio de CPU para 1000 Gerações.

Tipo de Problema Tempo Médio para 1000 Gerações

7

J30 8.78 s

J60 34.78 s

J120 164.35 s

Conclusões

Neste artigo apresenta-se um algoritmo genético para o Problema do Sequenciamento de Projectos com Recursos Limitados RCPSP. A representação cromossómica utilizada baseia-se em chaves aleatórias. O sequenciamento das actividades feito com recurso a uma heurı́stica baseada em prioridades definidas pelo algoritmo genético. A heurı́stica gera sequenciamentos activos parametrizados.

Os testes de desempenho do algoritmo, realizados com base no conjunto de problemas J30, J60 e J120 apresentados em Kolisch et al. (1998), demostram que o algoritmo GAPS obtém um desempenho significativamente superior quando comparado com as heurı́sticas apresentadas em Hartmann e Kolisch (2000).


transferir texto