Modelização de Sistemas
Produtivos
Métodos de Análise de Sistemas
Produtivos
Etapas
1. Pesquisa geral sobre o tema proposto
2. Definição e elaboração do problema
3. Pesquisa de algoritmos de encaminhamento
4. Simulação manual para prioritização de produtos
5. Implementação e teste do sistema
Grupo 1 - Masp 2002
2
1.
• Rede
Pesquisa geral sobre o tema
proposto
Agentes (produtores, fornecedores e consumidores)
Bens ( matérias-primas ou produtos acabados
• Mecanismos de atribuição de tarefas baseados em leilões
Estabelecimento de regras de conduta
• Protocolo de mercado
Disciplina na forma de negociar
Alocação de tarefas
Grupo 1 - Masp 2002
3
2. Definição e elaboração do problema
• Problema de escalonamento de produtos
• Mecanismo de leilão para os produtos não se
adapta a este tipo de problemas
Porquê ?
• Parâmetros fixos (custos e tempos de operação)
• Prioridades atribuidas em função de parâmetros fixos
Grupo 1 - Masp 2002
4
2. Definição e elaboração do problema
Especificação:
• Conjunto de grafos representativos de um qualquer sistema
produtivo
• Cada rede deverá ter no máximo 4 operações
• Atribuição de máquinas a centros de operação por produto
• Existência de apenas 6 máquinas e 5 produtos
•Para cada rede deveriam estar definidos os tempos de
execução e os custos associados a cada arco
• Restrições de ocupação de máquinas
Grupo 1 - Masp 2002
5
2. Definição e elaboração do problema
Grupo 1 - Masp 2002
6
3. Algoritmos de encaminhamento
Algoritmo de Dijkstra
Dijkstra com variável de ocupação de rede
Método ‘k shortest path’
Algoritmo A star
Grupo 1 - Masp 2002
7
Algoritmo de Dijkstra
• Para cada nó da rede define-se o caminho
mínimo relativamente ao nó inicial
• O cálculo do caminho mínimo baseia-se na
soma pesada de critérios (tempo e custo)
que ligam cada nó
Grupo 1 - Masp 2002
8
Algoritmo de Dijkstra - exemplo
Produto V
Operação 1
Operação 2
Operação 3
Operação 4
19
B
7 ,4
8
E
A
7
0
5 ,2
C
A
14 4 ,5
D
9 ,8
3 ,7
29
7 ,7
12
8 ,4
31
5 ,5
10 ,3
5 ,3
2 ,5
23
3 ,6
4 ,4
D
16
E
2 ,5
C
F
3 ,2
2 ,6
29
21
Legenda: Tempo.custo
Etiqueta : tempo+custo
Grupo 1 - Masp 2002
9
Algoritmo de Dijkstra com variável de
ocupação de rede
• Implementação do algoritmo de Dijkstra
com a a adaptação à ocupação da rede
• É criada uma variável adicional que define
em cada momento se a recurso a utilizar (no
nosso caso, a máquina) está livre
Grupo 1 - Masp 2002
10
Dijkstra com variável de ocupação
de rede
Modelo matemático
Função objectivo:
N N
MIN  
 i 1 J 1
 (c
N
q 1
iJ

* xijq * p1 _ ij )  (t iJ * xijq * p 2 _ ij ) 


Restrições:
N
1.
2.
N
q
x

x
  ik
q
ki
; i=1,...,N q=1,...,N
(Assegura a continuidade da rede )
k 1
k 1
xkiq  0,1
Grupo 1 - Masp 2002
11
Dijkstra com variável de ocupação
de rede
Definição de variáveis:
v
ciJ
- custo de processamento (i,j)
v xijq  1
- se (i,j) encontrar-se ocupado no processamento de
xijq  0
um produto, caso contrário
v p1_ ij
1_ ij
- Peso da decisão em se optar pelo peso do pcusto
v p 2 _ ij
- Peso da decisão em se optar pelo peso do tempo
 p2 _ ij  100%  p1_ ij
Grupo 1 - Masp 2002
12
Método ‘k shortest path’
• Equivalente ao método de Dijkstra
• Para cada nó da rede define-se o caminho
mínimo relativamente ao nó final
• Possui um algoritmo que permite em cada
momento determinar os caminhos
alternativos caso um nó esteja ocupado
Grupo 1 - Masp 2002
13
Algoritmo de ‘K shortest path’ - exemplo
Legenda: Tempo.custo
Etiqueta : tempo+custo
Grupo 1 - Masp 2002
14
Método ‘k shortest path’
Fórmula para o cálculo da perda de distância:
(e)= l(e) + d(head(e),t)-d(tail(e),t)
em que:
(e) : corresponde à variação no caminho total com a
inclusão do novo braço e.
l(e) : valor de percorrer o novo braço e
d(head(e),t): distância mínima associada ao nó que
separa o Início do arco e e o nó final
d(tail(e),t): distância mínima associada ao nó que
separa o fim do arco de e o nó final
Grupo 1 - Masp 2002
15
Método ‘A Star’
• Utiliza-se um método de determinação do
caminho mínimo ( Dijkstra ou k shortest
path)
• Para cada nó da rede define-se os valores de
todos os percursos possíveis relativamente a
um nó (inicial ou final)
• Permite recalcular o caminho mínimo caso
haja uma alteração dos parâmetros do
caminho desde o início
Grupo 1 - Masp 2002
16
Algoritmo de ‘A Star’ – exemplo
Produto I
Legenda: Tempo.custo
Etiqueta : tempo+custo
Grupo 1 - Masp 2002
17
Método A*
• Utiliza-se um método de determinação do
caminho mínimo ( Dijkstra ou k shortest path);
• Para cada nó da rede define-se os valores de todos
os percursos possíveis relativamente ao nó final
com base em estimativas, não necessitando ter
informação exacta;
• Permite recalcular o caminho mínimo caso haja
diferenças entre a informação da rede e o ambiente
encontrado;
Grupo 1 - Masp 2002
18
Método A*
f v  gv  c.hv
g[v]
h[v]
c
distância actual ao nó seguinte;
estimação da heuristica da distância do nó n até ao
objectivo;
constante.
Grupo 1 - Masp 2002
19
4. Simulação manual para
prioritização de produtos
• Objectivo:
– Determinar o critério que define as prioridades
de entrada dos produtos
– Melhorar o desempenho do sistema:
• Menores custos globais ...
• Menor tempo global ...
... de execução de todos os produtos
Grupo 1 - Masp 2002
20
Simulação manual para prioritização
de produtos
• Critérios:
– Data de início e número de referência do
produto
– Maior tempo de execução
– Menor tempo de execução
– Maior custo
– Menor custo
– Maior relação custo/tempo
– Prazo de entrega
Grupo 1 - Masp 2002
21
Simulação manual para prioritização
de produtos
Relação de custos por produto para cada critério
Grupo 1 - Masp 2002
22
Simulação manual para prioritização
de produtos
Relação de datas de fim por produto para cada critério
Grupo 1 - Masp 2002
23
Simulação manual para prioritização
de produtos
Critério
Custos
Tempos
Custos + Tempos
4
2
6
Maior tempo de execução
2
1
3
Menor tempo de execução
4
2
6
Maior custo
7
1
8
Menor custo
4
0
4
Maior relação custo/tempo (utilização do caminho
óptimo)
3
0
3
prazo de entrega
2
3
5
Data de início e número do produto
Número de produtos que cada critério consegue optimizar
Grupo 1 - Masp 2002
24
Simulação manual para prioritização
de produtos
Critério
Custos
Tempos
Custos + Tempos
26
168
194
Maior tempo de execução
122
215
337
Menor tempo de execução
47
179
226
Maior custo
0
307
307
Menor custo
25
248
273
Maior relação custo/tempo (utilização do caminho
óptimo)
42
378
420
prazo de entrega
31
105
136
Data de início e número do produto
Desvio do valor óptimo para cada critério
Grupo 1 - Masp 2002
25
Simulação manual para prioritização
de produtos
• Conclusão
– Em função do parâmetro custo temos que o
critério de escolha ‘Maior Custo’ optimiza a
solução
– Em função do parâmetro tempo, vemos que a
melhor escolha é o critério ‘Datas de fim’
– No global vemos que o melhor desempenho é
obtido através da escolha do critério ‘Data de
fim’
Grupo 1 - Masp 2002
26
5. Implementação e teste do sistema
• O sistema foi implementado em MSExcel
utilizando o algoritmo já definido:
Dijkstra com variável de ocupação da rede
Grupo 1 - Masp 2002
27
5. Implementação e teste do sistema
• Dados de entrada
Custo e tempo dos arcos
Pesos de decisão
Prioridades de entrada
Tempo de colocação
Quantidade
• Dados de saída
Caminho Mínimo
Tempo de ocupação da máquina
Custo do caminho percorrido
Custo do caminho óptimo
Grupo 1 - Masp 2002
28
Implementação e teste do sistema
• Determinação do caminho mínimo em função dos
parâmentros
• Importância atribuída pelo decisor ao custo e tempo
• Ocupação prévia da máquina
• Tempos e custos de operação
• Tempos de ocupação em cada máquina
•Quantidade de produto
• Tempos de colocação
Grupo 1 - Masp 2002
29
Implementação e teste do sistema
(Etapas)
• 1º Determinação do caminho mínimo de forma independente
• 2º Introdução de restrição de ocupação
1 Máquina
1 Produto, em cada instante
Evitar sobreposição no escalonamento
Como?
Tempo de Ocupação Dinâmico
Grupo 1 - Masp 2002
30
Tempo de Ocupação Dinâmico
Tempo de Ocupação Dinâmico (TOD)= Tempo Fixo + Atraso
Atraso = Tempo Espera até Máquina estar Livre
Cálculo do caminho mínimo em função de TOD
Dois Tipos de Soluções Possíveis
Grupo 1 - Masp 2002
31
Tempo de Ocupação Dinâmico
TOD diferente Tempo Fixo
Soluções
Esperar e operar
na mesma máquina
Grupo 1 - Masp 2002
Seguir caminho
alternativo
32
Referências
• www.fe.up.pt/~ee97069/Masp
• Magalhães, Álvaro; Ribeiro, Bernardo;
Bessa, João; Elawar, José Lúcio; Marques,
Teresa - Relatório final ‘Modelização do
Sistema Produtivo’, 2002
Grupo 1 - Masp 2002
33