18
2
Problemas de Planejamentos
2.1
Descrição do Problema
Problemas de planejamento são problemas de otimização tipicamente
combinatoriais. A tarefa de planejamento consiste em alocar tarefas ao longo do
tempo que devem ser feitas utilizando um número limitado de recursos,
respeitando diversas restrições e otimizando um ou mais objetivos. Uma tarefa é
dada como completa após a execução de uma seqüência pré-definida de operações
e o resultado final do planejamento consiste em um plano que exibe todas as
tarefas associadas aos instantes iniciais e finais e aos recursos usados para cada
operação. Estas associações de tempo e recurso afetam a qualidade de um
PUC-Rio - Certificação Digital Nº 0116630/CA
planejamento com respeito a critérios como custo, tempo de execução, etc.
Problemas do tipo flow shop são problemas onde todas as diferentes
tarefas são feitas pela mesma seqüência de recursos. Um planejamento é portanto
determinado pela ordem na qual as tarefas são programadas. Em problemas do
tipo job shop, cada tarefa necessita utilizar cada recurso somente uma vez (Bäck
et al, 1997).
A estrutura geral de um problema de planejamento pode ser descrita como
uma quádrupla (R, P, J, C) (Bäck et al, 1997)(Husbands, 1994), onde:
•
R é um conjunto de recursos, por exemplo, máquinas ou pessoal, com
diferentes capacidades funcionais.
•
P é um conjunto de produtos. Cada produto pode ser produzido através de
diferentes procedimentos, chamados planos de processo. Cada plano de
processo consiste em uma seqüência de operações.
•
J é um conjunto de tarefas a serem programadas de acordo com diversas
restrições definidas em C. Para cada tarefa existirá um produto resultante
em P e um tempo de execução para a mesma.
•
C é um conjunto de restrições, por exemplo, relações de precedência ou
restrições de capacidade, que necessitam ser satisfeitas. Normalmente
existem vários tipos diferentes de restrições específicas para cada
aplicação.
19
A qualidade de um planejamento é medida através de uma função objetivo
que associa um valor numérico a um planejamento. Diferentes objetivos podem
ser identificados em um planejamento como, por exemplo, minimizar o tempo de
execução, minimizar os custos de execução, etc. Geralmente, não existe apenas
um único objetivo sendo que em algumas aplicações podemos ter vários objetivos,
algumas vezes conflitantes, como por exemplo minimizar o consumo de energia
elétrica e maximizar o uso de recursos.
Com exceção de alguns casos teóricos de pouca importância prática, o
processo de determinar uma solução ótima para um problema de planejamento
pertence a classe de problemas NP-hard (problemas que não podem ser resolvidos
de forma não-determinística em tempo polinomial). A prática também tem
demonstrado que este tipo de problema representa uma tarefa de extrema
PUC-Rio - Certificação Digital Nº 0116630/CA
dificuldade de solução por especialistas humanos (Bäck et al, 1997).
2.2
Planejamento de Uso de Recursos em Portos de Embarque de
Minério
A otimização de planejamentos de descarga e embarque de minério em
portos constitui um problema extremamente difícil devido a vários aspectos: a
diversidade de tarefas com restrições de precedência; ao grau de complexidade
das regras que envolvem a operação portuária; e a quantidade e diversidade de
recursos que devem ser utilizados para execução das tarefas. Esta seção
exemplifica o funcionamento de um porto real localizado em Vitória – Espírito
Santo que foi usado como base de inspiração para a implementação do estudo de
caso no capítulo 5 que utiliza um porto fictício.
2.2.1
Funcionamento do Porto de Tubarão
O porto de Tubarão é um complexo industrial localizado em Vitória e
controlado pela Companhia Vale do Rio Doce. Este complexo portuário é
responsável pelo embarque anual de cerca de 70 milhões de toneladas de minério
de ferro para exportação e mercado interno.
20
O porto conta com dezenas de equipamentos e recursos diferentes para
fazer a operação de embarque do minério nos navios. Uma pequena lista com uma
breve descrição destes recursos é mostrada a seguir:
Equipamento
Descrição
Local de atracação do navio para embarque de minério. Cada píer tem uma
série de restrições operacionais (as restrições são explicadas em detalhe mais
Píer
adiante). O porto conta com 3 píeres denominados:
•
Píer 1 Norte (P1N)
•
Píer 1 Sul (P1S)
•
Píer 2 (P2)
Neste equipamento é acoplada a composição ferroviária contendo o minério
PUC-Rio - Certificação Digital Nº 0116630/CA
para descarga. O virador de vagões então gira os vagões, dois a dois, fazendo
Virador
com que o minério seja despejado sobre correias transportadoras. O
de Vagão
mecanismo de tração para puxar toda a composição fica no próprio virador,
não necessitando portanto de uma locomotiva para puxá-los a medida que o
minério é descarregado.
Acoplada a uma correia, é responsável por despejar o minério em uma pilha de
Empilhadeira
estocagem. Este equipamento se assemelha a um guindaste e se desloca pelas
áreas do porto sobre pares de trilhos.
Acoplada a uma correia é responsável por retirar minério de uma pilha de
Recuperadora
estocagem em geral para embarque no navio. Este equipamento conta com um
conjunto de pás mecânicas que retiram o minério das pilhas de estocagem.
Carregador de
Acoplado a uma correia, é responsável por despejar o minério nos porões do
Navio
navio. Funcionam de forma semelhante às empilhadeiras.
Correia
Responsável pelo transporte do minério através do porto. Estes equipamentos
Transportadora
Áreas de
Estocagem
são responsáveis pelo tráfego de minério pelo porto.
Estas áreas são usadas para estocar o minério de ferro para embarque. São
divididas em balizas para facilitar o controle, com espaçamento de 10 metros
entre cada uma delas.
Tabela 1 – Lista de recursos do porto
Uma visão geral e bastante genérica da estrutura do porto é mostrada na
figura a seguir:
21
Área A
Virador 1
Virador 2
Virador 3
Virador 4
Empilhadeira
1
Empilhadeira
2
Empilhadeira
3
Empilhadeira
n
Área B
Área C
PUC-Rio - Certificação Digital Nº 0116630/CA
Recuperadora
1
Área D
Área E
Recuperadora
2
Área F
Área G
Recuperadora
3
Área H
Área I
Recuperadora
n
Carregador 1
Carregador 2
Carregador n
Píer 1 Sul
Píer 1 Norte
Píer 2
Figura 1 – Visão geral do porto
No porto utiliza-se com freqüência o conceito de rotas: percursos
completos feitos por uma determinada carga entre dois pontos. Alguns exemplos
de rotas que podem ser citados são: entre os viradores e as empilhadeiras, entre as
recuperadoras e os carregadores de navio e entre áreas distintas. No total existem,
atualmente, cerca de 400 rotas diferentes no porto.
Mensalmente, cerca de 40 navios com capacidades de carga que variam
entre 70.000 e 350.000 toneladas são atendidos pelo porto. Diversos
equipamentos são utilizados também para descarregar o minério que chega via
estrada de ferro no porto e estocá-los em grandes áreas para aguardar a chegada
dos navios que irão transportar este minério. Toda esta operação é controlada e
planejada por um grupo de pessoas com o auxílio apenas de algumas planilhas e
relatórios internos.
Para se compreender melhor a dimensão do problema, deve-se
compreender o funcionamento e a operação do porto. Diariamente, os
planejadores recebem informações atualizadas sobre quais navios se encontram no
22
porto atracados, quais navios estão aguardando a ordem para atracação e quais
navios estão programados para chegar no porto nos próximos dias (com um
horizonte de até 30 dias, ainda que os operadores observem no máximo 7 dias a
frente) além do tipo de carga que cada navio irá transportar. Após o anúncio da
chegada do navio no porto (que não necessariamente corresponde ao momento da
atracação, já que os píeres do porto podem estar todos ocupados neste momento),
o porto tem um limite de tempo, definido contratualmente com a empresa
compradora, para embarcar todo o minério de ferro sem o pagamento de uma
multa (esta multa corresponde a um valor por cada hora excedente do tempo de
embarque). Este limite de tempo é chamado laytime e é contado a partir do
anúncio da chegada do navio no porto até a desatracação do mesmo. Da mesma
forma, caso o porto consiga embarcar todo o minério antes de um período de
tempo também definido em contrato, ele recebe um prêmio da empresa
PUC-Rio - Certificação Digital Nº 0116630/CA
compradora (em geral correspondente a metade do valor da multa).
A partir destas informações e através de reuniões diárias com
representantes da área de produção (responsáveis pelas minas), decide-se quais
cargas serão enviadas através de uma malha de estradas de ferro que partem das
regiões de produção com destino ao porto. Esta decisão deve ser tomada com
antecedência já que, em média, um trem leva 12 horas entre sair da mina e chegar
no porto e, idealmente, deseja-se que quando o navio atraque no píer, todo o
minério destinado a ele já esteja estocado no porto, pronto para embarque. Além
disso, estas decisões devem ser tomadas levando-se em conta a capacidade de
produção das minas.
Os planejadores também decidem, a partir da fila de navios, da disposição
do minério estocado no porto e da disponibilidade de máquinas, em qual píer cada
navio irá atracar. Esta escolha é de fundamental importância e deve obedecer uma
série de premissas e restrições:
•
Cada píer tem um limite operacional pré-definido. Só podem atracar no
píer navios que respeitem estes limites operacionais. Entre outros,
podemos citar o calado máximo do navio (distância entre o fundo do navio
e o fundo do mar quando o navio estiver com a carga completa), o calado
aéreo (air draft – distância entre a altura da lança do carregador e o convés
23
do navio ao atracar), maré (em algumas situações, o navio tem um calado
grande e só pode sair do píer com determinadas condições de maré).
•
Alguns píeres trabalham com dois carregadores de navio ao mesmo tempo
e, portanto podem operar com o dobro da capacidade que um píer com
apenas um carregador de navio. O uso desse píer se torna interessante, por
exemplo, quando se tem um navio com grande quantidade de carga a
transportar.
•
Os navios devem ser atendidos, por força contratual, na ordem em que
chegam no porto e respeitando a capacidade de cada píer. Portanto, navios
muito grandes, que atracam somente no píer 2, têm preferência sobre
navios menores (que podem atracar no píer 1 sul ou no píer 1 norte) para
atracar neste píer (mesmo que estes navios menores tenham chegado
antes). Do mesmo modo, navios de porte médio, que podem atracar no píer
PUC-Rio - Certificação Digital Nº 0116630/CA
1 norte ou no píer 2, têm preferência sobre navios menores (que podem
atracar no píer 1 sul) para atracar neste píer e no píer 2. Finalmente, os
navios que podem atracar em qualquer píer devem sempre atracar na
ordem em que chegam (salvo se houver um navio maior que atenda os
requisitos descritos acima).
Finalmente, é função também dos planejadores reservar áreas de
estocagem de minério nos pátios do porto. Como o espaço é limitado este
planejamento deve ser feito de forma cautelosa para evitar que trens carregando
minério fiquem parados aguardando a liberação de alguma dessas áreas.
Todas as decisões feitas pelos planejadores são tomadas em conjunto com
a equipe responsável pela manutenção dos equipamentos. Esta equipe tenta
negociar com os planejadores períodos de parada dos equipamentos para
manutenção preventiva enquanto os planejadores, por sua vez, tentam encontrar
soluções para poder manter o porto operando sem o equipamento durante o
período de manutenção.
Com a chegada do minério no porto através dos trens, entram em ação os
operadores, responsáveis pelo controle das operações no porto. A primeira tarefa
dos operadores consiste em selecionar qual virador de vagões será responsável por
descarregar os lotes (lotes são conjuntos de 80 vagões e cada trem é em geral
composto de 2 lotes) que chegam no porto. Esta escolha é feita baseada nas rotas
24
disponíveis (compostas pelas correias transportadoras ligadas as empilhadeiras de
minério) e nas áreas nas quais se deseja empilhar o minério. Em alguns casos,
pode ser interessante dividir o lote em dois e descarregar cada metade,
simultaneamente, em dois viradores diferentes. Em outros casos isso pode não ser
interessante ou ainda ser inviável devido as características do minério. Em muitas
situações o trem traz dois lotes de minério que devem ser misturados durante a
descarga (blending) e portanto virados simultaneamente para juntá-los numa parte
mais a frente da rota.
Os
operadores
também
são
responsáveis
por
selecionar
quais
empilhadeiras serão usadas para despejar o minério nas pilhas. Estas escolhas
também não podem ser arbitrárias já que as empilhadeiras operam somente em
determinadas áreas do porto.
Outra tarefa de responsabilidade dos operadores é o embarque do minério
PUC-Rio - Certificação Digital Nº 0116630/CA
no navio. Os operadores precisam verificar as condições de entrada do navio no
píer: se a maré está adequada para entrada ou saída do navio no píer, se o calado
aéreo está adequado (caso não esteja, o navio precisa passar por uma operação de
lastro na qual seus porões são preenchidos com água para diminuir a altura do
mesmo de modo que ele consiga passar pela lança do carregador). O operador
também deve seguir o plano de carga do navio: o plano de carga é passado do
comandante do navio para o operador e contém informações sobre qual a
quantidade de minério deve ser jogada em cada porão e em qual ordem, de modo
a evitar danos ao casco do navio.
Além da grande dificuldade em se operar estes equipamentos de modo a
evitar que ocorram bloqueios, ou seja, que duas tarefas que poderiam ser
executadas simultaneamente tenham que ser executadas individualmente devido a
escolha incorreta das rotas, os operadores ainda devem levar em consideração a
taxa de operação de cada equipamento. Cada equipamento tem uma velocidade de
operação diferente e acoplar equipamentos mais rápidos em outros mais lentos faz
com que se tenha que reduzir a velocidade de operação deste e, como resultado,
tenha-se uma sub-utilização do recurso.
Finalmente, os operadores são responsáveis por tomar as devidas medidas
de contingência em caso de problemas de operação. Em geral, estes problemas
ocorrem devido a quebra de equipamentos durante a operação. Dependendo do
tempo estimado para o conserto do equipamento, os operadores podem decidir
25
entre aguardar ou proceder, caso seja possível, com um plano alternativo de
operação.
Tanto os operadores como os planejadores trabalham desta forma
almejando alguns objetivos comuns (e muitas vezes conflitantes). Dentre eles,
PUC-Rio - Certificação Digital Nº 0116630/CA
pode-se destacar:
•
Minimizar a multa por sobrestadia do navio no porto;
•
Minimizar o tempo de espera dos vagões na descarga;
•
Minimizar a quantidade de minério estocada no porto;
•
Minimizar a necessidade de recircular o minério entre áreas;
•
Minimizar a quantidade de pilhas de estocagem de minérios;
•
Maximizar o uso de simultâneo de recursos.
Pode-se notar pela descrição dada acima que existe uma necessidade de se
planejar as tarefas numa determinada seqüência de modo a se ter as informações
necessárias para se planejar a tarefa subseqüente. Esta seqüência é mostrada
através do diagrama a seguir:
26
Atracação
Abertura de Pilhas
Planejamento de
Lotes
Descarga de
Lotes
PUC-Rio - Certificação Digital Nº 0116630/CA
Embarque
Desatracação
Figura 2 – Seqüência de Planejamento
Ou seja, só é possível planejar a abertura de pilhas após se ter planejado a
atracação do navio (pois é necessário saber qual píer o navio está atracado para se
saber quais áreas têm rotas que podem atender aquele píer). Por sua vez, o
planejamento da produção dos lotes depende da informação de quando a pilha tem
que estar pronta e portanto tem que ser feito depois de planejar as aberturas. A
descarga dos lotes só pode ser feita depois que se souber o planejamento da
produção dos mesmos. O embarque só pode ser realizado depois que se souber
quando os lotes terão sido descarregados e o minério portanto estará disponível. E
finalmente, a desatracação só pode ser feita depois que se souber quando o
embarque terá sido concluído.
Além disso, atracações em cada um dos píeres dependem das
desatracações dos navios que chegaram antes, já que a fila dos navios (que
representa a ordem na qual os navios chegaram no porto) deve ser respeitada.
27
2.3
Modelagem de Soluções por Algoritmos Genéticos
Recentemente várias pesquisas na área de planejamento com o uso de
computação evolucionária (com destaque principalmente para os algoritmos
genéticos convencionais) foram desenvolvidas. Com relação a modelos usando
algoritmos genéticos convencionais, podemos usar representações diretas ou
indiretas (Bagchi et al, 1991). Além disso, as representações indiretas podem ser
classificadas de maneira distinta como independente do domínio e específica ao
problema. Abaixo essas formas de representação são descritas detalhadamente
(Bäck et al, 1997):
•
Representação indireta independente do domínio – a maioria dos
PUC-Rio - Certificação Digital Nº 0116630/CA
algoritmos trabalha com esta representação ou seja, com uma população de
indivíduos onde cada um deles codifica uma possível solução. Como a
representação não identifica diretamente a solução (um planejamento), fazse necessário construir um decodificador que faça o elo entre o indivíduo e
o planejamento que ele representa. É responsabilidade deste decodificador
garantir que o planejamento gerado seja válido. Como não existe nenhuma
informação auxiliar relacionada a características específicas do problema
de planejamento, o algoritmo genético faz uma reprodução cega das
soluções codificadas utilizando operadores genéticos convencionais.
Alguns exemplos deste tipo de representação são:
1. Representação Binária – neste modelo, a solução é representada
por uma cadeia de bits e o algoritmo genético utiliza-se de
operadores genéticos convencionais como, por exemplo, o
crossover de um ponto. As diferenças nesta abordagem são
encontradas em relação ao significado de cada bit. Pode-se utilizálos, por exemplo, para representar a hora de término de cada tarefa
sendo que cada horário é representado por um inteiro binário
(Cleveland & Smith,1989).
2. Representação de Seqüência de Tarefas – neste caso, a lista de
todas as tarefas que devem ser planejadas são representadas como
um indivíduo. A ordenação da lista representa de algum modo (em
28
geral através de uma lista de prioridades) a ordem na qual as
tarefas devem ser colocadas no planejamento. Deste modo, o
problema
passa
a
ser
semelhante
a
um
problema
de
seqüenciamento como, por exemplo, o problema do caixeiroviajante (Travelling Salesman Problem – TSP). O algoritmo
genético, portanto se encarrega de gerar novas permutações desta
lista
de
tarefas.
Várias
abordagens
se
utilizaram
desta
representação (na maioria dos casos para problemas do tipo flow
shop)
(Biegel
&
Davern,
1990)(Bierwirth,
1993)(Bruns,
1992)(Cleveland & Smith, 1989)(Lawton, 1992)(Syswerda, 1991).
Vários operadores foram também desenvolvidos sendo que os
decodificadores variavam dos mais simples a sistemas baseados em
conhecimento.
PUC-Rio - Certificação Digital Nº 0116630/CA
3. Representação por Chave Aleatória – o planejamento é codificado
através do uso de números aleatórios. Estes valores são usados
como chaves de ordenação para decodificar a solução. Cada tarefa
está associada a uma posição na representação e o planejamento
pode ser gerado ordenando-se as chaves aleatórias de modo que as
tarefas são seqüenciadas na ordem final das chaves (Bean, 1994).
•
Representação indireta específica ao problema – neste tipo de
representação, algum ou todo o conhecimento sobre o problema
investigado é representado nos indivíduos. De modo a trabalhar
corretamente sobre a representação expandida, o algoritmo genético
precisa de novos operadores genéticos, dependentes do domínio do
problema. De qualquer modo, ainda se faz necessário o uso de um
decodificador capaz de gerar soluções viáveis a partir dos indivíduos. Um
exemplo deste tipo de ordenação é descrito abaixo:
1. Representação por Lista de Preferência – baseado numa
representação que especifica uma lista de preferência para cada
equipamento. Esta lista contém todas as tarefas a executar mais os
elementos “espera” e “não operando”. Ela é interpretada como um
indicador de qual tarefa um determinado equipamento irá executar
preferencialmente em um determinado momento, ou se este
29
equipamento deverá permanecer em espera ou parado. O operador
de crossover troca listas de preferências entre diversos indivíduos e
o operador de mutação reordena o conteúdo da lista de preferência
(Davis, 1985).
•
Representação direta – neste tipo de representação, o próprio planejamento
como um todo é usado como um indivíduo. Este planejamento deve ser
viável e toda informação relevante para descrever de forma única um
planejamento em particular, deve estar incluída na representação. O
decodificador não se faz mais necessário neste tipo de representação e o
algoritmo genético é o único método que realiza a busca já que, a
informação no indivíduo engloba todo o espaço de busca pesquisado e
operadores genéticos particulares ao problema são necessários. Um
exemplo deste tipo de representação é descrito abaixo:
PUC-Rio - Certificação Digital Nº 0116630/CA
1. Representação por Lista de Tarefas-Máquinas-Início – nesta
representação um planejamento é representado por uma lista de
tarefas onde para cada tarefa é designada uma máquina e um
instante de início de execução. Os operadores genéticos selecionam
diversos instantes iniciais de execução para gerar os filhos,
ajustando estes tempos conforme a necessidade de modo a produzir
sempre planejamentos válidos (Kanet & Sridharan, 1991).
No próximo capítulo é apresentado um breve resumo sobre Algoritmos
Genéticos, enfatizando a sua aplicação em problemas como o do caixeiro viajante,
que admitem solução por representação de cromossoma baseada em ordem, muito
empregada em problemas de planejamento de um modo geral, e também utilizada
nesta pesquisa.