O PROBLEMA DE SCHEDULING
EM JOB-SHOP
SOLUÇÃO POR APROXIMAÇÃO COM ALGORITMO
GENÉTICO
Estrutura
Introdução
 Objetivos
 Tópicos para revisão da literatura
 Metodologia a ser adotada
 Comentários

Introdução
Sobrevivência no mercado está associada ao
planejamento e controle da produção, que atua também
na programação da produção com o escalonamento de
atividades;

O escalonamento é peça fundamental na tomada de
decisão, tanto de manufatura como de serviços.

Introdução
WALTER (1999) considera que organizar os
processos produtivos frente a um planejamento maior é
objetivar um melhor atendimento de prazos ou datas de
entrega, minimização de tempos de fluxos dos estoques
intermediários, maximização da capacidade disponível.


Sistemas discretos e contínuos;

Job-shop e escalonamento;
Estrutura
Introdução
 Objetivos
 Tópicos para revisão da literatura
 Metodologia a ser adotada
 Comentários

Objetivos

OBJETIVO GERAL
Desenvolver método baseado em algoritmo
genético para solucionar schedulings em Job-Shops,
com soluções eficientes em tempo computacional
satisfatório.
Estrutura
Introdução
 Objetivos
 Tópicos para revisão da literatura
 Metodologia a ser adotada
 Comentários

Tópicos para revisão da literatura
O problema de scheduling de Job-Shop:
 Algoritmos genéticos;
 Representação genética das soluções;

Tópicos para revisão da literatura





Introdução
Objetivos
Tópicos para revisão
da literatura
Metodologia a ser
adotada
Comentários



O problema de
scheduling de Job-Shop;
Algoritmos genéticos;
Representação genética
das soluções;
O JSSP
Em linhas gerais, um job-shop é uma organização
funcional cujos departamentos são organizados em
torno de processos particulares, os quais consistem em
tipos específicos e/ou operações, tais como perfuração
e montagem em uma fábrica, operações de leitura ótica
e impressão em um laboratório de computação.
Os bens produzidos ou os serviços oferecidos são
originados por pedidos individuais de um cliente
específico.
O JSSP
Especificamente, o Job-Shop pode ser definido
como sendo um conjunto de N jobs J={J1, J2, ..., JN} a
serem processados em M máquinas disponíveis
M={M1, M2, ..., MM}.
Cada job possui uma ordem de execução
específica entre cada uma das máquinas, ou seja, um
job é composto de uma lista ordenada de operações,
cada qual definida pela máquina requerida e pelo
tempo de processamento na mesma.
O JSSP
As restrições que podem ser seguidas são:





Operações não podem ser interrompidas, e cada máquina
pode processar apenas uma operação de cada vez;
Cada job só pode ser processado em apenas uma máquina
por vez;
Cada job é processado por uma seqüência conhecida de
operações;
Não existe restrições de precedência entre operações de
diferentes jobs;
Não existe relação de precedência entre as operações
executadas por uma mesma máquina;
O JSSP
Definidas as sequências de máquina de cada job, o
problema consiste em determinar as seqüências dos
jobs em cada máquina, de forma que o tempo de
execução transcorrido, desde o início do primeiro job
até o término so último, seja mínimo.
A medida de qualidade empregada, conhecida por
makespan não é única, mas é o critério mais simples e
mais largamente usado.
Normalmente o número de restrições é muito
grande, tornando o Job-Shop um dos problemas mais
difíceis de ser solucionado.
O JSSP
Exemplo (j=3/m=3 Job-shop):
Como distribuir o melhor arranjo de tarefas
para as máquinas M1, M2 e M3 ?
O JSSP
Exemplo (cont):
Solução:
31 unidades de tempo
O JSSP
Os JSSP’s e casos de scheduling similares são
problemas de otimização combinatória, classificados
como problemas NP-hard (GOLDBARG E LUNA,
2000). Apesar de existirem métodos exatos, é quase
impossível resolvê-los desta forma, exceto para
exemplos relativamente pequenos do problema.
O JSSP
Em ambientes de produção reais, é suficiente obter
resultados próximos do ótimo, mas em tempo
computacional razoável, conseguido com os métodos
heurísticos.
São aproximações importantes aplicadas ao JSSP:
Busca Tabu (TS) (BARNES e CHAMBERS, 1995),
Simulated Annealing (SA) e Algoritmos Genéticos
(AG) (YAMADA e NAKANO, 1997).
Muito utilizados em problemas de scheduling, os
AGs demonstram maior versatilidade ante outras, dada
a facilidade na codificação do espaço do problema
(STORER et al 1995).
Algoritmos genéticos
É uma técnica heurística que consiste na busca de soluções
baseadas em mecanismos da seleção natural e genética.
Inicialmente estudados por HOLLAND (1975), fundamentaramse pela teoria geral de sistemas e adaptação robusta, com
aplicação prática na determinação de máximos e mínimos de
funções matemáticas.
Em linhas gerais, partindo de uma população inicial, cada
indivíduo passará pelas etapas tripartites do algoritmo como parte
da busca por soluções ótimas: reprodução, crossover e mutação
(GOLDBERG, 1989).
Tópicos para revisão da literatura





Introdução
Objetivos
Tópicos para revisão
da literatura
Metodologia a ser
adotada
Comentários



O problema de
scheduling de Job-Shop;
Algoritmos genéticos;
Representação genética
das soluções;
Algoritmos genéticos
Os AGs diferem das outras
apresentar características distintas:




heurísticas
por
opera em um conjunto de pontos (população) e não a partir
de pontos isolados;
opera em um espaço de soluções codificadas e não
diretamente no espaço de busca;
necessita como informação, somente o valor de uma função
objetivo (função de adaptabilidade, ou fitness);
usa transições probabilísticas e não regras determinísticas
(GOLDBARG e LUNA, 2000).
Algoritmos Genéticos
Analogia entre um AG numérico e a genética biológica
Fonte: HAUPT&HAUPT, 2004
Algoritmos Genéticos
Fluxograma de um algoritmo genético
Fonte: HAUPT&HAUPT, 2004
Algoritmos Genéticos
Geração de dois filhos por meio de cruzamento de pais selecionados.
Fonte: HAUPT&HAUPT, 2004
Algoritmos genéticos
Passo 1: Inicialização
Ler o tamanho da população, K, e taxa de mutação, pm.
Inicializar cromossomos gerando soluções factíveis no tamanho da população.
Passo 2: Cálculo do fitness
Calcular os valores de fitness de cada indivíduo da população inicial.
Passo 3: Seleção dos pais
Selecionar randomicamente dois cromossomos da população, considerando a
probabilidade de escolha associada ao fitness de cada um.
Passo 4: Geração de descendência
Empregando o operador crossover, gerar dois cromossomos a partir dos pais
selecionados no passo 3.
Passo 5: Fim da geração de descendência
Repetir os passos 3 e 4 se o tamanho da geração de descendentes for < K; caso
contrário, ir para o passo 6.
Passo 6: Mutação
Para cada indivíduo da população, varrer os elementos de cada cromossomo,
modificando-os randomicamente, com probabilidade pm.
Passo 7: Cálculo do fitness
Calcular o fitness para os cromossomos descendentes.
Passo 8: Finalização
Caso o critério de finalização seja alcançado, parar; caso contrário, dirigir-se ao passo 3.
Fonte: RODRIGUES et ali, 2003
Algoritmos genéticos
O tamanho da população é um dos principais
fatores de controle de um algoritmo genético,
entretanto, é preciso considerar ainda a taxa de
ocorrência de mutações e o número de gerações,
além de outros fatores, como o número de gerações
sem melhoras significativas quanto ao melhor
indivíduo encontrado.
Tópicos para revisão da literatura





Introdução
Objetivos
Tópicos para revisão
da literatura
Metodologia a ser
adotada
Comentários



O problema de
scheduling de Job-Shop;
Algoritmos genéticos;
Representação genética
das soluções;
Codificação das soluções
Exemplo: Problema do Caixeiro Viajante
Esquema de codificação
- Exemplo de solução válida para o problema:
Indivíduo e cromossomo
Cromossomo: 001 100 010 001
Indivíduo: ACBA
Estrutura
Introdução
 Objetivos
 Tópicos para revisão da literatura
 Metodologia a ser adotada
 Comentários

Proposta metodológica
Inicialmente,
desenvolver
pesquisa
bibliográfica sobre o tema, aprofundando o
assunto de JSSP, bem como do uso de AGs na
busca de soluções para o problema.
Posteriormente, desenvolver avaliações das
soluções encontradas para um dado problema
apresentado e avaliar o comportamento ante
diferentes
tratamentos
de
operadores
crossover.
Estrutura
Introdução
 Objetivos
 Tópicos para revisão da literatura
 Metodologia a ser adotada
 Comentários

Comentários