Modelo matemático para resolução de problemas de …



[pic]

Métodos de Análise de Sistemas Produtivos

Modelização do Sistema Produtivo

12 de Junho de 2002

Alunos:

Álvaro Magalhães

Bernardo Ribeiro

João Bessa

José Lúcio

Teresa Marques

Docentes:

Fernando Manuel Ferreira Lobo Pereira

Gil Manuel Magalhães de Andrade Gonçalves

Índice

1. Introdução 2

2. Pesquisa geral 4

3. Definição do problema 5

4. Modelos Matemáticos 9

Algoritmo de Dijkstra 9

Dijkstra com variável de ocupação de rede 13

Método ‘k shortest path’ 14

Algoritmo A star 20

5. Simulação 23

Os Grafos 24

Simulações prioritizando a entrada dos produtos 29

Conclusões 36

6. Implementação 38

7. Resultados 41

8. Conclusão 43

9. Anexos 44

Anexo 1 – Resultados da pesquisa inicial 44

Introdução

Este documento pretende descrever todo o processo de pesquisa e implementação baseado no tema inicial: Modelização do sistema produtivo (market based approach).

De uma maneira geral podemos dividir o trabalho em 4 partes fundamentais:

- Pesquisa geral sobre o tema proposto (1 mês)

- Definição e elaboração do problema (2 semanas)

- Pesquisa de algoritmos de encaminhamento (1.5 semanas)

- Simulação manual para prioritização de produtos (1.5 semanas)

- Implementação e teste do sistema (3 semanas)

Na pesquisa geral foram abordados de uma forma genérica vários conceitos relaccionados com mecanismos de atribuição de tarefas baseadas em leilões, ou seja, mecanismos em que os recursos são atribuídos dinâmicamente de acordo com condições renegociáveis ao longo do processo.

O processo de definição e elaboração do problema consistiu na concepção de um conjunto de grafos, cada um definindo os possíveis percursos de um produto por um determinado conjunto de máquinas. De referir nesta etapa a existência de repetições de máquinas no percurso de cada produto e da partilha das mesmas máquinas em todos os grafos. Para cada máquina é definido (no seu arco) um conjunto de tempo de execução e custo de execução. Foi considerado variável consoante o percurso escolhido, ou seja, para a mesma máquina os tempos e custos variam de acordo com a máquina anterior.

A pesquisa de algoritmos consistiu no levantamento de vários algoritmos de encaminhamento (caminho mínimo) já existentes. Através deste levantamento foi possível compreender como abordar o problema na tentativa de escolher apenas caminhos óptimos para todos os produtos.

A simulação manual permitiu, para além de testar o algoritmo escolhido verificar quais os vários mecanismos de atribuição de prioridades mais vantajosos para o sistema. De uma forma mais geral, esta etapa permitiu analisar o comportamento do algoritmos à ordem de entrada dos produtos na rede.

A parte final do trabalho consistiu na implementação de um sistema simples que permitisse verificar a funcionalidade do sistema, tentando de uma forma mais automática obter resultados para o nosso problema.

Estas fases estarão descritas mais detalhadamente ao longo do documento sendo referidas as principais conclusões de cada etapa.

Pesquisa geral

A pesquisa geral, tal como já referido, focou os mecanismos de atribuição de tarefas baseadas em leilões, ou seja, mecanismos em que os recursos são atribuídos dinâmicamente de acordo com condições renegociáveis ao longo do processo. De facto, apesar desta pesquisa ter sido enriquecedora, os conceitos adquiridos foram um pouco relegados no desenrolar do trabalho, uma vez que o problema definido não se mostrou adquado à implementação deste tipo de mecanismos.

Sendo o problema proposto um problema de escalonamento com rede bem determinadas para cada produto, o mecanismo de leiloar os recursos não se adapta uma vez que:

- os parâmetros (os tempos e custos) depois de definidos são fixos para cada produto

- as prioridades são também atribuídas de acordo com parâmetros fixos: datas de fim, tempos de execução, custos de execução de cada produto.

Após a definição das prioridades, a atribuição de uma determinada máquina a um produto é definida de acordo com a disponibilidade da máquina no tempo desejado. Após a atribuição dos recursos para um produto, apenas o tempo de espera para entrada na máquina poderá influênciar a atribuição dos recursos para o produto seguinte.

Não consideramos por isso relevante a aplicação dos conhecimentos adquiridos nesta fase já que não consideramos existir negociação de parâmetros neste problema.

Definição do problema

O objectivo do trabalho é partir de um conjunto de grafos representativos de um qualquer sistema produtivo e solucionar o problema de atribuição de máquinas a centros de operação por produto, tendo em conta que os produtos podem ser produzidos simultaneamente, existindo por isso restrições de ocupação de máquinas.

Na criação dos grafos, representativos de um qualquer sistema produtivo, foram estabelecidos os seguintes parâmetros:

• Cada rede deverá ter no máximo 4 operações definidas através de números

• Existência de apenas 6 máquinas, representadas por letras maiúsculas

• Existência de 5 produtos, representados por números romanos

• Para cada rede deveriam estar definidos os tempos de execução e os custos associados a cada arco

Após a resolução dos problemas para uma primeira rede, será feita a abordagem de integração para os restantes produtos através da combinação entre as várias redes.

Foram criados os seguintes grafos:

Produto I

[pic]

Figura 1 – Grafo representativo do produto I

Produto II

[pic]

Figura 2 – Grafo representativo do produto II

Produto III

[pic]

Figura 3 – Grafo representativo do produto III

Produto IV

[pic]

Figura 4 – Grafo representativo do produto IV

Produto V

[pic]

Figura 5 – Grafo representativo do produto V

Modelos Matemáticos

Existem vários modelos matemáticos para resolução de problemas de afectação de operações a recursos produtivos. Os diversos métodos existentes apoiam-se nos algoritmos de caminho mínimo, em especial o algoritmo de Dijkstra.

Cada método apresentado pretende demostrar o funcionamento do algoritmo para um dos grafos construídos para o enunciado. Para os modelos apresentados foi escolhido como exemplo o produto I, sendo todos os cálculos efectuados para esse produto.

Algoritmo de Dijkstra

Letra representa recursos e algarismos representam operação.

Forma Tabelar de resolver o problema especifico:

Dentro de ( ) está a atribuição a cada recurso de um valor, para que possa ser identificado como um nó. Um mesmo recurso pode então estar representado por mais de um nó diferente.

|I (0) |A1 (1) |

|  | Valor mínimo dos nós associados às últimas operações possíveis | |

|  | Valor mínimo óptimo final, calculado através do mínimo dos valores a | |

| | | | | | | | | | |

|E |>>> valor mínimo | | | | | | |

A solução deste problema é a seguinte sequência: E1 >> D2 >> C3

Esta solução apenas considera um valor fixo para cada arco, considerando para tal que tanto a variável Custo como Tempo têm um peso unitário.

Em seguida, demonstra-se a resolução do mesmo problema mas considerando o valor de cada ramo em função das duas variáveis já referidas.

W = T*x + C*y

|I (0) |A1 (1) |F1 (2) |E1 (3) |C2 (4) |B2 (5) |D2 (6) |

|  |5x + 5y |4x + 3y |3x + 2y |10x + 11y |7x + 8y |6x + 6y |

|E |  | |  |8x + 5y |  |6x + 5y |

|  |  |  |  |  |  |  |

| | | | |8> solução óptima a encontrar;

Pode existir mais de que um nó associado a uma mesmo recurso, por isso convém ter presente quais os nós respectivos para cada recurso, para que depois de encontrada a solução óptima se poder fazer o escalonamento em termos temporais dos diversos recursos. A identificação através dos nós só serve para resolução do problema, já que um recurso pode aparecer mais de que uma vez na rede, e nessa altura terá que ser tratado como se diferentes recursos se tratassem.

1ª OPERAÇÃO (1)

E1 = min { E0 + W0 [1] } // só entra um arco em cada um destes nós por

E2 = min { E0 + W0 [2] } isso a solução até aqui é imediata;

E3 = min { E0 + W0 [3] }

2ª OPERAÇÃO (2)

E4 = min { E1 + W1 [4] ; E2 + W2 [4] }

E5 = min { E1 + W1 [5] }

E6 = min { E2 + W2 [6] ; E3 + W3 [6] }

3ª OPERAÇÃO (3)

E7 = min { E4 + W4 [7] }

E8 = min { E5 + W5 [8] ; E6 + W6 [8] }

E9 = min { E4 + W4 [9] ; E6 + W6 [9] }

4ª OPERAÇÃO (4)

E10 = min { E7 + W7 [10] ; E5 + W5 [10] }

E11 = min { E7 + W7 [11] ; E8 + W8 [11] ; E9 + W9 [11] }

SOLUÇÃO FINAL:

E12 = min { E8 ; E10 ; E11 } >>> solução óptima

Modelo matemático generalizado

Para todas as operações que compõem a rede, calcula-se o valor mínimo (E) para todos os nós que lhe estão associados, em que o valor mínimo de cada nó é encontrado da seguinte forma:

Sendo h = [0,...,r] o conjunto de nós pertencentes à rede, “m” o índice do nó para o qual se está a calcular o valor mínimo ( m ε h ), e [n,...,t] o intervalo de índices associados aos nós precedentes, que têm arcos a “entrar” no nó “m”...

Em = min { En + Wn [m] ; .... ; Et + Wt [m] }, para m ε [0,r-1]

Tendo que para inicializar E0 = 0;

E a solução óptima é encontrada quando se encontrar o valor mínimo para Er. Er é calculado da seguinte forma:

Er = min { Ey ;...; Ex } em que [y,...,x] ε [0,...,r-1] e que define o conjunto de nós que têm arcos com destino ao nó “r”;

De referir que o nó 0 e “r” não estão associados a recursos mas sim a marcas que representam o início e fim da rede;

NOTA:

A fim de se entender este raciocínio, é aconselhável ter presente um dos esquemas das redes que foram criadas.

Dijkstra com variável de ocupação de rede

Este método é idêntico ao método de Dijktra simples para apenas um grafo. Este algoritmo apresenta uma variável extra que representa o estado de ocupação num determinado instante.

A sua aplicação para apenas um grafo é idêntica à acima mencionado tendo por isso sido decidido apenas apresentar o modelo matemático.

Formulação do modelo matemático

Função objectivo:

[pic]

Restrições:

1. [pic] ; i=1,...,N q=1,...,N (Assegura a continuidade da rede )

2. [pic]

Definição de variáveis:

❖ [pic]- custo de processamento (i,j)

❖ [pic] se (i,j) encontrar-se ocupado no processamento de um produto, caso contrário [pic]

❖ [pic]- Peso da decisão em se optar pelo peso do custo [pic]

❖ [pic]- Peso da decisão em se optar pelo peso do tempo [pic]

A ideia subjacente a este modelo será a do operador definir à partida um determinado peso para o custo e para o tempo de forma a permitir uma melhor decisão, tendo sempre em conta a ocupação das máquinas.

Método ‘k shortest path’

Este algoritmo é uma generalização do problema de caminho mínimo em que são obtidos não um mas vários caminhos mínimos unindo um nó inicial s e um nó de destino t. O objectivo é listar k caminhos que unem dois pontos de um grafo com o menor comprimento total.

A ideia essencial deste algoritmo é calcular vários caminhos mínimos partindo não do nó inicial mas do final. Dessa forma é sempre possível conhecer o valor ao ponto inicial em qualquer ponto da rede. É por isso o contrário do normal algoritmo de Dijkstra.

Resolução do problema específico usando a forma tabular:

Letra representa recursos e algarismos representam operação.

Dentro de ( ) está atribuição a cada recurso de um valor, para que possa ser identificado como um nó; um mesmo recurso pode então estar representado por mais de um nó diferente.

Analisando o grafo e considerando a soma dos diferentes parâmetros tempo e custo, considerando-os unitários ou seja com a mesma importância para o problema, obtêm-se a seguinte tabela :

|F |A4 (11) |

|(1| |

|2)| |

|  | Valor mínimo dos nós associados às últimas operações possíveis |

|  | Valor mínimo óptimo final, calculado através do mínimo dos valores a mínimos |

| | Valor que não o mínimo |

|E |>>> valor mínimo |

A solução deste problema é a seguinte sequência: E1 >> D2 >> C3

Em seguida demonstra-se a resolução do mesmo problema mas considerando o valor de cada ramo em função das duas variáveis já referidas.

W = T*x + C*y

|F (12) |A4 (11) |F4 (10) |B3 (9) |C3 (8) |D3 (7) |D2 (6) |

| |0x + 0y |0x + 0y |5x + 1y |5x + 3y |2x + 2y |10x + 4y |

|E | | | |0x + 0y |5x+3y |5x + 2y |

| | | | | | | |

| | | | | | | |

|B2 (5) |C2 (4) |E1 (3) |F1 (2) |A1 (1) |I (0) |

|10x + 6y |7x + 3y |8x + 5y |7x + 5y |12x + 9y |11x+12y |

|11x+9y |5x + 4y | |11x + 5y |12x + 9y |11x + 7y |

| | | |9x+11y |10x + 10y |17x+14y |

| | | | | |15x+15y |

Resolvendo agora o problema em função dos “pesos” das variáveis Tempo e Custo, verifica-se que a solução do problema se mantém a mesma independente dos referidos parâmetros.

No entanto vê-se que os melhores caminhos alternativos podem variar de acordo com os pesos atribuídos aos diferentes parâmetros.

O grande interesse deste método é reconhecer para cada nó qual é o valor mais curto de chegada ao nó final e qual o melhor caminho para o fazer.

|Caminho óptimo |E1 -> 13 |D2 ->7 |C3 -> 0 | |Final 18 |

| |F1-> 12 |D2->7 |C3->0 | |Final 19 |

| |A1->20 |C2->9 |D4->4 |F5->0 |Final 30 |

[pic]

Figura 6 – Caminho mínimo e alternativo para o produto I

Poderemos ver que estes são caminhos directos mas podem ser calculadas as distâncias para caminhos não directos através da inserção de outro caminho da rede. Para o cálculo da perda de distância poder-se-á utilizar a fórmula:

((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

Por exemplo, se não for possível passar pelo nó C3 por alguma impossibilidade e em vez disso formos por B3 temos um acrescento ao caminho mínimo de:

((D2->B3) = -(5+3) +7-6=7

Daqui se pode concluir que alterando o percurso para incluir o nó B3 em vez de C3 são gastas mais 7 unidades de distância.

De notar que se o nó a incluir já pertencer ao caminho óptimo temos que a variação terá o valor zero.

Modelo Matemático

Em seguida passa-se a apresentar um modelo matemático para este problema:

- primeiramente temos uma solução orientada ao nosso problema especifico

- em seguida e em função disso tenta-se retirar um modelo generalizado que sirva para qualquer outro problema deste tipo

ESPECIFICAÇÕES:

W = X*T + Y*C

, em que

W ( Peso total do arco;

T ( Tempo de operação;

C ( Custo de operação;

X,Y ( pesos das variáveis que estão em jogo;

Wi [j] ( Peso do arco com origem em i e destino em j; i,j ( [0,12]

Ek ( Valor mínimo até ao nó k; k ε [0,12]

E [12] = 0 ( Ponto de partida;

E [0] ( Solução óptima a encontrar;

1ª OPERAÇÃO (4)

E12 = min { E11 + E10 + E8 } // o nó final é único e o valor inicial será neste caso é sempre 0

E12 = E11 = E10 = E8 // devido à forma como estamos a considerar o problema

2ª OPERAÇÃO (3)

E9 = min { E11 + W9 [11] }

E8 = min { E12 ; E11 + W8 [11] }

E7 = min { E10 + W7 [10] ; E11 + W7 [11] }

3ª OPERAÇÃO (2)

E6 = min { E9 + W6 [9] ; E8 + W6 [8] }

E5 = min { E8 + W5 [8] ; E10 + W5 [10] }

E4 = min { E9 + W4 [9] ; E7 + W7 [7] }

4ª OPERAÇÃO (1)

E3 = min { E6 + W3 [6] }

E2 = min { E6 + W2 [6] ; E4 + W2 [4] }

E1 = min { E4 + W1 [4] ; E5 + W1 [5] }

SOLUÇÃO FINAL:

E0 = min { E1+ W0 [1] ; E2 + W0 [2]; E3 + W0 [3] } >>> solução óptima

Modelo matemático generalizado:

Para todas as operações que compõem a rede calcula-se o valor mínimo (E) para todos os nós que lhe estão associados, em que o valor mínimo de cada nó é encontrado da seguinte forma:

Sendo:

h = [0,...,r] o conjunto de nós pertencentes à rede

m, o índice do nó para o qual se está a calcular o valor mínimo ( m ε h ),

[n,...,t] o intervalo de índices associados aos nós precedentes, que têm arcos a “entrar” no nó “m”...

Em = min { En + Wm [n] ; .... ; Et + Wm [t] }

para m ε [0,r-1] e m anterior a n

A inicialização ocorre para Er = 0;

A solução óptima é encontrada quando se encontrar o valor mínimo para Er e que é calculado da seguinte forma:

E0 = min { Ey ;...; Ex }

em que [y,...,x] ε [0,...,r-1] e que define o conjunto de nós que têm arcos com destino ao nó “0”.

De referir que o nó 0 e “r” não estão associados a recursos mas sim a marcas que representam o início e fim da rede.

Um algoritmo de trocas englobado neste modelo foi já referido e é formulado matematicamente através de:

( (em[n])= Wm[n] + Em - En)

em que:

em[n] : novo braço a incluir no grafo partindo de um nó inicial m e terminando no nó final n

((em[n]) : corresponde à variação no caminho total com a inclusão do novo braço Em.

Algoritmo A star

A teoria do A* é relativamente simples. Basicamente, cada nó (posição) no gráfico tem três atributos principais: f, g e h.

g é o custo de chegar ao ponto. Este normalmente é o custo de mudar um nó mais o custo do nó pai.

h é a distância à meta - não tem que ser a distância real (A * tem muitas aplicação - pathfinder é um).

Podemos definir uma classe de heurísticas admissíveis de estratégias de procura usando a função evolução:

f(n) =g(n)+h(n). f(n)

representa uma estimativa do custo total do caminho desde o início, por n até ao objectivo.

Também há duas listas, Aberto e Fechado. Na lista aberta estão todos os nós que não foram explorados. Por explorar, quero dizer todas as posições adjacentes que foram abertas (também passou para a lista Aberta), ou não podem ser aberto. Na lista fechada estão todos os nós que foram explorados.

O algoritmo de A* pode ser definido da seguinte forma:

1. Iniciar no primeiro nó;

2. Se o nó actual é o objectivo então, deve-se parar a pesquisa;

3. Se o nó actual não é o nó final, então escolhe-se o caminho com a menor estimativa

4. Repetir o ponto 2.

Desta forma é necessário calcular todos os caminhos conhecidos desde o início até ao fim. Com esta informação da estimativa é possível escolher o melhor caminho.

[pic]

Figura 7 – Aplicação do método – atribuição de valores aos nós

[pic]

Figura 8 – Resultado final

O caminho mínimo está demarcado por uma linha vermelha.

Analisando todos os algoritmos apresentados e o problema concreto que existe para resolver, conclui-se que o método que melhor se adequa ao caso será: Algoritmo de Dijkstra com variável de ocupação.

Como existe a necessidade de combinar vários produtos (várias redes) torna-se necessário saber a cada instante se uma determinada máquina está livre ou ocupada, de modo a que, quando um determinado produto é lançado na produção seja possível saber quais as máquinas que estão a ser usadas e de modo a encontrar o caminho mínimo dentro dos disponíveis.

Simulação

Escolhido o algoritmo a usar o próximo passo será a simulação. Pretende-se simular o comportamento do algoritmo escolhido no plano temporal e para cada um dos grafos associados a cada produto.

Foram feitas várias simulações no sentido de determinar qual a melhor solução em termos de custo e tempo, variando a ordem de entrada dos produtos. As datas de início mínima foram escolhidas de acordo com o que foi considerado a mais problemática das situações, ou seja o início em simultâneo da possível produção de cada produto.

Nesta fase de simulação manual foi utilizado o algoritmo ‘k shortest path’ em detrimento do algoritmo de ‘dijkstra’ por trazer vantagens obvias para a obtenção de um novo caminho quando a máquina do caminho óptimo se encontra ocupada. Tal como já referido, este algoritmo permite conhecer para cada nó qual a ‘distância’ que o ‘separa’ do final. Essa é uma vantagem significativa para esta etapa uma vez que não se torna necessário calcular de novo todos os caminhos para mudar um percurso.

O número de unidades a produzir de cada produto foram atribuídos aleatoriamente.

[pic]

Table 1 – Produtos

Os Grafos

Foram determinados os vários caminhos mínimos, para os 5 produtos, tendo em conta: apenas o tempo, apenas o custo e o custo e o tempo.

Produto I

[pic]

Tabela 1 – Tabela de Relação Tempo/Custo dada pela soma dos 2 parâmetros

[pic]

Tabela 2 – Tabela de Tempos

[pic]

Tabela 3 – Tabela de Custos

É possível verificar que para este grafo considerar o tempo e a soma dos tempos e custos apresenta a mesma solução.

Produto II

[pic]

Tabela 4 – Tabela de Relação Tempo/Custo dada pela soma dos 2 parâmetros

[pic]

Tabela 5 – Tabela de Tempos

[pic]

Tabela 6 – Tabela de Custos

Produto III

[pic]

Tabela 7 – Tabela de Relação Tempo/Custo dada pela soma dos 2 parâmetros

[pic]

Tabela 8 – Tabela de Tempos

[pic]

Tabela 9 – Tabela de Custos

Para este grafo, escolher o tempo ou a soma dos tempos e custos apresenta a mesma solução.

Produto IV

[pic]

Tabela 10 – Tabela de Relação Tempo/Custo dada pela soma dos 2 parâmetros

[pic]

Tabela 11 – Tabelas de Tempos

[pic]

Tabela 12 – Tabela de Custos

Produto V

[pic]

Tabela 13 – Tabela de Relação Tempo/Custo dada pela soma dos 2 parâmetros

[pic]

Tabela 14 – Tabela de Tempos

[pic]

Tabela 15 – Tabela de Custos

Simulações prioritizando a entrada dos produtos

Foram feitas várias simulações que teve como objectivo testar vários escalonamentos temporais, de um conjunto de produtos por diversas máquinas, em que se foi variando o critério de escolha do caminho mínimo e de atribuição de prioridades. Tudo isto no sentido procurar qual o que melhor optimiza o escalonamento, tendo em conta os parâmetros tempo e custo.

1. Simulação com prioridades atribuídas pela data de início e número do produto

Esta simulação pretende demostrar o resultado obtido aquando da atribuição de prioridades pela data de inicio mais cedo. Para datas de inicio iguais o desempate é efectuado pela prioridade dada pelo utilizador a cada produto, neste caso a prioridade foi dada pelo número do produto.

|Produto |Cor |Prioridade |Número de Unidades |

|Produto 1 |10 (custo 18 dim=0) |50 |4 |

|Produto 2 |10 (custo 26 dim=0) |40 |6 |

|Produto 3 |48 |96 |1 |

|Produto 4 |18 |72 |2 |

|Produto 5 |14 |70 |3 |

|Produto 1’ |10 (custo 18 dim=4) |50 |5 |

|Produto 2’ |10 (custo 26 dim=10) |10 |7 |

[pic]

[pic]

Diagrama de Gantt referente à simulação 2

|Produto |Cor |Nº Unidades |Custo Final/unid |Data de Inicio |Data de Fim |

|Produto 3 | |2 |91 |

|Produto 1 |10 (custo 18 dim=0) |50 |3 |

|Produto 2 |10 (custo 26 dim=0) |40 |2 |

|Produto 3 |48 |96 |7 |

|Produto 4 |18 |72 |6 |

|Produto 5 |14 |70 |5 |

|Produto 1’ |10 (custo 18 dim=4) |50 |4 |

|Produto 2’ |10 (custo 26 dim=10) |10 |1 |

[pic]

[pic]

Diagrama de Gantt referente à simulação 3

|Produto |Cor |Nº Unidades |Custo Final/unid |Data de Inicio |Data de Fim |

|Produto 2´ |  |1 |28 |

|Produto 1 |18 |90 |4 |

|Produto 2 |26 |78 |6 |

|Produto 3 |91 |182 |1 |

|Produto 4 |37 |148 |2 |

|Produto 5 |29 |145 |3 |

|Produto 1’ |18 |90 |5 |

|Produto 2’ |26 |26 |7 |

[pic]

[pic]

Diagrama de Gantt referente à simulação 4

|Produto |Cor |Nº Unidades |Custo Final |

|Produto 1 |18 |90 |2 |

|Produto 2 |26 |78 |4 |

|Produto 3 |91 |182 |7 |

|Produto 4 |37 |148 |6 |

|Produto 5 |29 |145 |5 |

|Produto 1’ |18 |90 |3 |

|Produto 2’ |26 |26 |1 |

[pic]

[pic]

Diagrama de Gantt referente à simulação 5

|Produto |Cor |Nº Unidades |Custo Final |

|Produto 1 |18 |90 |4 |

|Produto 2 |26 |78 |6 |

|Produto 3 |91 |182 |1 |

|Produto 4 |37 |148 |2 |

|Produto 5 |29 |145 |3 |

|Produto 1’ |18 |90 |5 |

|Produto 2’ |26 |26 |7 |

[pic]

[pic]

Diagrama de Gantt referente à simulação 6

|Produto | |Nº Unidades |Custo Final/unid |

|Produto 1 |18 |95 |4 |

|Produto 2 |27 |81 |2 |

|Produto 3 |91 |182 |6 |

|Produto 4 |40 |160 |7 |

|Produto 5 |31 |155 |5 |

|Produto 1’ |18 |90 |3 |

|Produto 2’ |27 |27 |1 |

[pic]

[pic]

Diagrama de Gantt referente à simulação 7

|Produto |Cor |Nº Unidades |Custo Final/unid |Data de Inicio |Data de Fim |

|Produto 2´ |  |1 |27 |

|Critério 1 |4 |2 |6 |

|Critério 2 |2 |1 |3 |

|Critério 3 |4 |2 |6 |

|Critério 4 |7 |1 |8 |

|Critério 5 |4 |0 |4 |

|Critério 6 |3 |0 |3 |

|Critério 7 |2 |3 |5 |

Tabela 17 - Número de produtos que cada critério consegue optimizar

|Critérios |Custos |Tempos |Custos + Tempos |

|Critério 1 |26 |168 |194 |

|Critério 2 |122 |215 |337 |

|Critério 3 |47 |179 |226 |

|Critério 4 |0 |307 |307 |

|Critério 5 |25 |248 |273 |

|Critério 6 |42 |378 |420 |

|Critério 7 |31 |105 |136 |

Tabela 18 - Desvio do valor óptimo para cada critério

Analisando estes resultados, ve-se claramente que o critério 4 é aquele que consegue fazer o escalonamento melhor possível, ao ponto de conseguir alocar todos os produtos ao caminho optímo no que diz respeito ao parâmetro “custos”. No entanto, este mesmo crítério mostra-se bastante ineficaz no que diz respeito à optimização do tempo, e isso pode-se ver muito bem pela 2ª tabela, visto ser um dos critérios que apresenta um maior desvio em termos de “tempos”. Em relação a este parâmetro, o critério 7, apesar de conseguir optimizar apenas o tempo relativamente a 3 produtos, apresenta um desvio bastante mais a baixo dos outros critérios em termos temporais. Mesmo se se olhar para o desvio do custo óptimo, o valor registado não é assim muito elevado para este critério. Se se procurar analisar isto com um pouco de equilíbrio entre os dois parâmetros que estão em jogo, chega-se à conclusão que este último critério é o mais “consensual”. É obvio que isto depende sempre do “peso” ou importância que se pode dar mais, a um ou outro parâmetro.

Implementação

A implementação do trabalho foi talvez a etapa mais emocionante e criativa da nossa parte, uma vez que fomos confrontados com imensos desafios, partindo da ferramenta a usar até ao “timming” necessário para a sua própria execução. Este último aspecto viria a revelar-se crucial e decisivo no rumo seguido por todo o grupo de trabalho. Uma vez que o objectivo inicial proposto seria a implementação da heurística usando a ferramenta de modelização Matlab, resolvemos dar início à pesquisa na rede e nos tools do mesmo programa, à procura de pistas que melhor implementassem o modelo em causa.

Chegamos depois à conclusão que essa implementação conjugado com o factor ‘tempo disponível’, revelar-se-ia bastante mais complexa e não seria certamente a decisão mais acertada e conveniente para alcançarmos de forma realística os nossos intentos. Daí demos início à submissão de uma outra solução mais adequada à realidade. Após algumas propostas analisadas, chegamos a um consenso quanto à conveniência e eficácia da implementação da heurística, através de uma ferramenta de fácil acesso e também ela bastante eficaz: o Microsoft Excel. Esta ferramenta veio ao encontro das nossas expectativas, uma vez que nos permitiu um manejo muito abrangente às situações impostas e acima de tudo permitiu um enorme ganho de tempo na execução da nossa solução.

Etapas da Implementação

As várias etapas realizadas na nossa implementação tiveram como esqueleto uma prévia estruturação dos objectivos. Resumidamente, podemos dizer que o que pretendíamos foi criar uma articulação bastante interactiva que nos permitisse com poucos dados de entrada, tais como custos e tempo dos arcos, prioridade de entrada dos produtos, pesos de decisão relativos ao tempo e custo , e por fim tempo de colocação e quantidade de cada produto, a obtenção de um elevado grau de pormenor no que diz respeito ao cálculo de um caminho mínimo para os diferentes produtos.

O nosso programa permite simultaneamente, avaliação do caminho mínimo e o cálculo de tempos de ocupação nas diferentes máquinas pelos produtos, sendo os tempos divididos entre tempo de início e tempo final. Obtemos igualmente os custos dos caminho percorrido e o custo do caminho óptimo. Permite também a escolha dinâmica de qual o caminho a seguir por um segundo produto de acordo com a ocupação feita pelo produto anterior.

Numa primeira fase desenvolvemos uma arquitectura independente para cada produto que nos permitisse calcular, recorrendo à heurística Dijskra, o caminho mínimo, tendo como dados de entrada os tempos e custos das máquinas.

Após este ponto de partida fixamos a nossa atenção nos pormenores do que nos era exigido, tais como taxa de ocupação em que cada máquina só pode ser utilizada para um produto de cada vez ; ao analisar os escalonamentos de todos os produtos envolvidos, concluiu-se que apesar de cada produto estar associado a uma rede distinta, as máquinas que compõem cada rede são as mesmas, e como tal ocorreria situações em que uma dada máquina estaria ocupada por mais que um produto num mesmo instante. Este problema foi solucionado através da criação de uma variável em função do tempo, composta por uma “componente” fixa dada pelo dados iniciais da rede, e por uma “componente” variável função de um tempo de atraso, associada ao atraso a que um produto pode estar sujeito quando a máquina pretendida está ocupada.

O que a implementação faz é calcular o caminho mínimo para um produto em função do seu tempo fixo, ou seja do tempo em que demora a realizar a operação e do tempo de espera para a entrada na máquina respectiva, valor esse dado pela ocupação da máquina aquando da atribuição dos recursos à máquina anterior. Esse novo valor do tempo varia dinamicamente em função do atraso possível.

Esta fase caracterizou-se por uma discussão sobre a forma de limitar a taxa de ocupação a um produto. Inicialmente a ideia era partir do cálculo prévio do caminho óptimo, comparar a ocupação das máquinas devido aos produtos anteriores com a ocupação do produto em causa e somar o atraso ao tempo fixo. Este método permitiria que o sistema funcionasse independentemente da ordem pela qual os produtos entram na rede, ou seja seria irrelevante a prioridade atribuída aos produtos. Esta tentativa mostrou-se infrutífera já que o excel, sendo uma ferramenta mais limitadas que outras ferramentas do mesmo género, não permitiu a sua implementação devido a problemas de referências circulares.

Tivemos por isso de circundar o problema e calcular o tempo de espera de uma forma mais simples. Nesta nova versão, a prioridade dos produtos é uma exigência, não a podemos alterar. O que fazemos é antes de calcular os tempos para uma etapa, comparar a data de fim da etapa anterior (data de ínicio da seguinte) e a melhor data de fim da própria etapa (data de fim da etapa anterior somada ao tempo fixo de execução da etapa) com o intervalo de tempo de ocupação da máquina. Caso algumas das datas se encontrasse dentro do intervalo, somar-se-ia no tempo dinâmico a diferença entre a data de fim da ocupação da máquina (produtos anteriores) com a data de inicio da própria etapa. Dessa forma, a atribuição de tempo de uma máquina a um determinado produto fica condicionado com a ocupação prévia da máquina e o sistema fica com a possibilidade de alterar o percurso escolhido para um melhor, ou manter o mesmo percurso esperando que as operações já escalonadas terminem.

Resultados

Em função dos parametros introduzidos obteve-se diferentes escalonamentos, cujo o objectivo era evitar sobreposição dos dois produtos na mesma máquina, tentando ao mesmo tempo optimizar o caminho mínimo em função dos tempos e dos custos. As duas situações apresentadas diferem nos seguintes pressupostos. A primeira, o produto 2 espera em duas operações(Op1 e Op3) que o produto1 termine a operação, ocupando-a em seguida. Já na segunda situação o produto 2 irá optar por um caminho alternativo que é mais vantajoso do que esperar, uma vez ser essa a melhor decisão, como se pode observar logo na primeira operação.

[pic]

situação – 1

[pic]

situação - 2

Conclusão

Da realização deste trabalho é possível concluir que este método de escalonamento é uma boa solução quando o objectivo é minimizar os custos de todos os produtos depois de atribuída uma prioridade para cada produto. De facto, com este método, é tomado em consideração os tempos de espera nas máquinas para o cálculo dos melhores percursos para cada produto sendo que a solução encontrada se aproximará sempre daquela mais vantajosa para o problema em causa.

A utilização do MS Excel não se mostrou a escolha mais acertada, uma vez que este software não permite a utilização de referências circulares. A utilização desta ferramenta para este tipo de problemas também não se mostra adequada uma vez que não permite a escalabilidade dos processos, sendo que uma alteração como o acrescentar de uma máquina leva a esforços exagerados para a adaptação do problema.

Anexos

Anexo 1 – Resultados da pesquisa inicial

“Market Protocol for Decentralized Task Allocation”

William E. Walsh Michael P. Wellman

Será que no mundo em que vivemos, uma determinada entidade consegue sobreviver agindo de forma isolada, preocupando-se apenas em solucionar os seus problemas internos, sem se interessar com o que se passa com toda uma envolvente que a rodeia, e que mesmo que não queira será sempre um factor, do qual poderá depender a sua própria sobrevivência?

A sociedade de hoje caminha rapidamente para a globalização. As parcerias entre empresas são cada vez mais, e mesmo aquelas que tentam agir de maneira isolada, estão sempre dependentes do sucesso de outras entidades (mesmo indirectamente), não só para aquisição de inputs mas também para que haja quem necessite do seu produto final em causa.

A criação de um protocolo de mercado, visa o estabelecimento de um conjunto de “regras” de conduta, dos diversos agentes que estão inseridos cada vez mais numa imensa rede, tentando criar uma certa disciplina na forma como são negociados bens (matérias-primas ou produtos acabados), para que todos consigam “sobreviver” nos diversos mercados em que operam.

Numa perspectiva global todos agentes envolvidos (fornecedores ou consumidores) se inserem no mesmo contexto e partilham do mesmo problema: alocação de tarefas a determinados agentes de uma rede numa situação particular - a escassez de recursos. O objectivo é estabelecer um protocolo regulador da alocação de recursos, que permita reconhecer a chegada a um ponto de estabilidade, satisfazendo todas as tarefas necessárias para completar a cadeia através da negociação de preços satisfatórios para todas as partes.

A rede de agentes é descrita através de um grafo, conjunto de vértices e relações, em que os nós/vértices são constituídos por Bens e Agentes (Produtores, Fornecedores e Consumidores). Apesar de uma mesma tarefa poder ser realizada por mais de um agente, nesta situação de escassez e para manter a fiabilidade do sistema deverão ser retiradas as hipóteses de ciclo no fornecimento (um produtor fornecer a si próprio um bem de entrada).

A solução obtida é um sub-conjunto de um grafo que representa todas as hipóteses de configuração, esta é atingida quando um consumidor adquire um bem que deseje e todos os produtores são viáveis. Um agente pertence à solução se adquire/fornece um bem. Todos os bens da solução são adquiridos e/ou vendidos e existe uma correspondência de um para um entre relações de aquisição e de previsão.

A negociação de alocação é efectuada através de um sistema de leilão, baseada nos preços dos bens. Cada agente possui o seu “preço mínimo” ou preço de reserva e em função deste licita um determinado produto/bem de modo a maximizar a diferença entre a compra e a venda. A ninguém interessa vender o seu produto a cima/baixo do seu preço de reserva, pois iria acarretar prejuízos.

A negociação é realizada através de mensagens que são enviadas por cada agente com a sua proposta. Para cada agente só é considerada a última proposta. Sempre que uma oferta supera todas as outras é enviada uma mensagem a todos os agentes interessados com a informação do preço actual e a identificação de quem a propôs. A solução é encontrada quando, após um dado intervalo de tempo, cessam as chegadas de mensagens, e o preço em causa não ultrapassa o preço de reserva dos agentes. É enviada uma mensagem de notificação a cada agente com o preço final e as unidades transaccionadas.

“An implementation of the contract net protocol based on marginal cost

calculations”

T. W. Sandholm

abstract

Este paper formaliza o processo de decisão de bidding e awarding baseada no cálculo dos custos marginais baseados no critério do agente local. Com este protocolo os agentes (competidores e cooperadores), tendo critério muito distintos baseados no seu próprio interesse, podem interagir distribuindo tarefas de modo a que a rede funcione efectivamente e como um todo.

Introdução

CNP – contract net protocol

TRACONET – transportation cooperation net para atribuição de tarefas

O CNP é um protocolo usado inicialmente para o processo de negociação envolvendo uma selecção de atribuição de tarefas por parte quer de gestores e contratantes. Este paper formaliza um modelo(TRACONET), onde os agentes calculam localmente os custos marginais associados à execução de um determinado número de tarefas, através de decisões de anúncio, oferta e atribuição. A escolha dos contratantes baseia-se sempre no preço. Neste protocolo é também abordada a atitude perante o risco, ou seja, quando o agente não tem certeza de cumprir o estabelecido ou que a tarefa não seja rentável.

A arquitectura TRACONET

A negociação assíncrona automática de TRACONET permite que uma parte envolvida no processo possa realizar uma oferta (bid) para cada anúncio (announcement) que recebe, não tendo acesso às ofertas de outros agentes interessados, ou seja o agente parte do princípio que mais ninguém recebe o seu anúncio. Os agentes não possuem hierarquia fixa. Um agente pode ser gestor ou contratante, mas não precisa de ter os dois papeis, nem de negociar com todos os agentes.

Aquando da atribuição são enviadas mensagens de perda, que liberta o agente da sua oferta, que afecta o preço de outras ofertas e a avaliação de outras ofertas. Um tempo limite poderia também ser considerado para determinar quando um agente perde o ‘negócio’, o que implicaria a perda do assincronismo já que um agente teria apenas um determinado tempo de resposta.

Cada agente tem duas partes essenciais:

- sistema de regateamento (bargaining)

- optimizador local

O sistema de regateamento está dividido em 4 partes:

- anuncio (announcer)

- oferta (bidder)

- atribuição (awarder)

- reconhecimento da atribuição (award taker)

O algoritmo de optimização local não é específico para um determinado sistema de regateamento. Tem no entanto de

- contabilizar os custos marginais de um conjunto de entregas (a remover ou adicionar)

- optimizar todas as entregas de um agente

- remover ou adicionar conjuntos de entregas à solução de encaminhamento

Controlo local - Local Control

Utilizando o optimizador local, é atingida a solução inicial que indica a sequência de interacção com os agentes. Dessa forma são iniciadas as negociações. Durante as negociações o ciclo de controlo local percorre os agentes pela sequência determinada invocando os bidders, awarders,award takers e announcers. Os agentes (retirando os announcers) manuseiam as mensagens recebidas na altura da sua chamada. Durante todo o ciclo, o anunciador apenas lança um anúncio, já que é preferível lidar com todas as mensagens antes de lançar um novo anúncio. As mensagens recebidas num ciclo são tratadas no ciclo seguinte, prevenindo possíveis erros provocados por excessos de mensagens.

A entrada e saída de agentes na rede é feita dinamicamente. Aquando da entrada devem ser apagadas todas as mensagens acumuladas, estando depois preparado para iniciar as negociações. A saída das negociações é mais complicada:

- pode estar a ser-lhe atribuído um bem, que saindo, não será notificado

- podem estar a ser-lhe feitas ofertas. Se sair da negociação, o agente que faz a oferta não receberá qualquer tipo de mensagem, estando por isso comprometido a essa mensagem desnecessariamente

o segundo ponto é solucionado enviando mensagens de perda para todos os agentes que enviaram mensagens previamente. O primeiro através de um processo de escuta antes da saída da rede. Durante esta fase não há interacção com a rede acabando aquando da recepção de mensagens para todas as ofertas ainda pendentes.

Announcing

Os métodos de anúncios diferem de acordo com o número de tarefas que englobam. Renunciar o anúncio colocado, leva a melhores resultados, mas a negociações mais longas. É descrito um algoritmo de annoucing.

Bidding

Um agente de oferta, lê o anúncio enviado por outros agentes. Se o preço máximo mencionado no anúncio for maior que os custos do agente em causa, é lançada uma oferta com o preço do agente. Caso contrário não é feita qualquer oferta.

Quantos mais anúncios são lançados, mais ofertas são lançadas. Pode haver casos em que a cadência com que são lançados os anúncios é mais elevada do que a velocidade que o agente de oferta pode processar. Isso causa um ‘congestionamento’ na rede. Este problema pode ser resolvido fazendo com que o agente de oferta receba mensagens mais recentes que um dado momento no tempo.

É descrito o algoritmo de bidding.

Awarding

Um agente de atribuição lê as ofertas de outros agentes. Antes de processar as mensagens verifica se passou um determinado tempo desde o envio do anúncio de forma a que os potenciais contratantes tenham tempo de fazer a sua oferta. É enviada a mensagem de atribuição ou perda a todos os agentes que recentemente enviaram uma mensagem de oferta. É atribuída a tarefa ao agente que possuir a oferta mais barata.

Se passado um determinado tempo não houver ofertas para um determinado anúncio, a atribuição é adiada até à recepção da primeira oferta. Após o segundo tempo limite ter passado é enviada uma mensagem de perda a todos os agentes que receberam a mensagem de anúncio. As mensagens de oferta recebidas posteriormente são apagadas.

Todas as mensagens recebidas após o fase de atribuição são processadas por ordem de recepção antes da passagem para qualquer outra fase.

É descrito o algoritmo de awarding.

Taking Award

O agente a quem foi enviada a mensagem de atribuição lê-a e insere a sua tarefa no seu processo. Mesmo se a tarefa se mostre desvantajosa, o agente é obrigado a cumprir a tarefa.

“An Agent-Based Approach to Task Allocation in a Computer Support

Team”

Siani Pearson; Chris W. Preist; TorbjØrn S. Dahl; Erik de Kroon

O objectivo deste trabalho é apresentar um sistema baseado em agentes para a alocação de tarefas para membros de uma equipa de engenheiros de manutenção de computadores.

Este processo pode ser feito de forma a que os clientes contactem a equipa com os pedidos das tarefas que desejem. A equipa vai de seguida negociar com os clientes as tarefas e os prazos. O acordo deve satisfazer os clientes o mais possível, no entanto deve-se dar alguma liberdade de decisão aos membros das equipas.

O interesse deste trabalho é explorar a variedade das diferentes arquitecturas de organização de coordenação e comunicação entre agentes.

O contacto entre o cliente e o CST(computer suport team), é realizado através da ligação telefónica na qual o pedido define a tarefa, o período em que desejam que seja terminada, os detalhes de contacto e a periodicidade. Por sua vez a equipa de atendimento, define a prioridade da tarefa e atribui a um membro CST. A alocação vai depender de factores tais como: abilidade para a tarefa, responsabilidade, disponibilidade, carga horária e por fim, o custo.

As fases da provisão de serviços são obtidos usando um modelo de comunicação. O membro CST só realizará a tarefa, de acordo com o contacto que o cliente terá aceite. Este contracto especificará quem é que realizará a tarefa.

A arquitectura desenvolvida é um misto entre a arquitectura ADEPT e a arquitectura facilitadora. Aqui iremos ter um agente facilitador e um serviço independente de fornecimento de agentes.

Os agentes são independentes. No entanto espera-se que cooperem com o facilitador, apesar de só fazerem caso seja do seu prório interesse.

Para uma arquitectura de agentes internos, optou-se por um BDI( Beliefs-Desires- Intentions), que consiste num gestor de mensagens, uma base-de-dados credível ,gestor e um orientador para os objectivos. Optou-se por escolher uma base de dados que armazene todas as mensagens que um agente receba ou envie. O gestor de mensagens vai poder processar as mensagens alterando os objectivos e a base de dados. O gestor pode por sua vez , usar os planos da libraria de forma a satisfazer os clientes. O modelo de mensagens de comunicação usa a aproximação KQML para a gestão de mensagens que foca o problema de provisão de informação e a sua troca.

“KQML: KNOWLEDGE QUERY AND MANIPULATION LANGUAGE”

Tim Finin Richard Fritzson Don McKay Robin McEntire

Protocolo de comunicação entre agentes inseridos numa mesma envolvente de mercado, em formato de mensagem, que visa suportar uma arquitectura básica para partilha de conhecimento em tempo real e troca de informação, numa perspectiva de facilitar a comunicação entre agentes.

Todo o trabalho feito até agora teve o propósito de desenvolver modelos de alto-nível, técnicas e metodologias para construção de bases de conhecimento em larga escala compartilhadas.

São chamados Agentes Inteligentes, aqueles que são capazes de comunicar entre si usando uma linguagem expressiva, trabalhando cooperativamente na resolução de problemas comuns; O KQML foi desenvolvido para suportar interacção entre diferentes software, de agentes inteligentes, tendo vindo a ser implementado em diversos sistemas de informação que usam diferentes arquitecturas de software.

Linguísticamente falando, o objectivo é a partilha de sintaxes, semanticas e pragmáticas comuns; KIF, SQL e LOOM são algumas linguagens que tentam fazer isso, mas que ainda estão longe de ser standartizadas. Pretende-se que o processo computacional inclua as seguintes pragmáticas:

- Saber com quem comunicar e como encontrar essa entidade

- Saber como iniciar e manter a troca de informação

O KQML preocupa-se primeiramente com este tipo de questões e depois com as semânticas do processo computacional. A sincronia é a principal caracteristíca que se pretende neste tipo de comunicação.

Um elemento muito importante nesta rede, é o chamado agente facilitador ou mediador, que tem como objectivo a realização de diversos serviços que facilitem a comunicação entre agentes bem como ajudá-los a encontrar os clientes e servidores apropriados.

Aplicações KQML usam uma de duas técnicas simples:

- PACT project – todos os agentes usam um facilitador comum

- ARPI aplications – procura e estabelecimento de contacto com um

facilitador local; quando o agente entra na rede, o seu router fá-lo anunciar ao facilitador local, sendo então registado na sua base dados local; quando aplicação termina, o router envia uma mensagem para o facilitador removendo aplicação da base dados.

Tal como no domínio da internet, as técnicas utilizadas são o mapeamento dos agentes em referências especificas, que são usadas para contactar esses mesmos agentes. As aplicações KQML correntes usam protocolos de comunicação e mensagens standart como uma “camada transporte”, incluindo TCP/IP, HTTP, CORBA,...

LINGUAGEM PROPRIAMENTE DITA

Ser capaz de localizar e “chamar atenção” de alguém com quem se quer comunicar é uma parte do processo; envolver a mensagem de uma forma que

torne claro o propósito da comunicação é outra parte. O conteudo da mensagem é apenas uma parte da comunicação, que pode ser expresso em qualquer tipo de linguagem e escrita em ASCII ou na sua notação binária.

O KQML ignora o conteudo, apenas considera o início e o fim da mensagem. A sua sintaxe é baseada numa lista de parentesis balanceada, possuindo informação dos endereços e nomes dos agentes que envia e recebe. Tendo em conta a sua simplicidade, este tipo de linguagem tende a ser

modificada no futuro.

Para mais informação, nomeadamente:

- exemplos de situações que demonstram as funções dos facilitadores;

- exemplos de mensagens em formato KQML;

Consultar artigo intitulado “KQML as an Agent Communication Language”

“Building a Virtual marketplace for software development task”

Boris Kötting Frank Maurer

Este trabalho apresenta uma ferramenta de suporte para um software de

desenvolvimento de subcontractação de tarefas para a internet, em que será discutido um protocolo contract-net. Utiliza um software de suporte MILOS, que simula um mercado virtual.

O objectivo do MILOS é de fornecer uma maior flexibilidade nos processos de suporte via software. A modelação, planeamento e execução podem ser distribuidos a diferentes companhias, acedendo simplesmentes pela internet.

Quando um projecto é iniciado, é necessário ter em conta vários riscos, por isso é preciso estimar os possíveis ambientes. Para um apoio o gestor do sistema pode invocar um offering-agent GUI que pode introduzir informação. Os agentes licitadores de outras partes têm acesso ao mercado virtual e usarão o bidding-agent GUI para os apoiar no planeamento das suas responsabilidades. Desta forma o gestor que usará o offering-agent decide qual o bidding-agent que receberá a tarefa. Depois de garantido a tarefa ao bidding-agent e a tarefa será marcada como recurso de saída, e quando houver um vencedor este terá toda a informação e respectivos documentos sobre a tarefa.

O protocolo de negociação irá basear-se no net protocol.

Com o uso do mercado virtual, não haverá contacto entre agentes, será usado uma semântica baseada numa estrututa de objectos (JavaSpace protocol). A estrutura de objectos terá como componentes a especificação JavaSpace, especificação Negociação e a especificaçaõ Tarefa.

O tipo de ofertas podem ser de dois tipos: yes/no ou oferta parcial. O tipo yes/no só permite aos agentes aceitarem ou rejeitarem a proposta. Enquanto na oferta parcial (só poderá acontecer quanto as tarefas poderem ser decompostas em subtarefas), O bidding-agent recebe uma oferta, mas só poderá manipular as tarefas que podem ser efectuadas. Então ele põe um “partial bid” no mercado virtual de forma a nomear a subtarefa que quer realizar e o preço que quer receber.

“Interative Combinatorial Auctions: Theory and Practice”

David C. Parkes Lyles H. Ungar

Os leilões são mecanismos muito úteis na alocação de recurso. As aplicações incluem problemas de atribuição de tarefas e “scheduling”. No comércio electrónico este sistema é muito usado, sobretudo nos sites de venda de produtos através de leilões. Contudo estes sistemas são uma simples variação dos tradicionais leilões ingleses – licitações de um único produto.

O iBundle é um leilão interactivo que permite que os agentes licitem um conjunto de artigos enquanto o leiloeiro aumenta o preço e mantém uma alocação provisória. Este tipo de leilões faz sentido em muitos problemas da vida real. Por exemplo, um fabricante que precisa do produto A e B, não lhe interessa ter o produto A se não tiver o produto B. Apesar deste tipo de leilões poder ser aproximado por múltiplos leilões de um único item, estes últimos resultam, geralmente, em saídas “ineficientes”.

No iBundle, como num leilão interactivo, os agentes tem acesso aos valores dos diferentes conjuntos à medida que o preço é alterado e podem fazer novas ofertas de modo a “responder” a outros agentes. O iBundle é um leilão de preço ascendente que permite que os agentes licitem combinações arbitrarias de itens durante o leilão. O leiloeiro aumenta o preço dos conjuntos à medida que as licitações chegam e mantém um conjunto de licitações de modo a maximizar a receita. Os agentes podem indicar licitações exclusivas de conjuntos, isto é, por exemplo, um agente pode indicar que quer todos os itens de S1 ou todos os itens de S2. Todos as ofertas têm de ser incrementadas de um mínimo ( .

Para determinar o “vencedor” o leiloeiro tem de encontrar uma solução de modo a respeitar as restrições dos vários agentes e de modo a maximizar o lucro.

12

“On Bid Selection Heuristics for Real-Time Auctioning for Wide-Area

Network Resource Management”

Tem vindo a crescer a importância de maximizar a utilização de recursos, a fim de quem necessita deles, possa recuperar o seu investimento. Pretende-se o desenvolvimento de um sistema de “leilão”, que possa ser usado no comércio de recursos computacionais numa rede alargada. Um sistema desse tipo em tempo-real tem sido desenvolvido, como uma parte de um estudo chamado Computation Market (CM). Arquitectura do CM divide a rede alargada em regiões chamadas mercados locais (LM); um LM tem um servidor de leilão que gere as transações de recursos para as redes “vizinhas”; o núcleo de um sistema CM é o protocolo de oferta; o servidor recebe as ofertas para os recursos disponíveis e usa determinadas estratégias de maximização do lucro para seleccionar o conjunto de ofertas que deverão receber os recursos.

Algumas características de um CM:

- sistema baseado na internet

- uso do leilão tipo inglês

- baseado num mecanismo em que cada mercado local tem o seu próprio servidor

- Esquema que ofertas com várias combinações de recursos

- Não existe uma estrutura hierarquizada que limite a escalabilidade

- Uso de heurísticas para resolver os problemas de determinação das ofertas “vencedoras”

Arquitectura de um sistema CM é basicamente uma interconexão entre diversos mercados locais. Por sua vez um mercado local é composto por: um servidor de leilão (AS), um corrector local (LB), agentes fornecedores (SA) e agentes consumidores (CA).

Os CA’s devem especificar os atributos dos recursos que desejam. Para facilitar o processo de oferta, agrupa-se os recursos em classes baseadas nos seus atributos.

O AS oferece 3 tipos de funções:

- um mercado virtual para clientes locais

- comércio de serviços num mercado global

- selecção das ofertas vencedoras

O seu objectivo é maximizar o lucro dos serviços que oferece.

O LB examina as ofertas.

O SA fixa o preço de reserva (o mais baixo aceitável) para um recurso e ainda o mais baixo incremento aceitável, entre duas ofertas consecutivas. O CA responsabiliza-se pelas ofertas tendo em conta as características dos recursos, tendo que ser essa oferta mais elevada que a oferta maior, feita até então; O AS só aceita ofertas que sejam mais altas que o preço de reserva. O leilão acaba ao fim de um tempo pré-defenido e de uma forma períodica sendo as ofertas vencedoras determinadas pelo AS; são aceites ofertas multíplas para um recurso ou conjunto de recursos pertencentes à mesma classe. Cada CA pode ter conhecimento da oferta mais alta a fim de poder refazer a sua oferta. Para determinar o conjunto de ofertas “vencedoras” são usadas heurísticas de selecção, heurísticas essas compostas por um algoritmo baseado em arvore de ofertas , basicamente uma arvore binária com profundidade igual ao numero de classes de recursos existentes.

Para mais informação acerca do algoritmo, acompanhado de exemplo ,ver artigo “A Heuristic Approach to Task Allocation in Real-Time Distributed

Systems”.

Alguns problemas surgem, quando simuladas estas heurísticas, nomeadamente em situações de vários leilões combinatórios , quando se tenta resolvê-los em casos de multíplas unidades.

Uma questão importante é a variante Tempo-Real, que leva à necessidade de se determinar soluções o mais rapidamente possível.

“Bid Determination in Simultaneous Auctions”

Amy GreenWald Justin Boyan

O RoxyBot é um sistema que simula agentes de viagens. Este representa um conjunto de clientes que trocam bens complementares (por ex., bilhetes de avião e reservas em hotéis) e bens substituíveis (“substitutable”) (por ex., bilhetes de teatro e ópera). Este sistema deve ser capaz de comprar bens de modo a satisfazer as preferências dos seus clientes, mas da maneira mais económica possível.

O 1º objectivo é determinar o modo como vai licitar, devido ao facto de

os bens complementares e substituíveis serem vendidos em leilões simultâneos e não combinatoriais. A procura está dividida em 2 etapas. A primeira etapa tem como função atribuir pacotes de viagens – combinações de viagens e quartos de hotel e a segunda etapa deverá adjudicar pacotes de entretenimento – combinações de bilhetes de entretenimento. Estas duas etapas estão relacionadas: quando um pacote de viagens está atribuído, os pacotes de entretenimento restringem-se, em função do destino escolhido.

“The Auction Manager: Market Middleware for Large-Scale Electronic

Commerce”

T. Mullen M. P. Wellman

Como a diversidade dos participantes do comércio electrónico tem vindo a crescer, a complexidade de compra de uma vasta e dinâmica gama de bens e serviços precisam de ser escondidos do último utilizador. Quanto mais complexo for criado um sistema, mais garantias darão quanto à flexibilidade e a satisfação nos diferentes cenários de comércio existentes entre comunidades comerciais. Apresenta-se aqui um dos componentes, AM (Auction Manager-gestor de leilões) deste tipo de comércio, “Middleware”.Este tipo de gestor de comércio, foi criado para simplificar, automatizar a criação dos novos mercados. A AM determina quais os mercados apropriados para um dado comprador ou vendedor, usando as regras de “inferência específica” do mercado aplicado às ofertas do mesmo. Este sistema de gestão lida com diferentes perspectivas e visões dos problemas, dado que tem que suportar a

diversidade do mercado comercial. Entende-se diversidade às diferenças existentes nos mesmos, tais como por exemplo: diferenças de vocabulário, instituções e convenções. Isto sugere que os serviços Middleware – AM devam ser extremamente flexíveis. Por este facto este sistema confronta cada agente que deseje participar na sua interacção, um conjunto de questões a entrada, tais como:

- Como poderei descrever o que eu pretendo trocar?

- Onde posso trocar a mercadoria e em que termos?

- Com o que é que posso trocar?

- Como poderemos executar a transacção?

A arquitectura genérica deste tipo de comercio – Middleware

Uma parte da infra-estrutura deste comércio é a estrutura da interacção: descrição da linguagem para as mercadorias, negociação e protocolo de trocas.

Na primeira interacção a linguagem de descrição, ou ontologia permite uma largada captura de potenciais mercadorias. Por exemplo quando usamos um serviço de livrarias comum, estamos a aceder a um serviço que responde a queries, ou seja existirá um enquadramento numa determinada árvore comum, mediante a determinação prévia de um formato específico que se pretende. Torna-se assim mais fácil determinar e enquadrar a mercadoria num perfil desejado.

Numa segunda interacção que é a negociação, dado um elevado número de potenciais mercadorias e condições do comércio local, há necessidade de um mecanismo variável de negociação.

Os leilões promovem negociações automáticas segundo as seguintes características:

- Mediado – cada comprador não contacta separadamente nenhum vendedor

- Preço, não troca – preço minimiza e suprime a comunicação

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download