1 Inteligência Artificial Aplicada a Sistemas de Controle e Automação DAS 6607 Simulador da...

1

Inteligência Artificial Aplicada aSistemas 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

2

TópicosTópicos

IntroduçãoExemplo 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ábricaApresentação básica de um simulador de produção desenvolvido para uma empresa

3

Introdução: O que é Inteligência Introdução: O que é Inteligência Artificial?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.

4

Introdução ao ambiente Introdução ao ambiente fabrilfabril

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

5

SEQÜENCIAMENTO DA SEQÜENCIAMENTO DA PRODUÇÃOPRODUÇÃO

Problema Introdutório:Problema Introdutório:O Caso dos LeitoresO Caso dos Leitores

6

EnunciadoEnunciadoParte 1Parte 1

Alberto (A), Bruno (B), Carlos (C) e Daniel (D) moram juntos. Aos domingos, pela manhã, gostam de ler os jornais O Globo (GlGl), Jornal do Brasil (JBJB), O Dia (DiDi) e o semanário Casseta e Planeta (CPCP), 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.

7

DadosDados

Ordem

LEITOR ACORDA Tempo de leitura

Alberto 8:30 JB Gl Di CP

60 min 30 min 2 min 5 min

Bruno 8:45 Gl Di JB CP

75 min 3 min 25 min 10 min

Carlos 8:45 Di Gl JB CP

5 min 15 min 10 min 30 min

Daniel 9:30 CP JB Gl Di

90 min 1 min 1 min 1 min

8

QuestõesQuestõ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 ?

9

QuestõesQuestõ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?

10

QuestõesQuestõ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 ?

11

SEQÜENCIAMENTO DA SEQÜENCIAMENTO DA PRODUÇÃOPRODUÇÃO

Problema Introdutório:Problema Introdutório:O Caso dos LeitoresO Caso dos Leitores

12

AnalogiasAnalogias

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.

13

Solução GráficaSoluçã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.

14

Solução 1Solução 1Ordem

LEITOR ACORDA Tempo de leitura

Alberto 8:30 JB Gl Di CP60 m 30 m 2 m 5 m

Bruno 8:45 Gl Di JB CP75 m 3 m 25 m 10 m

Carlos 8:45 Di Gl JB CP5 m 15 m 10 m 30 m

Daniel 9:30 CP JB Gl Di90 m 1 m 1 m 1 m

JB

Gl

Di

CP

DanielAlberto Bruno Carlos

9:30 10:008:30 8:45 12:0010:15 11:00

Jornal Leitor 1 Leitor 2 Leitor 3 Leitor 4

JB

Gl

Di

CP

AA

11:5111:51

BB

CC

DD

DD

DD

DD

BB

BB

BB

CC

CC

CC

AA

AA

AA

15

Solução 1 / ObservaçõesSolução 1 / Observações

• O Roteiro (que é uma restrição do problema) pode levar a jornais ociosos .

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.

10:00

JB

Gl

Di

CP

12:0010:15 11:009:30 10:008:30 8:45

DanielAlberto Bruno Carlos

Ordem

LEITOR ACORDA Tempo de leitura

Alberto 8:30 JB Gl Di CP60 m 30 m 2 m 5 m

Bruno 8:45 Gl Di JB CP75 m 3 m 25 m 10 m

Carlos 8:45 Di Gl JB CP5 m 15 m 10 m 30 m

Daniel 9:30 CP JB Gl Di90 m 1 m 1 m 1 m

16

Solução 1 / ObservaçõesSolução 1 / Observações

• A Seqüência (que é fruto da solução adotada) pode levar a

leitores ociosos .

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.

JB

Gl

Di

CP

12:0010:15 11:009:30 10:008:30 8:45

DanielAlberto Bruno Carlos

Ordem

LEITOR ACORDA Tempo de leitura

Alberto 8:30 JB Gl Di CP60 m 30 m 2 m 5 m

Bruno 8:45 Gl Di JB CP75 m 3 m 25 m 10 m

Carlos 8:45 Di Gl JB CP5 m 15 m 10 m 30 m

Daniel 9:30 CP JB Gl Di90 m 1 m 1 m 1 m

Jornal Leitor 1 Leitor 2 Leitor 3 Leitor 4

JB

Gl

Di

CP

AA

BB

CC

DD

DD

DD

DD

BB

BB

BB

CC

CC

CC

AA

AA

AA

10:15

17

Solução 3Solução 3Ordem

LEITOR ACORDA Tempo de leitura

Alberto 8:30 JB Gl Di CP60 m 30 m 2 m 5 m

Bruno 8:45 Gl Di JB CP75 m 3 m 25 m 10 m

Carlos 8:45 Di Gl JB CP5 m 15 m 10 m 30 m

Daniel 9:30 CP JB Gl Di90 m 1 m 1 m 1 m

JB

Gl

Di

CP

12:0011:159:458:30 8:45

DanielAlberto Bruno Carlos

Jornal Leitor 1 Leitor 2 Leitor 3 Leitor 4

JB

Gl

Di

CP

AA

11:3011:30

BB

CC

DD

DD

DD

DD

BB

CC

CC

AA

AA

AA

BB

BB

CC

18

Conclusão do ProblemaConclusão do ProblemaComparando-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).

Solução Fim Planejado Esperas Forçadas

1 11:45 Bruno de 10:03 até 11:11

Carlos de 9:15 até 11:01

2 11:45 ---

3 11:30Alberto de 8:30 até 9:15

Bruno de 8:45 até 9:05

Daniel de 9:30 até 9:45

JB

Gl

Di

CP

12:0011:159:458:30 8:45

DanielAlberto Bruno Carlos

11:30

19

ConclusãoConclusão

Portanto, decisões “locais” que, à primeira vista, possam parecer irracionais,

JB

Gl

Di

CP

12:0011:159:458:30 8:45

DanielAlberto Bruno Carlos

11:30

Por exemplo,

Alberto acorda, todos continuam

dormindo, o seu jornal preferido

(JB) está disponível, e mesmo

assim ele é impedido de lê-lo

antes de Carlos que, por sua vez,

só acordará 15 minutos depois, e

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 !

20

Análise do Melhor CasoAnálise do Melhor Caso

Como provar que esta resposta é ótima ?

21

Solução ÓtimaSolução Ótima

• O que não significa que seja a única solução ótima !

JB

Gl

Di

CP

12:0011:159:458:30 8:45

DanielAlberto Bruno Carlos

11:3011:30

• Por exemplo, podemos só inverter os 2 últimos leitores do

Planeta na Solução 3 :

22

Universo de SoluçõesUniverso 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(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 !)44 = 331.776 soluções = 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 !)(n !)mm,

onde nn são os itens e mm são os recursos envolvidos no problema.

23

Complexidade do Problema 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 ? Expresse este

tempo na maior unidade possível (isto é, segundos, minutos,

horas, dias, semanas, meses ou o que for apropriado).

331.776 soluções / 1000 soluções por segundo / 60= 5 ½ minutos

24

Natureza Combinatória Natureza Combinatória ExplosivaExplosiva

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:

Leitores/ Itens

Jornais /Máquinas

Universo deSoluções

Tempo deProcessamento

Requerido

4 4

5 4

6 4

7 4

331.776

2,1 x 10 8

2,7 x 10 11

6,5 x 10 14

5,5 minutos

2,4 dias !

8,5 anos !!

205 séculos !!!!205 séculos !!!!

25

Técnicas para ResolverTécnicas para Resolver o Problema 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).

26

Métodos heurísticosMétodos heurísticosDiante da complexidade do problema de programação,

analisaremos agora quatro métodos estruturados para resolução do problema. São eles:

PROGRAMAÇÃO PARA FRENTEPROGRAMAÇÃO PARA FRENTE (pedido a pedido) => comumente (embora imprecisamente) chamado de “FORWARD PLANNING”

PROGRAMAÇÃO PARA TRÁS BASEADA NA ABORDAGEM PROGRAMAÇÃO PARA TRÁS BASEADA NA ABORDAGEM MRPMRP (pedido a pedido) => comumente (embora imprecisamente) chamado de “BACKWARD PLANNING”

PROGRAMAÇÃO BASEADA NA TEORIA DAS RESTRIÇÕESPROGRAMAÇÃO BASEADA NA TEORIA DAS RESTRIÇÕES (operação a operação) => também chamado de “PROGRAMA-ÇÃO MISTA”

PROGRAMAÇÃO POR SIMULAÇÃOPROGRAMAÇÃO POR SIMULAÇÃO (operação a operação) => também chamado (embora imprecisamente) de “PROGRAMA-ÇÃO POR CAPACIDADE FINITA”

27

Programação por SimulaçãoProgramação por Simulação

Com os dados do problema dos Leitores, construa uma solução estruturada baseada na “PROGRAMAÇÃO POR PROGRAMAÇÃO POR SIMULAÇÃOSIMULAÇÃ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.

28

Regras Heurísticas de CarregamentoRegras Heurísticas de Carregamento

PEPSPEPS (Primeiro a entrar deve ser o primeiro a sair)

MTPMTP (Item de menor tempo de processamento deve ser processado primeiro)

MDEMDE (Item com data de entrega mais apertada deve ser processado primeiro)

Maior MultaMaior Multa (Item que induz a maior multa deve ser processado primeiro)

Maior PreçoMaior Preço (Item que induz a maior preço deve ser processado primeiro)

Menor FolgaMenor Folga (Item que tem a menor folga calculada como:

(Data de entrega - Instante da decisão) - Tempo remanescente de processamento

Razão CríticaRazão Crítica (Item que tem a menor folga calculada como:

(Data de entrega - Instante da decisão) / Tempo remanescente de processamento

“... o número de regras de descarregamento de filas existentes só é limitado pela nossa ingenuidade ! ”

Você é capaz de imaginar outras regras heurísticas de descarregamento de filas ?

29

I

A 0 Atraso

Freqüência

a) situação “quase ótima” em termos de cumprimento de prazo de entrega.

0 I

A

b) regra ignorando os tempos de processamento e datas de entrega.Ex: PEPS

0 I

A

c) regra baseada em tempos de processamento.Ex: MTP

0 I

A

d) regra baseada em data de entrega (carga e capacidade balanceadas).Ex: MDE

0 I

A

e) regra baseada em data de entrega (carga e capacidade desbalanceadas).Ex: MDE

PEDIDOSADIANTADOS

PEDIDOSATRASADOS

30

Complicadores do ProblemaComplicadores 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

31

PONTUALIDADE TOTALPONTUALIDADE TOTAL Diante de tal complexidade, como chegar Diante de tal complexidade, como chegar

lá ?lá ?

PONTUALIDADE PONTUALIDADE TOTAL é :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

32

PONTUALIDADE TOTALPONTUALIDADE TOTAL

Ações indicadasAções indicadas Como ser PONTUAL PONTUAL ?

1. Planejar antecipadamente2. Programar realisticamente considerando os limites existentes de capacidade3. Programar com folga4. Programar detalhadamente o curto prazo5. Explorar as possibilidades de seqüenciamento existentes6. Explorar as possibilidades ligadas ao uso de máquinas e roteiros alternativos7. Explorar as possibilidades de ajuste do nível de capacidade

(e.g. horas-extras, subcontratações)8. Explorar as possibilidades de apressamento (i.e. expeditação) de pedidos urgentes9. Explorar as possibilidades de antecipação do recebimento de materiais críticos10. Explorar as possibilidades ligadas ao uso de projetos, processos e materiais

alternativos11. Antecipar para os clientes possíveis problemas de entrega, quando inevitáveis12. Prometer prazos e/ou decidir aceitar encomendas considerando os compromissos

já assumidos13. Acompanhar o andamento e a pontualidade dos processos internos14. Replanejar rapidamente e sempre que fatos significativos aconteçam sem terem

sido previstos

33

PONTUALIDADE TOTALPONTUALIDADE TOTAL

Ações indicadasAções indicadas Como fazer BARATO BARATO ?

15. Evitar grandes antecipações na produção de componentes não-críticos16. Apresentar os custos e benefícios de cada possível solução de programação17. Identificar as operações e recursos críticos para concentrar neles os ajustes de

capacidade (horas-extras, subcontratações)

Como fazer RÁPIDO RÁPIDO ?18. Programar para dispor dos equipamentos o mais cedo possível (e faturar o quanto

antes)

Como ser FLEXÍVEL FLEXÍVEL ?

19. Conhecer (representar) as alternativas de gestão de curto prazo para exploração sistemática

34

Simulação com capacidade finita Simulação com capacidade finita Acionamento x Dimensionamento x ProjetosAcionamento x Dimensionamento x Projetos

Simuladores voltados a programação do dia-a-dia e acionamentoSimuladores voltados a programação do dia-a-dia e acionamentoFactor, Schedulex, Leitstand, AHP-Leitstand, Auto-sched, Moopi, MPSwin, Infor, CA-Quick, Pacemaker, Preactor, CB/Plan, Response Agent, Fact, MicroPlanner, Metashop, Job-shop, Syn-Quest, Ortems, AutoSched, Broner, Process, See-The-Future (BR)

Simuladores voltados ao dimensionamento do sistema de produçãoSimuladores voltados ao dimensionamento do sistema de produçãoPromodel, Arena, See-why, Forssight

Simuladores voltados a gestão de projetosSimuladores voltados a gestão de projetosScitor OS Suite, Concerto

Simuladores voltados a programação do dia-a-diaSimuladores voltados a programação do dia-a-diaManugistics, Goal System, Thru-put, Drummer, Rhythm

35

Horários

Tipos de Operação

Situação

Custo Variável

Tempo Setup

Rendimento Classe

Estoques

Tipo: Contínuo, Taxa Habilitação Serventia:

Processamento, Setup, Transporte

Data

Acabado, Manufaturado

e Materiais,

Máquinas Operadores Ferramentas

Pedidos

Clientes

RecursosOnde

Plano de ProduçãoQuanto

EngenhariaO que e Como Faz

Fábrica

Exemplo simplificado de hierarquias de objetos e seus respectivos Exemplo simplificado de hierarquias de objetos e seus respectivos atributos para um simulador de manufatura (Fábrica)atributos para um simulador de manufatura (Fábrica)

Horários

Tempo de Transporte

Valor de Venda

Quantidade

Prioridade Tipo Item: Manufaturado

Itens

Unidade: Kg, Peças

Custo

Lista de Materiais

Componência

Lista de Operações e Alternativas

Roteiros de Produção

Alternativas de Recursos Taxa de Produção

Classe

Lote de Produção

Lote de Tranferência

Operador

Ferramenta

36

FontesFontes

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.

37

Obrigado pela atençãoObrigado pela atenção

e-mail: e-mail:

denis@trilhaprojetos.com.brdenis@trilhaprojetos.com.br

denispin@das.ufsc.brdenispin@das.ufsc.br

Página: www.trilhaprojetos.com.brPágina: www.trilhaprojetos.com.br