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).
