A INFLUÊNCIA DA TEMPERATURA INICIAL
NO DESEMPENHO DE UM MÉTODO HÍBRIDO
ALGORITMO GENÉTICO - SIMULATED
ANNEALING PARA A PROGRAMAÇÃO
FLOW SHOP PERMUTACIONAL
Walther Rogério Buzzo
Mestrado em Engenharia de Produção/Escola de Engenharia de São Carlos - USP
Av. Dr. Carlos Botelho, 1465. CEP 13560-250 - São Carlos/SP
João Vitor Moccellin
Escola de Engenharia de São Carlos - USP. SEM - Engenharia de Produção
Av. Dr. Carlos Botelho, 1465. CEP 13560-250 - São Carlos/SP
ABSTRACT
Flowshop scheduling for minimizing the makespan is one of the most well-know problems in the
area on scheduling. In the last decades, various approaches have been proposed to solve this
problem. Recently, some heuristics approaches were applied to the flow shop scheduling. In this
paper, a hybrid metaheuristic is presented for solving the m-machine, n-job flow shop scheduling
problem with the objective of minimizing the makespan. The influence of a parameter named Initial
Temperature on the hybrid metaheuristic performance is evaluated by computer simulations. The
proposed method is based on the combination of two approaches: Genetic Algorithm and Simulated
Annealing. The Genetic Algorithm starts with an initial population generated by efficient
scheduling heuristics and crosses over them. Following, Simulated Annealing improves those
sequences. The cycle repeats until stop rule. Simulated Annealing has the ability to escape from
local optima by accepting sequences that momentarily deteriorate the objective function and, due
this advantage, it has a great potential for obtaining high quality solutions. The mechanics of
Genetic Algorithm is simple: only copying string and swapping of string by three genetic operators
- reproduction, crossover and mutation. The conception of method is based on quality of solution
and computation effort.
KEYWORDS: production scheduling, flow shop, hybrid metaheuristics.
RESUMO
A programação em ambiente Flow Shop com o objetivo de minimizar o makespan é um dos mais
conhecidos problemas na área de programação de operações em máquinas. Nas últimas décadas,
várias abordagens foram propostas para resolver o problema. Recentemente, algumas abordagens
heurísticas foram aplicadas na programação de operações Flow Shop. Neste artigo, é apresentado
um metaheurístico híbrido para resolver o problema de operações Flow Shop de m máquinas e n
tarefas, com o objetivo de minimizar o makespan. É estudado também, a influência do parâmetro
Temperatura Inicial na performance do metaheurístico híbrido, através de simulações de
computador. O método proposto é baseado na combinação de duas abordagens: Algoritmo Genético
e Simulated Annealing. O Algoritmo Genético tem início com uma população gerada por métodos
heurísticos eficientes, fazendo o cruzamento entre os indivíduos desta população. Em seguida, o
Simulated Annealing melhora estas seqüências. O ciclo se repete até uma condição de parada.
Simulated Annealing tem a capacidade de escapar de ótimos locais aceitando seqüências que
deterioram momentaneamente a função-objetivo e, devido a esta vantagem, ele apresenta um grande
potencial para obter soluções de qualidade. O mecanismo do Algoritmo Genético é simples: ele
apenas copia séries e faz a permutação entre as mesmas através de três operadores - reprodução,
cruzamento e mutação. A concepção do método baseia-se na qualidade da solução e no esforço
computacional.
PALAVRAS-CHAVE: programação da produção, flow shop, metaheurísticos híbridos.
1. INTRODUÇÃO
O problema de programação de operações em ambiente Flow Shop é um problema de
programação da produção no qual cada uma de um conjunto de n tarefas deve ser processada por
um conjunto de m máquinas distintas, tendo o mesmo fluxo de processamento nas máquinas. O
tempo de processamento da tarefa i na máquina j é pij ( i = 1, 2, ..., n; j = 1, 2, ..., m). Quando em
cada máquina a ordem de processamento das tarefas é a mesma, tem-se o Flow Shop Permutacional.
A solução do problema consiste em se determinar dentre as (n!) seqüências possíveis das
tarefas, aquela que otimiza alguma medida de desempenho, geralmente associada ao fator tempo.
Neste trabalho adota-se como função-objetivo a Duração Total da Programação (makespan),
que é o intervalo de tempo entre o início da execução da primeira tarefa na primeira máquina e o
término de execução da última tarefa na última máquina.
O problema em questão é classificado como NP-hard, de modo que pode ser resolvido
eficientemente de maneira ótima somente nos casos de pequeno porte. Um extenso esforço de
pesquisa tem sido dedicado ao problema nas últimas décadas. Técnicas de Programação
Matemática, tais como Programação Linear Inteira (SELEN & HOTT [26]) e técnicas de
enumeração do tipo branch-and-bound (IGNALL & SCHRAGE [8]) têm sido empregadas para a
solução ótima do problema. Entretanto, tais técnicas não são eficientes em termos computacionais,
em problemas de médio e grande porte. Recentemente, graças ao aperfeiçoamento dos
computadores, alguns métodos heurísticos foram aplicados para a solução de tais problemas.
Um método heurístico não pode garantir a qualidade da solução, sendo aceitável se os
resultados forem satisfatórios quanto à proximidade da solução e quanto ao esforço computacional.
Os métodos heurísticos podem ser classificados de várias formas, uma das quais classifica-os em:
(i) Métodos Construtivos - a seqüência adotada como solução do problema é obtida:
• diretamente a partir da ordenação das tarefas segundo índices de prioridade calculados em
função dos tempos de processamento das tarefas: PALMER [21];
• escolhendo-se a melhor seqüência das tarefas a partir de um conjunto de seqüências obtidas
utilizando-se índices de prioridade associados às tarefas: CAMPBELL, DUDEK & SMITH [1];
• a partir da geração sucessiva de seqüências parciais das tarefas (sub-seqüências) até a
obtenção de uma seqüência completa através de algum critério de inserção de tarefas: NEH
(NAWAZ, ENSCORE & HAM [18] ).
(ii) Métodos Melhorativos - obtém-se uma solução inicial e posteriormente, através de algum
procedimento iterativo, geralmente envolvendo trocas de posições das tarefas na seqüência, buscase obter uma seqüência das tarefas melhor que a atual quanto à medida de desempenho adotada.
Nesta categoria destacam-se os procedimentos de busca em vizinhança, como por exemplo
DANNENBRING [2]. Recentemente, foram desenvolvidos métodos de busca em vizinhança de
maior complexidade (Busca Tabu e Simulated Annealing) que têm sido alvo de gradativo interesse
na comunidade científica em função de aplicações bem sucedidas reportadas na literatura.
Exemplos de aplicações dessas técnicas são encontrados em: ISHIBUCHI, MISAKI &
TANAKA [9]; MOCCELLIN [13]; OSMAN & POTTS [20]; PARK & KIM [22]; WIDMER &
HERTZ [28] e ZEGORDI, ITOH & ENKAWA [29].
Outra técnica do tipo melhorativo - denominada Algoritmo Genético - tem despertado
interesse pela sua capacidade de solução de problemas de natureza combinatorial. REEVES [24]
utilizou do Algoritmo Genético na solução do problema de Programação de Operações Flow-Shop
Permutacional.
2. MÉTODOS METAHEURÍSTICOS HÍBRIDOS
Uma idéia que tem despertado atenção refere-se ao desenvolvimento de métodos
metaheurísticos híbridos utilizando as metaheurísticas Busca Tabu, Simulated Annealing e
Algoritmo Genético. O objetivo é combinar as técnicas preservando suas características de ação
inteligente, de tal forma que o procedimento resultante seja mais eficaz do que qualquer um dos
seus componentes isoladamente.
Na literatura são reportados alguns trabalhos relatando experimentações com variantes ou
combinações desses três métodos, como observado em: FOX [4]; GLOVER, KELLY &
LAGUNA [5]; KIM, NARA & GEN [10]; ROACH & NAGI [25]. No caso específico do problema
de Programação de Operações Flow Shop, tem-se os trabalhos de: DÍAZ [3]; MURATA,
ISHIBUCHI & TANAKA [16] e PIRLOT [23].
O objetivo deste trabalho é propor um novo método metaheurístico híbrido (denominado
HBGASA) que utiliza as metaheurísticas Algoritmo Genético e Simulated Annealing para o
problema de Programação de Operações Flow Shop Permutacional e, posteriormente, avaliar a
influência da TEMPERATURA INICIAL no desempenho do mesmo. O desempenho do HBGASA é
comparado ao desempenho do Algoritmo Genético puro e do Simulated Annealing puro, tomandose diferentes valores de temperatura inicial.
3. ALGORITMO GENÉTICO
Desenvolvido por HOLLAND [7], o Algoritmo Genético é derivado de uma analogia com o
processo evolucionário de seleção natural. Além de ser uma estratégia diferenciada, pois se baseia
na evolução biológica, o Algoritmo Genético é capaz de identificar e explorar fatores ambientais
(do espaço de soluções) e convergir para soluções ótimas ou aproximadamente ótimas em níveis
globais e em uma grande variedade de problemas.
Na terminologia do Algoritmo Genético, um cromossomo representa uma solução para o
problema em estudo, sendo constituído de um conjunto de genes cada qual representando uma
característica específica do cromossomo. O valor associado à característica de cada gene é
denominado alelo. Uma população é constituída de um conjunto de cromossomos, sendo refeita
(atualizada, renovada) após cada geração. Um elemento fundamental do algoritmo é o operador
genético denominado operador de cruzamento o qual combina dois cromossomos para gerar
cromossomos "filhos" que mantêm certas características básicas dos cromossomos "pais". Além
desse operador, geralmente é considerado um outro denominado operador de mutação, o qual
introduz aleatoriamente transformações ou novas informações em uma população.
Na solução do problema de Programação de Operações Flow Shop Permutacional, um
cromossomo representa uma possível seqüência das tarefas e os genes representam as tarefas. A
especificação do "cenário" em que o Algoritmo Genético deve atuar é de fundamental importância
para a maximização da sua performance, como por exemplo: a determinação da forma de
construção das subpopulações iniciais e dos operadores de cruzamento e mutação que serão
empregados; a freqüência de utilização do operador de mutação, dentre outros.
4. SIMULATED ANNEALING
Técnica recente introduzida por KIRKPATRICK, GELATT & VECCHI [11], o Simulated
Annealing se baseia na idéia de se aplicar o princípio de tratamento térmico (aquecimento e
gradativo resfriamento) para a solução de problemas de natureza combinatorial, podendo ser
considerado um método heurístico melhorativo de busca aleatória na vizinhança.
O Simulated Annealing extrai ao acaso uma solução σ’ na vizinhança da solução atual σ. Se
o valor da função-objetivo da seqüência σ’ for menor ou igual ao valor da função-objetivo da
seqüência atual σ, então σ’ passa a ser a nova solução atual. Caso contrário, σ’ pode se tornar a
nova solução atual de acordo com uma probabilidade dada por:
p(k) = e -∆/T ,
onde:
• ∆ : diferença entre as medidas de desempenho das duas soluções e
• T : parâmetro denominado temperatura.
A metaheurística Simulated Annealing permite, portanto, a mudança de uma solução para
outra na vizinhança com um desempenho inferior quanto à função-objetivo adotada, possibilitando
assim, um movimento contrário a um eventual ótimo local. A temperatura T é geralmente alta nos
estágios iniciais, permitindo mudanças de soluções atuais com desempenho inferior. O valor de T
decresce gradativamente atingindo um valor próximo de zero, de modo que a troca de uma solução
atual só é permitida quando for encontrada uma solução vizinha com desempenho superior.
A aplicação do Simulated Annealing para a solução do problema de otimização requer a
tomada de decisões específicas para cada problema, como a determinação de métodos de geração da
solução inicial; a definição da vizinhança a ser considerada; a porcentagem da vizinhança analisada;
a temperatura inicial; a condição de parada, entre outras.
5. O MÉTODO HÍBRIDO HBGASA
O método híbrido proposto neste trabalho tem como ponto de partida duas soluções iniciais
geradas por dois métodos construtivos de comprovada eficiência/eficácia. O objetivo é melhorar
tais soluções, através de um procedimento que combina as metaheurísticas Algoritmo Genético e
Simulated Annealing. A seleção dos parâmetros utilizados no método é de fundamental importância
na maximização de sua performance. Tais parâmetros são descritos a seguir.
❶
Soluções Iniciais: são fornecidas pelo NEH (NAWAZ, ENSCORE & HAM [18]) e FSHOPH
(MOCCELLIN [13]). No método Simulated Annealing puro que é comparado com o híbrido
HBGASA, a solução inicial é a melhor dentre as fornecidas pelo NEH e FSHOPH.
❷
Vizinhança: foi utilizado o tipo de Vizinhança de Inserção (Shift Neighbourhood), onde uma
seqüência vizinha é obtida da seqüência atual removendo-se uma tarefa de sua posição e inserindo-a
em uma outra posição .
❸
Formas de Busca na Vizinhança: foi empregada a busca parcial aleatória, que consiste no
exame parcial da vizinhança, ou seja, apenas uma parcela Nvp(S) do número total de vizinhos será
avaliada, a qual é gerada aleatoriamente.
A parcela da vizinhança, baseada em NAGANO [17], é dada pelas expressões:
Nvp(S) = p (n - 1)2 , para n ≤ 30
Nvp(S) = p [1741 - 900 exp (-0,04(n - 30))] , para n >30
onde p é um parâmetro obtido experimentalmente no conjunto {0,05; 0,10; 0,15; 0,20; 0,25;
0,30; 0,35; 0,40; 0,45; 0,50; 0,55; 0,60; 0,65; 0,70; 0,75; 0,80; 0,85; 0,90; 0,95; 1,00} e n é
o número de tarefas a serem programadas.
❹
Operador Reprodução: a reprodução é efetuada sobre a população constituída pelas duas
seqüências “pais” e duas seqüências “filhos”. As duas seqüências que apresentarem as menores
durações totais de programação são selecionadas para a aplicação do operador de cruzamento.
❺ Operador de Cruzamento: é responsável pela recombinação das características dos pais durante a
reprodução, permitindo que as próximas gerações herdem tais características. Utilizou-se neste
trabalho, o operador de cruzamento de UM CORTE, detalhado a seguir:
• PASSO 1: Escolha um ponto para se dividir cada pai, em duas subseqüências;
• PASSO 2: A solução filho é gerada através da união de duas subseqüências, uma de cada
pai, na sua posição absoluta;
• PASSO 3: Para evitar a inviabilidade da solução filho, troca-se as tarefas duplicadas por
aquelas que faltam para completar a solução filho.
❻
Operador de Mutação: este operador é necessário para a introdução e a manutenção da
diversidade genética da população. Apesar da sua relativa importância, ele não é utilizado no
método híbrido HBGASA, uma vez que nesse método tal função é realizada pelo procedimento
Simulated Annealing.
Porém, para o Algoritmo Genético puro (a ser comparado com o método híbrido) foram
desenvolvidos 3 operadores de mutação. O mutação 1 consiste em escolher aleatoriamente uma
tarefa e trocá-la de posição com a sua subseqüente. O operador mutação 2 troca aleatoriamente as
posições de duas tarefas quaisquer da seqüência. Por sua vez, o mutação 3 escolhe ao acaso um
ponto para se dividir a seqüência em duas subseqüências, as quais têm suas posições relativas
invertidas. Pode-se notar que os operadores de mutação propostos têm graus de “perturbação”
crescentes. O operador mutação 1 é aplicado toda vez que não houver melhoria na melhor
seqüência até então obtida, após 0,01TNbS(m,n) seqüências sucessivas geradas e avaliadas. O
mutação 2 é utilizado se não houver melhoria após 0,027TNbS(m,n) seqüências sucessivas. O
operador mutação 3, que causa uma maior modificação na seqüência gerada é aplicado após
0,10TNbS(m,n) seqüências sucessivas sem melhoria quanto à melhor solução até o momento
obtida. Os coeficientes 0,01; 0,027 e 0,10 foram estabelecidos em função do “grau de perturbação”
de cada operador e também de forma que não haja a possibilidade de aplicação simultânea de dois
ou dos três operadores.
❼ Temperatura Inicial T1: objeto de estudo do
presente trabalho, a temperatura inicial é um dos
parâmetros sensíveis e experimentais do método híbrido. Com o objetivo de obter o melhor valor
para tal parâmetro, foi estabelecido um conjunto representativo dado por {20, 30, 45, 60, 70}.
❽ Função de Resfriamento F(Tk): no procedimento Simulated Annealing, após cada iteração ocorre
uma diminuição da temperatura conforme a seguinte expressão:
Tk + 1 = Tk / (1 + βTk ), onde:
• Tk = temperatura da k-ésima iteração;
• β é um parâmetro dado pela relação: β = (T1 - TK) / [(K - 1).(T1 . TK)],
sendo: T1 = temperatura inicial; TK = temperatura final e K = número de iterações.
O número de iterações K depende da estrutura do método, puro ou híbrido, sendo uma
função da condição de parada. A temperatura final é adotada igual a 1 (um).
❾
Probabilidade de Aceitação p(k): a probabilidade de aceitação de um “movimento” no
procedimento Simulated Annealing é calculada pela distribuição de Boltzmann, ou seja :
p(k) = exp (-∆ / Tk), onde:
• ∆ = C(σ’) - C(σ);
• σ’: solução “candidata”, extraída da vizinhança da solução atual (corrente);
• σ : solução atual;
• Tk : temperatura na iteração k.
❿ Condição de Parada: o método híbrido HBGASA encerra a busca por melhores soluções após um
número TNbS(m,n) pré-determinado de seqüências avaliadas de acordo com a Tabela 1. Tais
números foram obtidos por experimentação prévia : Para cada classe de problema (número de
máquinas m, número de tarefas n), o valor TNbS(m,n) corresponde ao número médio de seqüências
avaliadas utilizando-se o método heurístico de Busca Tabu FShop.TS5 (MOCCELLIN &
NAGANO [14]).
TABELA 1 - Condição de Parada
Número de
(máquinas, tarefas)
(4, 20)
(4, 30)
(4, 40)
(4, 50)
(4, 60)
(4, 70)
(4, 80)
(4, 90)
(4, 100)
TNbS
(m,n)
9693
43732
77742
105623
133502
137452
166050
155455
194680
Número de
(máquinas, tarefas)
(7, 20)
(7, 30)
(7, 40)
(7, 50)
(7, 60)
(7, 70)
(7, 80)
(7, 90)
(7, 100)
TNbS
(m,n)
10812
59666
162358
165856
178017
135330
107244
128733
108136
Número de
(máquinas, tarefas)
(10, 20)
(10, 30)
(10, 40)
(10, 50)
(10, 60)
(10, 70)
(10, 80)
(10, 90)
(10, 100)
TNbS
(m,n)
16750
73503
125728
154223
166257
173862
189378
189406
190884
Convém ressaltar que os dois métodos puros (Algoritmo Genético e Simulated Annealing),
que são comparados com o híbrido HBGASA, utilizam a mesma condição de parada.
5.1. O ALGORITMO HBGASA
No método híbrido HBGASA, os passos 1, 2 e 3 referem-se à sua “parte Algoritmo
genético”, enquanto que os passos 4 e 5 (em itálico) correspondem à “parte Simulated Annealing”.
PASSO 1) Seleção dos pais: obter a seqüência inicial 1 (solução do NEH) e a seqüência inicial 2
(solução inicial do FSHOPH).
s1 := seqüência inicial 1
s2 := seqüência inicial 2
f(s1) := makespan da seqüência inicial 1
f(s2) := makespan da seqüência inicial 2
Se f(s1) ≤ f(s2) então
e
Caso contrário,
BS := s1
BM := f(s1)
{melhor solução já obtida}
{makespan da melhor solução}
BS := s2 e BM := f(s2).
Enquanto o número total de seqüências geradas e avaliadas ≤ TNbS(m,n) e s1 ≠ s2:
PASSO 2) Aplicar o operador de cruzamento em s1 e s2:
s1 ✖ s2 → s3 e s4
(onde s3 e s4 são as seqüências descendentes)
Ordenar as 4 seqüências em ordem crescente do makespan f(s).
PASSO 3) Selecionar as 2 seqüências que apresentam os 2 menores makespans
s1 := seq[1]
{seqüência com o primeiro melhor makespan}
f(s1) := f( seq[1] )
s2 := seq[2]
{makespan da primeira melhor seqüência}
{seqüência com o segundo melhor makespan}
(s2) := f( seq[2] )
{makespan da segunda melhor seqüência}
Se f(s1) < BM então:
BS := seq[1]
BM := f( seq[1] ).
PASSO 4) Aplicar a técnica Simulated Annealing tendo s1 como solução inicial, com o número de
iterações K = Nvp(S), determinando a melhor seqüência s* (a de menor makespan).
s1 := s*
f(s1) := f(s*)
Se f(s1) < BM
então
BS := s1
BM := f(s1).
PASSO 5) Aplicar a técnica Simulated Annealing tendo s2 como solução inicial, com o número de
iterações K = Nvp(S), determinando a melhor seqüência s** (a de menor makespan).
s2 := s**
f(s2) := f(s**)
Se f(s2) < BM
então
BS := s2
BM := f(s2).
PASSO 6) Tomar as seqüências s1 e s2 e aplicar o procedimento descrito a partir do Passo 2
• RESULTADOS:
BS : a melhor seqüência das tarefas (solução do problema);
BM : valor do makespan ou duração total da programação das tarefas segundo BS.
6. Experimentação Computacional
Foram desenvolvidos e testados 100 programas híbridos (HBGASA), através da combinação
das diferentes temperaturas iniciais e porcentagem da vizinhança avaliada (vide Item 5). Tais
programas foram comparados com o método metaheurístico Algoritmo Genético puro (onecutGA) -
que também utilizou o operador de cruzamento de UM CORTE - e com o Simulated Annealing puro
(ModSAfshopH).
Na experimentação, foram testados 540 problemas, divididos em 27 classes de acordo com o
número de máquinas (m) e o número de tarefas (n), para: m = 4, 7 , 10 máquinas e n = 20, 30, 40,
50, 60, 70, 80, 90, 100 tarefas. Foram resolvidos 20 problemas por classe.
Todos os problemas foram gerados aleatoriamente, sendo os tempos de processamento das
tarefas números inteiros distribuídos uniformemente no intervalo [0, 100]. O equipamento utilizado
foi um microcomputador Pentium II - Intel MMX de 266 MHz, com 64 Mb de memória RAM,.
Para que o experimento fosse conduzido de maneira mais adequada e eficiente,
desenvolveu-se um software (em linguagem Pascal) chamado Gerenciador de Problemas Flow
Shop, contendo os algoritmos onecutGA, ModSAfshopH e HBGASA.
Os resultados foram analisados em termos dos índices de PORCENTAGENS DE SUCESSO
para máquinas agrupadas. Tal índice mostra o número relativo (porcentagem) de melhoria da
função-objetivo obtido por um determinado método, em relação a um número de tarefas (n)
específico. Assim, se um método apresenta Porcentagem de Sucesso igual a 100%, significa as que
todos os 20 problemas por ele resolvidos tiveram as funções-objetivo melhoradas. Vale lembrar que
foram resolvidos 20 problemas em cada classe de problema (m , n).
As PORCENTAGENS DE SUCESSO (%) para máquinas agrupadas constituem as médias
aritméticas obtidas pelo método em questão, assim calculadas: [% da classe (4, n) + % da classe
(7, n) + % da classe (10, n)] / 3, onde n é o número de tarefas, que pode variar de 20 a 100.
- Exemplo: as PORCENTAGENS DE SUCESSO obtidas pelo método HBGASA 2030 para
o caso de número de tarefas (n) = 20 são: 75% para a classe (m = 4, n = 20); 80% (m = 7, n = 20) e
40% (m = 10, n = 20). Assim, a PORCENTAGEM DE SUCESSO para máquinas agrupadas,
obtidas pelo método HBGASA 2030 no caso (n) = 20, é: (75% + 80% + 40%) / 3 = 65%.
7. Análise dos Resultados Obtidos
As Tabelas 2 a 6 ilustram os resultados obtidos na comparação das Porcentagens de Sucesso
para os diferentes algoritmos nas diversas temperaturas inicias (T1 = 20, 30, 45, 60 e 70).
Na elaboração das tabelas citadas acima, foi utilizada a seguinte simbologia:
➲ o elemento “X” indica que o método HBGASA obteve maior Porcentagem de Sucesso
para uma determinada porcentagem de vizinho analisada, quando comparada ao Algoritmo
Genético e Simulated Annealing puros;
➲ o elemento “•” indica que o método HBGASA apresentou a mesma Porcentagem de
Sucesso obtida pelo Simulated Annealing puro (empate);
➲ célula não preenchida indica que o Simulated Annealing puro obteve maior Porcentagem
de Sucesso do que os demais métodos.
No caso dos híbridos, os dois primeiros números encontrados junto ao nome “HBGASA”
indicam a temperatura inicial e os dois números posteriores indicam a porcentagem da vizinhança
analisada na fase Simulated Annealing. Exemplo:
- HBGASA 2060 Ä Temperatura Inicial = 20;
Vizinhança de Inserção analisada = 60%.
TABELA 2: Comparação entre as Porcentagens de Sucesso obtidas pelo onecutGA, ModSAfshopH
e HBGASA, para Temperatura Inicial = 20.
Algoritmo
20
onecutGA
ModSAfshopH
HBGASA 2005
HBGASA 2010
HBGASA 2015
HBGASA 2020
HBGASA 2025
HBGASA 2030
HBGASA 2035
HBGASA 2040
HBGASA 2045
HBGASA 2050
HBGASA 2055
HBGASA 2060
HBGASA 2065
HBGASA 2070
HBGASA 2075
HBGASA 2080
HBGASA 2085
HBGASA 2090
HBGASA 2095
HBGASA 20100
30
40
Número de Tarefas
50
60
70
•
X
X
X
X
X
X
X
X
X
X
•
X
X
X
X
X
X
X
X
X
•
X
X
X
•
X
•
X
X
X
X
X
X
X
X
•
X
•
X
X
X
X
X
•
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
80
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
90
100
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
TABELA 3: Comparação entre as Porcentagens de Sucesso obtidas pelo onecutGA, ModSAfshopH
e HBGASA, para Temperatura Inicial = 30.
Algoritmo
20
onecutGA
ModSAfshopH
HBGASA 3005
HBGASA 3010
HBGASA 3015
HBGASA 3020
HBGASA 3025
HBGASA 3030
HBGASA 3035
HBGASA 3040
HBGASA 3045
HBGASA 3050
HBGASA 3055
HBGASA 3060
HBGASA 3065
HBGASA 3070
HBGASA 3075
HBGASA 3080
HBGASA 3085
HBGASA 3090
HBGASA 3095
HBGASA 30100
30
40
Número de Tarefas
50
60
70
X
80
90
X
X
X
X
X
X
X
X
•
X
X
X
•
•
X
X
X
•
•
100
X
•
X
X
X
X
X
X
X
•
X
X
X
•
X
X
TABELA 4: Comparação entre as Porcentagens de Sucesso obtidas pelo onecutGA, ModSAfshopH
e HBGASA, para Temperatura Inicial = 45.
Algoritmo
20
onecutGA
ModSAfshopH
HBGASA 4505
HBGASA 4510
HBGASA 4515
HBGASA 4520
HBGASA 4525
HBGASA 4530
HBGASA 4535
HBGASA 4540
HBGASA 4545
HBGASA 4550
HBGASA 4555
HBGASA 4560
HBGASA 4565
HBGASA 4570
HBGASA 4575
HBGASA 4580
HBGASA 4585
HBGASA 4590
HBGASA 4595
HBGASA 45100
30
40
Número de Tarefas
50
60
70
80
90
100
X
X
X
X
•
X
X
X
X
X
X
•
X
X
•
•
•
X
•
X
•
•
TABELA 5: Comparação entre as Porcentagens de Sucesso obtidas pelo onecutGA, ModSAfshopH
e HBGASA, para Temperatura Inicial = 60.
Algoritmo
20
30
40
Número de Tarefas
50
60
70
onecutGA
ModSAfshopH
HBGASA 6005
HBGASA 6010
HBGASA 6015
HBGASA 6020
HBGASA 6025
HBGASA 6030
HBGASA 6035
HBGASA 6040
HBGASA 6045
HBGASA 6050
HBGASA 6055
HBGASA 6060
HBGASA 6065
HBGASA 6070
HBGASA 6075
HBGASA 6080
HBGASA 6085
HBGASA 6090
HBGASA 6095
HBGASA 60100
80
90
100
X
X
X
X
X
X
TABELA 6: Comparação entre as Porcentagens de Sucesso obtidas pelo onecutGA, ModSAfshopH
e HBGASA, para Temperatura Inicial = 70.
Algoritmo
20
onecutGA
ModSAfshopH
HBGASA 7005
HBGASA 7010
HBGASA 7015
HBGASA 7020
HBGASA 7025
HBGASA 7030
HBGASA 7035
HBGASA 7040
HBGASA 7045
HBGASA 7050
HBGASA 7055
HBGASA 7060
HBGASA 7065
HBGASA 7070
HBGASA 7075
HBGASA 7080
HBGASA 7085
HBGASA 7090
HBGASA 7095
HBGASA 70100
30
40
Número de Tarefas
50
60
70
80
90
100
X
X
X
X
A análise das Tabelas 2 a 6 mostram alguns aspectos relevantes:
☞ O método híbrido HBGASA apresenta melhor desempenho quando a Temperatura Inicial
é baixa (T1 = 20 e T1 = 30). Em Temperaturas Iniciais altas (T1 = 60 e T1 = 70), o Simulated
Annealing puro apresenta desempenho bastante superior, quando comparado ao HBGASA.
Apesar da Condição de Parada ser idêntica para todos os métodos testados (ou seja, o
número de seqüências avaliadas TNbS(m,n)), os métodos onecutGA e HBGSA são interrompidos
caso as seqüências-filhos geradas sejam idênticas às seqüências-pais. Assim, em algumas situações
o Simulated Annealing puro é capaz de realizar um maior número de iterações, aumentando a
possibilidade de encontrar soluções melhores.
☞ O desempenho do HBGASA melhora conforme a porcentagem da vizinhança visitada
aumenta. Isto ocorre pois, quanto maior for o número de vizinhos analisados, maiores serão as
chances de se encontrar uma solução de melhor qualidade (isto é, de menor makespan).
De acordo com os resultados encontrados nas Tabelas 2 a 6, pode-se observar que os
métodos híbridos que apresentam os melhores desempenhos são aqueles que trabalham à T1 = 20.
Dentre eles, destacam-se: HBGASA 2070 (T1 = 20 e p = 70%); HBGASA 2075 (T1 = 20 e p = 75%)
e HBGASA 2085 (T1 = 20 e p = 85%).
As PORCENTAGENS DE SUCESSO obtidas pelos métodos onecutGA, ModSAfshopH,
HBGASA 2070, HBGASA 2075 E HBGASA 2085 (para T1 = 20) são encontrados nas Tabelas 7 a 9.
TABELA 7: Porcentagens de Sucesso de onecutGA, ModSAfshopH e HBGASA 2070
Algoritmo
onecutGA
ModSAfshopH
HBGASA 2070
20
30
40
21,66
68,33
78,33
21,66
68,33
73,33
28,33
80,00
71,66
Número de Tarefas
50
60
70
21,66
71,66
75,00
26,66
63,33
80,00
34,99
64,99
81,66
80
90
100
33,33
66,66
83,33
33,33
71,66
81,66
43,33
60,00
89,99
TABELA 8: Porcentagens de Sucesso de onecutGA, ModSAfshopH e HBGASA 2075
Algoritmo
onecutGA
ModSAfshopH
HBGASA 2075
20
30
40
21,66
73,33
78,33
21,66
69,99
64,99
25,00
66,66
76,66
Número de Tarefas
50
60
70
21,66
71,66
78,33
28,33
66,66
78,33
34,99
71,66
76,66
80
90
100
31,66
71,66
76,66
31,66
73,33
83,33
46,66
71,66
81,66
TABELA 9: Porcentagens de Sucesso de onecutGA, ModSAfshopH e HBGASA 2085
Algoritmo
20
onecutGA
ModSAfshopH
HBGASA 2085
30
40
Número de Tarefas
50
60
70
80
90
100
20,00 20,00 23,33 21,66 31,66 38,33 31,66 34,99 44,99
69,99 66,66 68,33 81,66 73,33 71,66 73,33 75,00 68,33
76,66 68,33 73,33 63,33 76,66 78,33 75,00 85,00 81,66
8. Considerações Finais
A programação de operações em ambiente Flow Shop, com o objetivo de minimizar o
makespan é um dos problemas mais conhecidos na área de scheduling. Várias abordagens tem sido
propostas para a resolução deste problema e, dentre as mais recentes contribuições da Pesquisa
Operacional, destacam-se: Algoritmo Genético e Simulated Annealing.
Este trabalho apresenta um método metaheurístico híbrido Algoritmo Genético - Simulated
Annealing (HBGASA) para a solução do problema de programação de operações em ambiente Flow
Shop Permutacional. Outro objetivo é a analisar a influência da temperatura inicial no desempenho
do método em questão.
A identificação dos valores específicos dos parâmetros empregados no HBGASA influi
diretamente no desempenho do método híbrido. Dentro deste contexto, um parâmetro que merece
destaque é a temperatura inicial.
Através da experimentação computacional, verificou-se que o método HBGASA apresenta
performance superior quando trabalha com uma temperatura inicial baixa (T1 = 20).
Outros parâmetros importantes, tais como o operador de cruzamento utilizado, tipo de
vizinhança e formas de busca na vizinhança também se apresentam como alvos de estudo de
futuros trabalhos.
9. Bibliografia
1.
CAMPBELL, H.G., DUDEK, R.A., and SMITH, M.L. (1970), “A Heuristic Algorithm for the n-job, m-machine
Sequencing Problem”, Management Science 16/B, 630-637.
2.
DANNENBRING, D.G. (1977), “An Evaluation of Flow-Shop Sequencing Heuristics”, Management Science 23,
1174-1182.
3.
DÍAZ, B.A. (1996), “An SA/TS Mixture Algorithm for the Scheduling Tardiness Problem”, European Journal of
Operational Research 88, 516-524.
4.
FOX, B. (1992), “Integrating and Accelerating Tabu Search, Simulated Annealing, and Genetic Algorithms”,
Annals of Operations Research 41, 47-67.
5.
GLOVER, F., KELLY, J.P. and LAGUNA, M. (1995), “Genetic Algorithms and Tabu Search: Hybrids for
Optimization”, Computers & Operations Research 22, 111-134.
6.
GOLDBERG, D.E. (1989), “Genetic Algorithms in Search, Optimization, and Machine Learning”. Addison Wesley.
7.
HOLLAND, J.H. (1975), “Adaptation in natural and artificial systems”. The University of Michigan Press, Ann
Arbor, Mich.
8.
IGNALL, E. and SCHRAGE, L.E. (1965), “Application of Branch and Bound Technique to some Flow-Shop
Problem”, Operations Research 13, 400-412.
9.
ISHIBUCHI, H., MISAKI, S. and TANAKA, H. (1995), “Modified Simulated Annealing Algorithms for the Flow
Shop Sequencing Problem”, European Journal of Operational Research 81, 388-398.
10. KIM, H., NARA, K. and GEN, M. (1994), “A Method for Maintenance Scheduling Using GA Combined with SA”,
Computers & Industrial Engineering 27, p.477-480.
11. KIRKPATRICK, S., GELATT, C.D. Jr. and VECCHI, M.P. (1983), “Optimization by Simulated Annealing”,
Science 220, 671-680.
12. LIN, F-T, KAO, C-Y and HSU, C-C (1991), “Incorporating Genetic Algorithms into Simulated Annealing”, Dept.
of Computer Science and Information Engineering, National Taiwan University.
13. MOCCELLIN, J.V. (1995), “A New Heuristic Method for the Permutation Flow Shop Scheduling Problem”,
Journal of the Operational Research Society 46, 883 - 886.
14. MOCCELLIN, J.V. and NAGANO, M.S. (1998), “Evaluating the Performance of Tabu Search Procedures for
Flow Shop Sequencing”, Journal of the Operational Research Society 49, 1296 - 1302.
15. MOTA, W.L. (1996), “Análise Comparativa de Algoritmos Genéticos para o Problema de Programação de
Operações Flow Shop Permutacional”, Dissertação de Mestrado, Escola de Engenharia de São Carlos - USP, 128 p.
16. MURATA, T., ISHIBUCHI, H. and TANAKA, H. (1996), “Genetic Algorithms for Flowshop Scheduling
Problems”, Computers & Industrial Engineering 30, p.1061-1071.
17. NAGANO, M.S. (1995), “Novos Procedimentos de Busca Tabu para o Problema de Programação de Operações
Flow Shop Permutacional”. São Carlos. 117p. Dissertação de Mestrado, Escola de Engenharia de São Carlos USP, 117p.
18. NAWAZ, M., ENSCORE Jr., E.E. and HAM, I. (1983), “A Heuristic Algorithm for the m-Machine, n-Job FlowShop Sequencing Problem”, OMEGA 11, 91-95.
19. OGBU, F.A. and SMITH, D.K. (1990), “The Application of the Simulated Annealing Algorithm to the Solution of
the n/m/Cmax Flowshop Problem”, Computers and Operations Research 17, 243-253.
20. OSMAN, I.H. and POTTS, C.N. (1989), “Simulated Annealing for Permutation Flow-Shop Scheduling”, OMEGA
17, 551-557.
21. PALMER, D.S. (1965), “Sequencing Jobs through a Multi-stage Process in the Minimum Total Time - A Quick
Method of obtaining a Near Optimum”, Operational Research Quarterly 16, 101-107.
22. PARK, M-W and KIM, Y-D (1998), “A Systematic Procedure for Setting Parameters in Simulated Annealing
Algorithms”, Computers & Operations Research 25, 207-217.
23. PIRLOT, M. (1996), “General Local Search Methods”, European Journal of Operational Research 92, 493-511.
24. REEVES, C.R. (1995), “A Genetic Algorithm for Flowshop Sequencing”, Computers & Operations Research 22,
5-13.
25. ROACH, A. and NAGI, R. (1996), “A Hybrid GA-SA Algorithm for Just-In-Time Scheduling of Multi-Level
Assemblies”, Computers & Industrial Engineering 30, 1047-1060.
26. SELEN, W.J. and HOTT, D.D. (1986), “A Mixed-Integer Goal Programming Formulation of the Standard FlowShop Scheduling Problem”, Journal of the Operational Research Society 37, 1121-1128.
27. TAILLARD, E. (1990), “Some Efficient Heuristic Methods for the Flow Shop Sequencing Problem”, European
Journal of Operational Research 47, 65-74
28. WIDMER, M. and HERTZ, A. (1989), “A New Heuristic Method for the Flow Shop Sequencing Problem”,
European Journal of Operational Research 41, 186-193.
29. ZEGORDI, S.H., ITOH, K. and ENKAWA, T. (1995), “Minimizing Makespan for Flow Shop Scheduling by
Combining Simulated Annealing with Sequencing Knowledge”, European Journal of Operational Research 85,
515-531.