Flow Shop Scheduling
Grupo:
Leandro Lopes
Marcelo Henrique Dias
Tópicos
 Descrição do problema
 Modelagem
 Implementação (!)
Descrição do problema
Há um conjunto de n jobs e m máquina cada
job possui um certo número de operações
Ex:
JOB 1
M1(2)
M2(2)
M3(4)
JOB 2
M1(3)
M2(1)
M3(1)
JOB 3
M1(2)
M2(3)
M3(2)
Descrição do problema
Objetivo:
Diminuir o makespan, ou seja, a
duração total da programação
Modelagem
Para representar as operações dos jobs,
utilizamos a seguinte estrutura:
JOB
M1
M2
M3
SOMA
1
2
2
4
8
2
3
1
1
5
3
2
3
2
7
Modelagem
Para representar as alocações dos jobs, temos
a estrutura:
M1
M2
M3
1
2
1
1
3
4
1
1
5
6
7
8
9
10 11 12
Modelagem
Será necessária uma matriz para auxiliar nas
alocações dos jobs:
JOB
Última Máquina
Última Posição
1
1
2
2
3
Modelagem
Construção da solução inicial:
 Método guloso
 Aloca sempre a operação do job com a maior
soma de tempos
JOB
M1
M2
M3
SOMA
1
2
2
4
8
2
3
1
1
5
3
2
3
2
7
Modelagem
Características:
 Não há possibilidade de inviabilidades
 Sobreposição
 Alocação de operações em ordem não permitida
1
2
3
4
M1 1
M2
1
1
1
1
M3
5
6
7
8
9 10 11 12
Modelagem
Função objetivo:
 Como não há inviabilidade
A função objetivo será apenas o tempo
total da duração da programação.
M1
M2
M3
1
2
3
4
5
6
7
8
1
1
3
3
2
2
2
1
1
3
3
3
2
1
1
1
1
9
3
10 11 12
3
2
Modelagem
Movimentos: Apenas são aceitos movimentos na máquina 1
M1
1
2
3
4
5
6
7
1
1
3
3
2
2
2
1
1
3
3
3
2
1
1
1
1
3
5
6
7
8
9
M2
M3
M1
M2
M3
1
2
3
2
2
2
4
8
9
10 11 12
3
2
10 11 12
Modelagem
Heurística:
 Busca Tabu
Vizinhança:
 Para cada job, movimentar a operação da máquina 1
em todas as possíveis posições da própria maquina 1
Modelagem
Vizinhança:
M1
1
2
3
4
5
6
7
1
1
3
3
2
2
2
1
1
3
3
3
2
1
1
1
1
3
5
6
7
8
9
M2
M3
M1
M2
M3
1
2
3
2
2
2
4
8
9
10 11 12
3
2
10 11 12
Modelagem
Vizinhança:
M1
1
2
3
4
5
6
7
1
1
3
3
2
2
2
1
1
3
3
3
2
1
1
1
1
3
5
6
7
8
9
M2
M3
1
M1
M2
M3
2
3
4
2
2
2
8
9
10 11 12
3
2
10 11 12
Modelagem
Vizinhança:
M1
1
2
3
4
5
6
7
1
1
3
3
2
2
2
1
1
3
3
3
2
1
1
1
1
3
6
7
8
9
M2
M3
1
M1
M2
M3
2
3
4
5
2
2
2
8
9
10 11 12
3
2
10 11 12
Modelagem
Vizinhança:
M1
1
2
3
4
5
6
7
1
1
3
3
2
2
2
1
1
3
3
3
2
1
1
1
1
3
4
5
6
7
8
9
2
2
2
M2
M3
1
M1
M2
M3
2
3
8
9
10 11 12
3
2
10 11 12
Modelagem
Vizinhança:
Para cada vizinho de um job x encontrado,
construir a solução e encontrar a Fo-job.
Guardar então o movimento na estrutura a seguir
Pi
vizinhos_job
Pf
Fo
Modelagem
Vizinhança:
Quando toda vizinhança com aquele job x estiver
completa, encontrar na estrutura vizinho_job
o movimento com melhor Fo
Gravar então o movimento na matriz de
melhores vizinhos gerais
Pi
vizinho_geral
Pf
Fo
Modelagem
Vizinhança:
Com a matriz vizinho_geral completa, encontrar
O melhor movimento, observando a Fo.
Se o mesmo for melhor que o Fo_star,
Fo_star  Fo;
Modelagem
Vizinhança:
M1
1
2
3
4
5
6
7
1
1
3
3
2
2
2
1
1
3
3
3
2
1
1
1
1
3
5
6
7
8
9
2
2
2
M2
M3
1
M1
M2
M3
2
3
4
X
8
9
10 11 12
3
2
10 11 12
Modelagem
Lista Tabu:
Utilizamos um matriz para guardar
os movimentos proibidos
JOB
Pi (Posição Inicial)
2
5
.
.
.
Implementação
?