FlowShop Scheduling
Permutacional
Solução pelo SA
Flávio Thimotio da Silva
Leonardo Jabour Lott Carvalho
Vinicius Graciano Guimarães
O FlowShop Scheduling
 Um conjunto de n tarefas devem ser
processadas, em m máquinas ordenadamente
 Número de possíveis soluções = (n!)*m
 É um problema NP-difícil
FlowShop Permutacional
 Quando a ordem de processamento em todas
as máquinas for a mesma, trata-se de um
problema FlowShop Permutacional.
 Número de possíveis soluções = (n!)
 É um problema NP-difícil (Garey et al.
[1976])
Objetivo
 Diminuir makespan, que é o tempo total de
processamento de todas as tarefas em todas
as máquinas
 O tempo de operação total de cada máquina
não é levado em consideração
Modelagem
 Dado um conjunto de tarefas n, a solução do
problema será a ordem de processamento das
tarefas
 Para n = 5
1
Ordem de processamento
5
4
3
2
Vizinhança
 Troca entre tarefas
1
Ordem de processamento
5
4
3
2
4
Ordem de processamento
5
1
3
2
Vizinhança
 Deslocamento
1
5
4
3
2
4
1
5
3
2
1
5
4
3
2
3
2
4
1
5
 Troca 2 a 2
Função de Avaliação
 Fo = min (makespan)
 Exemplo:
Máquinas
1
2
3
1
3
2
1
2
3
3
2
3
4
3
1
Tarefas
Função de Avaliação
 Makespan
 Seqüência de tarefas: 2 - 1 - 3
0
1
2
3
1
2
2
2
3
2
4
1
2
Tempo
5 6 7
1 1 3
2 2 1
2
8
3
1
2
makespan
9 10 11 12 13 14
3 3
3 3 3
1
3
Função de Avaliação
 Vizinho: 1 - 2 - 3
makespan
0
1
2
3
1
1
2
1
3
1
4
2
1
Tempo
5 6 7 8
2 2 3 3
1
2 2
1
9 10 11 12 13
3 3
2 3 3 3
2 2
3
Resultados
 100 tarefas
 5 máquinas
 Taxa de resfriamento = 0.95
 Temperatura inicial


Algorítmo
Número de movimentos aceitos = 90% de n
Resultados
 Desvio médio = 0,014%
 Desvio Padrão = 0,016%
Makespan
20140
20130
20120
20110
execução
29
27
25
23
21
19
17
15
13
11
9
7
5
3
20100
1
makespan
20150
Resultados
Tempo de execução
110
(s)
100
90
80
70
60
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
execução
FIM