O PROBLEMA DE SCHEDULING
EM JOB-SHOP
SOLUÇÃO POR APROXIMAÇÃO
Estrutura do trabalho
1. Introdução
1.2. O problema de job-shop scheduling
1.2.1. Representação por grafos disjuntivos
1.2.2. Construção de escalas
1.2.3. Representação binária
3. Algortimos genéticos
3.1 Conceitos básicos
3.2 Algoritmo genético simples
3.3 O procedimento de um algoritmo
genetico simples
2. Técnicas para solucionar os JSSP
2.1. Soluções ótimas
2.2. Soluções aproximadas
2.2.1. Regras de despacho
2.2.2. Metaheurísticas
2.2.2.1. Algoritmos genéticos
2.2.2.2. Simulated annealing
2.2.2.3. Outros procedimentos de busca
local e modelos híbridos
2.2.3. Outras soluções não ótimas
2.4. Conclusões
4 Um algoritmo genético simples no
problema de scheduling de job-shop
4.1 Codificação genética de uma solução
de schedule
4.2 Harmonização local
4.3 Harmonização Global
4.4 Forcing
4.5 Algoritmo genético simples para o Jobshop
4.6 Limitações para uma aproximação
simples
......
Estrutura

Representação de JSSP clássicos




Gráficos de Gantt
Grafos disjuntivos
Construção de escalas (soluções factíveis)
Representação binária
Estrutura

Representação de JSSP clássicos




Gráficos de Gantt
Grafos disjuntivos
Construção de escalas (soluções factíveis)
Representação binária
Representação do problema
Gráfico de Gantt
(YAMADA & NAKANO, 1997)
Representação do problema
Grafo disjuntivo
(YAMADA & NAKANO, 1997)
Representação do problema
Arco conjuntivo (
Arco disjuntivo (
): seqüência tecnológica
): par de operações na mesma máquina
P12=3
P11=3
O11
O12
P21=4
O
P13=3
O13
P23=3
P22=2
O23
O21
O32
O22
O31
P32=3
*
O33
P31=2
P33=1
Oij= operação da tarefa i na máquina j
Pij= tempo de processamento da operação Oij
Representação do problema
Selecionando uma das direções de cada arco
disjuntivo sem que ocorram ciclos no grafo, reduzse, destas para restrições de precedência.
Estando o grafo totalmente orientado, encontrar
o makespan é calcular o maior caminho entre a
partida e a chegada.
Assim, o JSSP fica reduzido a encontrar-se,
mediante as trocas de orientações dos arcos no
caminho mais longo, uma onde o makespan é
mínimo.
(AYDIN e FOGARTY, 2004)
Representação do problema
7
5
O11
O12
O13
4
0
0
10
O
8
O22
O21
O23
0
3
O31
O32
4
O33
12
2
*
Representação do problema
7
5
O11
O12
O13
4
0
0
O
10
O22
8
O23
0
*
3
O31
O32
O33
4
12
7
5
O11
0
2
O21
O12
O13
4
7
0
10
O
8
O22
4
3
O23
O21
10
0
3
O31
O32
4
O33
12
2
*
Representação do problema
7
5
O11
O12
O13
4
0
7
0
O
10
O22
4
O23
8
3
2
O21
*
10
0
3
O31
O32
4
O33
12
O comprimento do maior caminho é o makespan (tempo de processamento total).
Aquí, o seu valor é: 0 + 4 + 5 + 7 + 10 + 12 + 3 + 4 = 45 ut .
Estrutura

Representação de JSSP clássicos




Gráficos de Gantt
Grafos disjuntivos
Construção de escalas (soluções factíveis)
Representação binária
Construção de escalas
Objetiva-se aquí procurar compreender
as características de alguns algoritmos de
construção de escala, para posteriormente
compreender melhor algumas técnicas
que podem ser empregadas ao longo do
estudo.
Entende-se escala como sendo uma
solução viável para o JSSP.
Construção de escalas
Factível
Inadmissível
Semi-ativo
Ativo
Sem-atraso
Ótimo
Infactível
Contém excesso
de
ociosidade,
mas podem ter
tarefas adiantadas
para melhora da
qualidade.
Não há excessos
de
ociosidade,
mas podem ter
tarefas adiantadas
sem que atrasem
outras.
Construção de escalas
Semi-ativo
M4 OP1 OP1
M3 OP1
Ativo
M2
Sem-atraso
M1
Ótimo
OP2
OP2
OP1
Escala existente
M4 OP1 OP1
M3 OP1
M2
M1
Ativo: nenhuma
Semi-ativo:
todasoperação
as operações
são escalonadas
poderá
ser iniciada
o mais
mais cedo
cedo,
possível
sem
que após
ocorraaso operações
atraso de já
OP2
agendadas,
outra
operação
obedecendo
já agendada
as ou
restrições
viole
alguma
tecnológicas
restrição do
e
seqüência de processamento.
problema.
OP2
OP1
OP2 OP2
Escala semi-ativa
M4 OP1 OP1
M3 OP1
M2
M1
OP2 OP2 OP2
OP1
Escala ativa
Construção de escalas
As escalas sem-atraso são aquelas onde
nenhuma máquina permanece ociosa quando
poderia estar processando alguma operação.
Toda operação pode ser escalonada numa
posição anterior às tarefas já agendadas
(respeitando as restrições), desde que isto não
cause atrasos nas operações já escalonadas.
Estrutura

Representação de JSSP clássicos




Gráficos de Gantt
Grafos disjuntivos
Construção de escalas (soluções factíveis)
Representação binária
Representação binária
Um sequenciamento semi-ativo pode ser obtido pela troca de
arcos disjuntivos em orientados.
Rotular cada arco disjuntivo com valores 0 e 1 implicará na
possibilidade de uma palavra binária equivaler ao schedule feito.
Rotulando arcos disjuntivos
Quando o arco conectando Oij e Okj (i<k) for 1 significa que
Oij será processada antes de Okj, ou seja, a precederá. Tem-se 0 para
caso contrário.
Referências
YAMADA, T. e NAKANO R., Genetic Algorithms for Job-Shop Scheduling
Problems. Proceedings of Modern Heuristic for Decision Support, p.
67-81, Londres, Março de 1997.