Inteligência Artificial Aplicada a
Sistemas de Controle e Automação
DAS 6607
Simulador da Produção
Departamento de Automação e Sistemas
Universidade Federal de Santa Catarina
Professor:Guilherme Bittencourt
Aluno: Denis Pinha
1
Tópicos
Introdução
Exemplo de um problema (Contexto)
Universo de Soluções, complexidade
e técnicas para resolver o problema
Hierarquia dos frames (objetos ou
conceitos) de um simulador de fábrica
Apresentação básica de um
simulador de produção desenvolvido
para uma empresa
2
Introdução: O que é
Inteligência Artificial?
Conjunto de técnicas para resolver problemas complexos, isto é,
problemas que, apesar de não ter solução algorítmica , são
solucionados por seres humanos.
3
Introdução ao
ambiente fabril
 o conhecimento sobre o mundo não precisa, necessariamente,
obedecer a nenhuma propriedade matemática global, como
coerência ou completude. Sua adequação deve ser medida pela sua
utilidade na solução de problemas práticos;
Ex:
Cabine de Pintura ,
Operações
Simultâneas, Peças
Conjugadas, Estoque
Alto
4
SEQÜENCIAMENTO DA
PRODUÇÃO
Problema Introdutório:
O Caso dos Leitores
5
Enunciado
Parte 1
Alberto (A), Bruno (B), Carlos (C) e Daniel (D) moram
juntos. Aos domingos, pela manhã, gostam de ler os jornais O
Globo (Gl), Jornal do Brasil (JB), O Dia (Di) e o semanário
Casseta e Planeta (CP), que recebem à porta de casa por volta
das 8:00 horas.
Além disso, após todos terem lido todos os jornais,
desejam sair juntos, e o mais cedo possível, para a praia no
(único) carro que possuem.
A hora em que acordam, bem como a ordem em que
preferem ler os jornais e os respectivos tempos de leitura,
podem ser vistos no quadro apresentado a seguir.
Por uma questão de organização, os jornais não são
subdivididos em partes ou cadernos e, portanto, só podem ser
lidos por uma pessoa de cada vez.
6
Dados
O rd e m
L E IT O R
ACO RDA
A lb e rto
8 :3 0
B ru n o
C a rlo s
D a n ie l
8 :4 5
8 :4 5
9 :3 0
T e m p o d e le itu ra
JB
Gl
Di
CP
6 0 m in
3 0 m in
2 m in
5 m in
Gl
Di
JB
CP
7 5 m in
3 m in
2 5 m in
1 0 m in
Di
Gl
JB
CP
5 m in
1 5 m in
1 0 m in
3 0 m in
CP
JB
Gl
Di
9 0 m in
1 m in
1 m in
1 m in
7
Questões
Supondo que os quatro amigos conseguem se alimentar e
realizar as suas higienes matinais enquanto estão lendo os jornais,
pergunta-se:

Qual a relação deste enunciado com o de um problema de
programação e controle da produção? Isto é, o que seriam
neste enunciado os:
• Produtos ou itens
• Máquinas ou recursos de produção
• Tempos de operação ou de fabricação
• Roteiros de produção
• Prioridades ou seqüências de produção

Quais técnicas ou ferramentas de Sistemas, Planejamento e
Controle da Produção e/ou Pesquisa Operacional podem ser
usadas para a solução do problema ?
8
Questões

Qual a seqüência de leitura de cada jornal (isto é, quem lê o
quê em primeiro, segundo, terceiro e quarto lugar) que permite
a Alberto, Bruno, Carlos e Daniel saírem juntos o mais cedo
possível para a praia? Que hora é esta ?

É possível provar que a resposta dada ao item anterior é a
resposta ótima do problema ? Como ?

Supondo que os quatro amigos possam ler os jornais em
qualquer ordem, quantas soluções possíveis tem esse
problema?
9
Questões
 Nesse caso, considerando que um computador rápido leva um
segundo para processar (isto é, encontrar e avaliar) mil
soluções possíveis do problema, qual o tempo computacional
necessário para pesquisar todo o universo de soluções com o
objetivo de se encontrar a solução ótima ? Expresse este
tempo na maior unidade possível (isto é segundos, minutos,
hora, dia, semanas, meses ou o que for apropriado).

Como este tempo computacional cresceria se o número de
leitores passasse a ser cinco ? E se fossem seis os leitores ?
E se fossem sete ?
10
SEQÜENCIAMENTO DA
PRODUÇÃO
Problema Introdutório:
O Caso dos Leitores
11
Analogias

Qual a relação do problema com a programação e controle
da produção? Isto é, o que seriam no enunciado os:

Produtos ou itens ?


Seriam as pessoas: Alberto, Bruno, Carlos e Daniel.
Máquinas ou recursos de produção ?
 Seriam os jornais: Jornal do Brasil, Globo, Dia e
Planeta.

Tempos de operação ou de fabricação ?

Seriam os tempos estimados de leitura.
12
Solução Gráfica

Qual a seqüência de leitura de cada jornal (isto é, quem lê o
quê em primeiro, segundo, terceiro e quarto lugar) que permite
ao Alberto, Bruno, Carlos e Daniel saírem juntos o mais cedo
possível para a praia? Que hora é esta ?

Para solução da questão será utilizado um método de
"tentativas e erros".
Serão testadas três alternativas
baseadas em três hipóteses distintas de priorização (isto
é, seqüência de leitura de cada jornal), escolhendo-se o
melhor resultado obtido.
13
Solução 1
O rd e m
L E IT O R
AC O R D A
A lb e rto
8 :3 0
B ru n o
C a rlo s
D a n ie l
T e m p o d e le itu ra
JB
Gl
Di
CP
60 m
30 m
2 m
5 m
Gl
Di
JB
CP
75 m
3 m
25 m
10 m
Di
Gl
JB
CP
5 m
15 m
10 m
30 m
CP
JB
Gl
Di
90 m
1 m
1 m
1 m
8 :4 5
8 :4 5
9 :3 0
J o rn a l
L e ito r 1 L e ito r 2 L e ito r 3 L e ito r 4
Di
A
B
C
D
C
B
C
A
A
B
D
D
CP
D
A
C
B
JB
Gl
JB
Gl
Di
CP
8:30
8:45
9:30
10:00
10:15
11:00
12:00
11:51
Alberto
Bruno
Carlos
Daniel
14
Solução 1 / Observações
•
O Roteiro (que é uma restrição do problema) pode levar a
jornais ociosos .
JB
O rd e m
Gl
Di
L E IT O R
AC O R D A
A lb e rto
8 :3 0
B ru n o
CP
C a rlo s
8:30
8:45
9:30
10:00 10:15
11:00
10:00
Alberto
Bruno
Carlos
12:00
D a n ie l
8 :4 5
8 :4 5
9 :3 0
T e m p o d e le itu ra
JB
Gl
Di
CP
60 m
30 m
2 m
5 m
Gl
Di
JB
CP
75 m
3 m
25 m
10 m
Di
Gl
JB
CP
5 m
15 m
10 m
30 m
CP
JB
Gl
Di
90 m
1 m
1 m
1 m
Daniel
ex: às 10:00 horas, Bruno pega O Dia ao invés do Jornal do Brasil (que
assim fica mais tempo ocioso), porque o seu roteiro obriga que assim seja.
15
Solução 1 / Observações
•
A Seqüência (que é fruto da solução adotada) pode levar a
leitores ociosos .
JB
O rd e m
Gl
Di
L E IT O R
AC O R D A
A lb e rto
8 :3 0
B ru n o
CP
8 :4 5
C a rlo s
8:30
8:45
9:30
10:00 10:15
11:00
12:00
T e m p o d e le itu ra
8 :4 5
D a n ie l
9 :3 0
10:15
Alberto
Bruno
Carlos
JB
Gl
Di
CP
60 m
30 m
2 m
5 m
Gl
Di
JB
CP
75 m
3 m
25 m
10 m
Di
Gl
JB
CP
5 m
15 m
10 m
30 m
CP
JB
Gl
Di
90 m
1 m
1 m
1 m
Daniel
J o rn a l
ex: às 10:15 horas, Carlos pode pegar o
Jornal do Brasil mas tem que esperar
Daniel, porque a seqüência de produção
adotada obriga que assim seja.
L e ito r 1 L e ito r 2 L e ito r 3 L e ito r 4
JB
A
D
C
B
Gl
Di
B
C
C
B
A
A
D
D
CP
D
A
C
B
16
Solução 3
O rd e m
L E IT O R
AC O R D A
A lb e rto
8 :3 0
B ru n o
C a rlo s
D a n ie l
T e m p o d e le itu ra
JB
Gl
Di
CP
60 m
30 m
2 m
5 m
Gl
Di
JB
CP
75 m
3 m
25 m
10 m
Di
Gl
JB
CP
5 m
15 m
10 m
30 m
CP
JB
Gl
Di
90 m
1 m
1 m
1 m
8 :4 5
8 :4 5
9 :3 0
J o rn a l
L e ito r 1 L e ito r 2 L e ito r 3 L e ito r 4
C
A
B
D
Di
C
C
B
B
A
A
D
D
CP
C
D
B
A
JB
Gl
JB
Gl
Di
CP
8:30
8:45
9:45
11:15
12:00
11:30
Alberto
Bruno
Carlos
Daniel
17
Conclusão do Problema
Comparando-se as três soluções verifica-se que a melhor
solução é a terceira. Um resultado nada óbvio já que das três
hipóteses examinadas essa é aquela onde mais leitores são
submetidos a esperas forçadas (vide quadro abaixo).
JB
Gl
Di
CP
8:30
8:45
9:45
11:15
12:00
11:30
Alberto
Bruno
S o lu ç ã o
F im P la n e ja d o
1
1 1 :4 5
Carlos
Daniel
E s p e ra s F o rç a d a s
B r u n o d e 1 0 :0 3 a té 1 1 :1 1
C a r lo s d e 9 :1 5 a té 1 1 :0 1
2
1 1 :4 5
3
1 1 :3 0
--A lb e r to d e 8 :3 0 a té 9 :1 5
B r u n o d e 8 :4 5 a té 9 :0 5
D a n ie l d e 9 :3 0 a té 9 :4 5
18
Conclusão
Portanto, decisões “locais” que, à primeira vista, possam
parecer irracionais,
Por exemplo,
Alberto acorda, todos continuam
JB
dormindo, o seu jornal preferido
Gl
(JB) está disponível, e mesmo
Di
assim ele é impedido de lê-lo
CP
antes de Carlos que, por sua vez,
só acordará 15 minutos depois, e
8:30
8:45
9:45
11:15
11:30
Alberto
Bruno
Carlos
Daniel
12:00
ainda lerá 2 outros jornais antes
de pegar o JB !
numa visão “global” e estruturada do problema - proporcionada
pelo gráfico de Gantt - mostram-se perfeitamente lógicas .
Aqui, o entendimento integral do problema mostra como a
paciência (de Alberto, Bruno e Daniel) pode ser uma virtude necessária
e compensadora !
19
Análise do Melhor Caso

Como provar que esta resposta é ótima ?
20
Solução Ótima
•
O que não significa que seja a única solução ótima !
•
Por exemplo, podemos só inverter os 2 últimos leitores do
Planeta na Solução 3 :
JB
Gl
Di
CP
8:30
8:45
9:45
11:15
12:00
11:30
Alberto
Bruno
Carlos
Daniel
21
Universo de Soluções

Caso os quatro amigos possam ler os jornais em qualquer
ordem, quantas soluções possíveis tem esse problema ?

Se houvesse apenas um jornal, haveria (4 !) = 24 soluções
de seqüenciamento.

Como, entretanto, há quatro jornais em questão e o
seqüenciamento da leitura de cada um deles é independente
da
seqüência
de
leitura
dos
demais,
há
(4 !)4 = 331.776 soluções.

Com efeito, o número de soluções possíveis (factíveis e
não factíveis) de seqüenciamento é da ordem de (n !)m,
onde n são os itens e m são os recursos envolvidos no
problema.
22
Complexidade do Problema

Neste caso, considerando que um computador rápido leva um
segundo para processar (isto é, encontrar e avaliar) mil soluções
possíveis do problema, qual o tempo computacional necessário
para pesquisar todo o universo de soluções com o objetivo de
se encontrar a solução ótima ?
unidade possível
Expresse este tempo na maior
(isto é, segundos, minutos, horas, dias,
semanas, meses ou o que for apropriado).

331.776 soluções
= 5 ½ minutos
/
1000 soluções por segundo
/
60
23
Natureza Combinatória
Explosiva

Como este tempo computacional cresceria se o número de
leitores passasse a ser cinco ?
E se fossem seis leitores ?
E se fossem sete ?

A tabela abaixo registra a evolução do universo de soluções
e correspondente tempo de processamento:
L e ito re s
/ Ite n s
J o rn a is /
M á q u in a s
U n ive rs o d e
S o lu ç õ e s
Tem po de
P ro c e s s a m e n to
R e q u e rid o
4
4
331.776
5,5 minutos
5
4
2,1 x 10 8
2,4 dias !
6
4
2,7 x 10 11
8,5 anos !!
7
4
6,5 x 10 14
205 séculos !!!!
24
Técnicas para Resolver
o Problema

Quais técnicas ou ferramentas de Administração, Sistemas
(Sistema Multiagente (SMA) , Planejamento e Controle e/ou
Pesquisa Operacional podem ser usadas para a solução do
problema ?

Ferramentas gráficas (e.g. gráficos de Gantt), métodos
analíticos ou matemáticos (e.g. programação linear,
programação combinatorial,
programação inteira,
programação dinâmica)
e métodos heurísticos,
baseados no bom-senso (e.g modelos de simulação
computacional).
25
Métodos heurísticos
Diante da complexidade do problema de programação,
analisaremos agora quatro métodos estruturados para resolução
do problema. São eles:

PROGRAMAÇÃO PARA FRENTE (pedido a pedido)
comumente
(embora imprecisamente) chamado
“FORWARD PLANNING”

PROGRAMAÇÃO PARA TRÁS BASEADA NA ABORDAGEM
MRP (pedido a pedido)
=> comumente
(embora
imprecisamente) chamado de “BACKWARD PLANNING”

PROGRAMAÇÃO BASEADA NA TEORIA DAS RESTRIÇÕES
(operação a operação) => também chamado de “PROGRAMAÇÃO MISTA”
PROGRAMAÇÃO POR SIMULAÇÃO (operação a operação) =>
também chamado (embora imprecisamente) de “PROGRAMAÇÃO POR CAPACIDADE FINITA”

=>
de
26
Programação por Simulação
Com os dados do problema dos Leitores, construa uma
solução estruturada baseada na “PROGRAMAÇÃO POR
SIMULAÇÃO (operação a operação)”. Utilize para tanto a seguinte
lógica de construção:

Avance o “relógio da simulação” até o instante onde ocorre o
primeiro evento significativo (por exemplo, a chegada de um material,
o fim de processamento num recurso, etc.)

Com base no critério de prioridade adotado (MDE), identifique os
pedidos que podem ser processados nesse instante no recurso em
questão e selecione o mais prioritário para programação.

Repita o passo 2 até que todas as operações tenham sido
programadas.
27
Regras Heurísticas de Carregamento
“... o número de regras de descarregamento de filas
existentes só é limitado pela nossa ingenuidade ! ”






PEPS
(Primeiro a entrar deve ser o primeiro a sair)
MTP (Item de menor tempo de processamento deve ser processado primeiro)
MDE (Item com data de entrega mais apertada deve ser processado primeiro)
Maior Multa (Item que induz a maior multa deve ser processado primeiro)
Maior Preço (Item que induz a maior preço deve ser processado primeiro)
Menor Folga (Item que tem a menor folga calculada como:
(Data de entrega - Instante da decisão) - Tempo remanescente de processamento

Razão Crítica (Item que tem a menor folga calculada como:
(Data de entrega - Instante da decisão) / Tempo remanescente de processamento
Você é capaz de imaginar outras regras heurísticas de
descarregamento de filas ?
28
PEDIDOS
ADIANTADOS
Freqüência
PEDIDOS
ATRASADOS
a) situação “quase ótima” em termos
de cumprimento de prazo de entrega.
I
A
0
0
I
A
I
A
Atraso
b) regra ignorando os tempos de
processamento e datas de entrega.
Ex: PEPS
I
A
0
c) regra baseada em tempos de
processamento.
Ex: MTP
0
d) regra baseada em data de entrega
(carga e capacidade balanceadas).
Ex: MDE
e) regra baseada em data de entrega
(carga e capacidade desbalanceadas).
Ex: MDE
0 A
I
29
Complicadores do Problema






Tempos de preparação de máquina
Tempos de transporte
Descontinuidades do tempo (turnos, fins-de-semana, feriados)
Manutenção preventiva
Perdas históricas de capacidade (e.g. manutenção corretiva)
Disponibilidade restrita de ferramentas ou moldes (além das
máquinas)




Disponibilidade restrita de pessoal
Limitações de orçamento
Dinâmica de re-programação
Fabricação para posterior montagem
30
PONTUALIDADE TOTAL
Diante de tal complexidade, como chegar lá ?
PONTUALIDADE TOTAL é :
Programar e controlar a produção tendo como meta
Entregar 100% dos pedidos no prazo de acordo com as
especificações técnicas e o orçamento combinado
e assim
Desenvolver junto ao cliente uma reputação de excelência
em termos de cumprimento de prazos
31
PONTUALIDADE TOTAL
Ações indicadas

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
Como ser PONTUAL ?
Planejar antecipadamente
Programar realisticamente considerando os limites existentes de capacidade
Programar com folga
Programar detalhadamente o curto prazo
Explorar as possibilidades de seqüenciamento existentes
Explorar as possibilidades ligadas ao uso de máquinas e roteiros alternativos
Explorar as possibilidades de ajuste do nível de capacidade
(e.g. horas-extras, subcontratações)
Explorar as possibilidades de apressamento (i.e. expeditação) de pedidos
urgentes
Explorar as possibilidades de antecipação do recebimento de materiais críticos
Explorar as possibilidades ligadas ao uso de projetos, processos e materiais
alternativos
Antecipar para os clientes possíveis problemas de entrega, quando inevitáveis
Prometer prazos e/ou decidir aceitar encomendas considerando os compromissos
já assumidos
Acompanhar o andamento e a pontualidade dos processos internos
Replanejar rapidamente e sempre que fatos significativos aconteçam sem terem
sido previstos
32
PONTUALIDADE TOTAL
Ações indicadas

Como fazer BARATO ?
15. Evitar grandes antecipações na produção de componentes não-críticos
16. Apresentar os custos e benefícios de cada possível solução de programação
17. Identificar as operações e recursos críticos para concentrar neles os ajustes de
capacidade (horas-extras, subcontratações)

Como fazer RÁPIDO ?
18. Programar para dispor dos equipamentos o mais cedo possível (e faturar o quanto
antes)

Como ser FLEXÍVEL ?
19. Conhecer (representar) as alternativas de gestão de curto prazo para exploração
sistemática
33
Simulação com capacidade finita
Acionamento x Dimensionamento x Projetos
Simuladores voltados a programação do dia-a-dia e acionamento
Factor, Schedulex, Leitstand, AHP-Leitstand, Auto-sched, Moopi,
MPSwin, Infor, CA-Quick, Pacemaker, Preactor, CB/Plan,
Response Agent, Fact, MicroPlanner, Metashop, Job-shop, SynQuest, Ortems, AutoSched, Broner, Process, See-The-Future (BR)
Simuladores voltados a programação do dia-a-dia
Manugistics, Goal System, Thru-put, Drummer, Rhythm
Simuladores voltados ao dimensionamento do sistema de produção
Promodel, Arena, See-why, Forssight
Simuladores voltados a gestão de projetos
Scitor OS Suite, Concerto
34
Exemplo simplificado de hierarquias de objetos e seus respectivos
atributos para um simulador de manufatura (Fábrica)
Fábrica
Recursos
Onde
Máquinas
Operadores
Engenharia
O que e Como Faz
Plano de Produção
Quanto
Ferramentas
Clientes
Tempo de
Transporte
Prioridade
Tipo:
Contínuo, Taxa
Rendimento
Tempo Setup
Custo Variável
Habilitação
Serventia:
Processamento,
Setup, Transporte
Pedidos
Valor de Venda
Classe
Horários
Data
Lista de Operações e
Alternativas
Itens
Tipo Item
: Manufaturado
Unidade: Kg, Peças
Custo
Lista de Materiais
Componência
Roteiros de
Produção
Lote de Produção
Quantidade
Estoques
Acabado
, Manufaturado
e Materiais,
Lote de Tranferência
Alternativas
de Recursos
Taxa de Produção
Situação
Classe
Tipos de Operação
Operador
Horários
Ferramenta
35
Fontes
BITTENCOURT , Guilherme - Notas de Aula da Disciplina DAS 6607 2007
COSTA, R, 1996, Pontualidade total na produção sob encomenda:
conceito, tecnologia e uso da simulação computacional na gestão do
chão de fábrica. Ph.D dissertação, Universidade Federal do Rio de
Janeiro, Rio de Janeiro, Rio de Janeiro, Brasil.
36
Obrigado pela atenção
e-mail:
[email protected]
[email protected]
Página: www.trilhaprojetos.com.br
37