- Modelagem Matemática e Computacional / CEFET-MG

Transcrição

CENTRO FEDERAL DE EDUCAÇÃO
TECNOLÓGICA DE MINAS GERAIS
Diretoria de Pesquisa e Pós-Graduação
Programa de Pós-Graduação em Modelagem
Matemática e Computacional
Otimização de Layouts Industriais
Utilizando Heurística SDPI no
treinamento de Redes Neurais
MLP
Dissertação de Mestrado, submetida ao Programa de
Pós-Graduação em Modelagem Matemática e Computacional, como parte dos requisitos exigidos para
a obtenção do título de Mestre em Modelagem
Matemática e Computacional.
Aluno: Ricardo Soares
(Engenheiro Mecânico – UFMG)
Orientadora: Profa. Dra. Maria das Graças de Almeida (CEFET-MG)
Co-Orientador: Prof. Dr. Sérgio Ricardo de Souza (CEFET-MG)
Belo Horizonte, 31 de agosto de 2006.
Agradecimentos
Primeiramente, a Deus.
Aos meus pais, Walter e Odina.
À minha esposa Cláudia e aos meus filhos Guilherme e Eduardo pela compreensão
das ausências em alguns momentos.
Aos colegas e amigos, Alessandra, Marcelo, e Marcos pelo compartilhamento nas horas
difíceis.
À minha orientadora Profa.Dra. Maria das Graças de Almeida .
Ao meu co-orientador e amigo Prof.Dr. Sérgio Ricardo de Souza.
Este trabalho teve o apoio da CAPES.
ii
Dedicatória
Para
Cláudia, Guilherme, Eduardo e
principalmente aos meus pais.
iii
Sem sonhos, a vida não tem brilho. Sem metas, os sonhos não têm alicerces. Sem
prioridades, os sonhos não se tornam reais. Sonhe, trace metas, estabeleça prioridades
e corra riscos para executar seus sonhos. Melhor é errar por tentar do que errar por
omitir!. Não tenha medo dos tropeços da jornada. Não se esqueça de que você, ainda
que incompleto, foi o maior aventureiro da história.
Augusto Cury
iv
Resumo
O arranjo físico de equipamentos em uma instalação industrial tem sido objeto
de estudos por vários pesquisadores na busca do arranjo ótimo. Sendo assim, diversas metodologias têm sido desenvolvidas ao longo do tempo. Em 1957, Koopmans
e Beckmann utilizaram o problema quadrático de alocação como modelo matemático
nas soluções de problemas na área econômica. Em 1963, Armour e Buffa modelaram
atividades relacionadas com otimização de layouts, tendo, como base, o Problema
Quadrático de Alocação. Diversos tipos de formulações têm sido apresentadas para
este problema com base nas permutações das matrizes de entrada; fundamentadas na
programação inteira e booleana; na teoria dos grafos; programação semidefinida, dentre
outras. Este trabalho aborda uma solução computacional para o problema de arranjo
físico industrial com base em redes neurais multilayer perceptron para uma situação
realista de vinte e dois departamentos. A heurística Steepest Descent Pairwise Interchange servirá de suporte à rede neural, fornecendo os dados necessários para o seu
treinamento, validação e teste. De acordo com o número de departamentos, comparações são realizadas com métodos exatos enumerativos e com o algoritmo Branch and
Bound. Como resultado, o arranjo físico final para o caso em estudo foi satisfatório,
permitindo redução considerável no custo total.
Palavras-Chave: Problema quadrático de alocação, Algoritmo Branch and Bound,
Redes neurais Multilayer Perceptron.
v
Abstract
The facility layout problem have been object of studies for several researchers in
order to find optimal arrangement. A lot of Quadratic Assignment Problem (QAP)
formulation have been developed along the time, such as: Koopmans and Beckmann
(1957) used the quadratic assignment problem as mathematical model in the economical area; Armour and Buffa (1963) modeled activities related with layouts optimization
based in QAP. According to mathematical resources, some QAP formulations has been
made: based in matrix permutations ; integer and boolean linear programming; graph
theory; semidefined programming, among others. This document presents a computacional solution for the facility layout problem. Neural Network Multilayer Perceptron
will be used for a realistic situation with twenty-two departments. Heuristics Steepest
Descent Pairwise Interchange will serve as support to the neural network supplying it
for the data training, validation and test. Depending on departments numbers, comparisons will be made with enumerated exact methods as well as Branch and Bound
algorithm. As result, the final layout for the case in study was satisfactory, allowing
considerable reduction in the total cost.
Keywords: Quadratic assignment problem, Branch and Bound Algorithm, Multilayer Perceptron Neural Networks.
vi
Conteúdo
1 Introdução
6
1.1
Preliminares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
1.2
Motivação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
1.3
Caracterização do Problema . . . . . . . . . . . . . . . . . . . . . . . .
9
1.4
Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
1.5
Proposta de Desenvolvimento . . . . . . . . . . . . . . . . . . . . . . .
10
1.6
Organização do Trabalho . . . . . . . . . . . . . . . . . . . . . . . . . .
10
2 Problemas de Arranjo Físico
11
2.1
Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
2.2
Característica do Problema . . . . . . . . . . . . . . . . . . . . . . . . .
12
2.3
Formulações por Programação Booleana . . . . . . . . . . . . . . . . .
13
2.4
Formulações por Recobrimento de Conjunto . . . . . . . . . . . . . . .
14
2.5
Formulações por Programação Inteira . . . . . . . . . . . . . . . . . . .
16
2.6
Formulações por Grafos . . . . . . . . . . . . . . . . . . . . . . . . . .
17
2.7
Formulações por Permutações . . . . . . . . . . . . . . . . . . . . . . .
17
2.8
Formulações Traço . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
2.9
Conclusão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
3 Uma Revisão de Métodos Exatos e Heurísticos para a Solução do
Problema de Arranjo Físico
20
3.1
Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
3.2
Algoritmo Branch and Bound . . . . . . . . . . . . . . . . . . . . . . .
21
3.3
Steepest Descent Pairwise Interchange(SDPI) . . . . . . . . . . . . . .
28
3.4
Redes Neurais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
32
vii
viii
3.5
Redes Neurais MLP . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
Algoritmo de Levenberg-Marquardt . . . . . . . . . . . . . . . .
41
3.6
Colônia de Formigas . . . . . . . . . . . . . . . . . . . . . . . . . . . .
42
3.7
Conclusão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
43
3.5.1
4 Aplicação de Redes Neurais MLP à Solução do Problema de Arranjo
Físico
44
4.1
Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
44
4.2
Desenvolvimento do Modelo de Projeto . . . . . . . . . . . . . . . . . .
45
4.2.1
Variáveis de Interesse . . . . . . . . . . . . . . . . . . . . . . . .
46
4.2.2
Formulação Matemática Proposta . . . . . . . . . . . . . . . . .
47
4.3
Aplicação do Algoritmo Branch and Bound . . . . . . . . . . . . . . . .
49
4.4
Aplicação da Rede Neural MLP . . . . . . . . . . . . . . . . . . . . . .
52
4.4.1
Preparação dos dados . . . . . . . . . . . . . . . . . . . . . . . .
52
4.4.2
Criação da Rede Neural . . . . . . . . . . . . . . . . . . . . . .
54
4.4.3
Treinamento da Rede Neural MLP . . . . . . . . . . . . . . . .
55
4.4.4
Simulação da Rede Neural MLP . . . . . . . . . . . . . . . . . .
56
Análise dos resultados . . . . . . . . . . . . . . . . . . . . . . . . . . .
59
4.5.1
Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
59
4.5.2
Experimento . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
59
4.5.3
Resultados Obtidos e Limitações . . . . . . . . . . . . . . . . .
59
4.6
Análise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
60
4.7
Conclusão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
62
4.5
5 Conclusão Geral e Trabalhos Futuros
63
A Implementações MaTlab
65
A.1 Código para algoritmo Branch and Bound . . . . . . . . . . . . . . . .
65
A.2 Gerador de Matrizes . . . . . . . . . . . . . . . . . . . . . . . . . . . .
67
A.3 SDPI(Steepest Descent Pairwise Interchange)
. . . . . . . . . . . . . .
68
A.4 Colônia de Formigas . . . . . . . . . . . . . . . . . . . . . . . . . . . .
72
A.5 Algoritmo Exato . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
76
ix
Bibliografia
79
Lista de Tabelas
4.1
Áreas de conhecimento para projeto de arranjos físicos . . . . . . . . .
45
4.2
Relação dos Departamentos do Projeto. . . . . . . . . . . . . . . . . . .
47
4.3
Permutações possíveis . . . . . . . . . . . . . . . . . . . . . . . . . . .
50
4.4
Resultado Branch and Bound . . . . . . . . . . . . . . . . . . . . . . .
52
4.5
Matriz de Entrada: Fluxo e Distância . . . . . . . . . . . . . . . . . . .
58
4.6
Comparação dos Resultados . . . . . . . . . . . . . . . . . . . . . . . .
61
x
Lista de Figuras
2.1
Distância Euclidiana . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
3.1
Breadth Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
3.2
Depth Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
3.3
Best Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
3.4
Árvore Branch and Bound . . . . . . . . . . . . . . . . . . . . . . . . .
27
3.5
Árvore Branch and Bound (caminho mais curto) . . . . . . . . . . . . .
27
3.6
Fluxograma SDPI [36] . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
3.7
Matriz Distância . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
3.8
Matriz Fluxo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
3.9
Pares Permutados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
3.10 Célula.[51].
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
3.11 Modelo de Neurônio [51]. . . . . . . . . . . . . . . . . . . . . . . . . . .
34
3.12 Arquiteturas Redes Neurais. [1] . . . . . . . . . . . . . . . . . . . . . .
35
3.13 Modelo Aprendizado Supervisionado [1]
. . . . . . . . . . . . . . . . .
36
. . . . . . . . . . . . . . . . . . . . . . . .
36
3.15 Mínimos locais e platôs em uma superfície de erro[1] . . . . . . . . . . .
38
3.16 Fluxo processamento do Algoritmo Backpropagation.[1] . . . . . . . . .
39
4.1
Distribuição espacial das localidades
. . . . . . . . . . . . . . . . . . .
46
4.2
Arranjos para 4 departamentos . . . . . . . . . . . . . . . . . . . . . .
51
4.3
Preparação dos Dados. . . . . . . . . . . . . . . . . . . . . . . . . . . .
54
4.4
Estrutura Rede Neural . . . . . . . . . . . . . . . . . . . . . . . . . . .
55
4.5
Código para o Treinamento Rede MLP . . . . . . . . . . . . . . . . . .
56
4.6
Treinamento (Normalizado) Rede Neural . . . . . . . . . . . . . . . . .
57
3.14 Aprendizado do Perceptron
xi
xii
4.7
Código para Simulação da Rede Neural MLP
. . . . . . . . . . . . . .
57
4.8
Arranjo obtido com a Rede Neural MLP . . . . . . . . . . . . . . . . .
58
4.9
Vetor Saída Rede Neural . . . . . . . . . . . . . . . . . . . . . . . . . .
60
Lista de Siglas
ALDEP - Automated Layout Design Program.
COFAD - Computerize facilities Design.
CORELAP - Computerized Relationship Layout Planning.
CRAFT -Computerized Relative Allocation of facilities Technique.
FIFO - First-in-First-out
M.I.P - Mixed Integer Program.
M.L.P - Multilayer Perceptron.
N.P - Não Polinomial.
P.L.I - Programação Linear Inteira
P.Q.A - Problema Quadrático de Alocação.
P.Q.C - Problema Quadrático Cobertura de |Conjunto.
PLANET - plant Layout Analysis and Evoluation Technique.
Q.A.P - Quadratic Assignment Problem.
RNAs - Redes Neurais Artificiais.
S.D.P.I - Steepest Descent Pairwise Interchange.
xiii
Capítulo 1
Introdução
1.1
Preliminares
O arranjo físico de máquinas e equipamentos, em um espaço conhecido, tem sido
estudado em diferentes áreas, como o planejamento em áreas urbanas, a disposição de
teclas em máquinas, projeto de placas em circuito impresso, arranjo físico de células
de produção. A preocupação em minimizar o custo está presente em todas estas atividades. Este custo está intimamente ligado à relação de importância existente entre
os pares de instalações (por exemplo, o fluxo de materias) e a distância entre elas,
informações que são tipicamente fornecidas pelo engenheiro de produção.
Originalmente tratado por Koopmans e Heragu [28], o problema de arranjo físico
tem sido alvo das mais diferentes propostas, na tentativa de buscar metodologias eficazes para otimizar a disposição física de funcionários e máquinas dentro das instalações
industriais.
Diversos métodos de resolução deste problema encontram-se na literatura, a
saber: Armour e Buffa [4], Nugent et al [43], Vollmann e Buffa [63], Kuriak e Heragu [31] e Meller e Gau [40], dentre outros. Em todos, o principal objetivo é encontrar
a melhor posição relativa entre os departamentos.
Formulado como um Problema Quadrático de Alocação (PQA) é, em geral, de
difícil solução, já que, para problemas de grande porte, não existem algoritmos capazes
de resolvê-lo em tempo polinomial.
Pode-se entender o PQA supondo m departamentos e n locais, de modo que
6
1.1
Preliminares
7
cada departamento i deverá ser posicionado em um único local j, e cada local j deverá
receber somente um departamento i. Esta correspondência biunívoca é essencial para a
resolução do problema. Além disto, cada par de departamentos possui pesos, referentes
ao grau de importância dentro das atividades da indústria. O objetivo é obter uma
permutação entre os departamentos, de tal maneira que a soma dos produtos peso e
distância seja a menor possível.
Várias propostas têm sido utilizadas para modelar este problema. Dentre as
principais, pode-se destacar: teoria dos grafos (Foulds e Robinson [15]), o MIP (Mixed
Integer Program) (Montreuil [41]; Montreuil et al.[42]; Heragu e Kusiak [22]) e a abordagem que utiliza estrutura de árvore binária, apresentada por Tam e Li [54] e, mais
tarde, empregada por Furtado e Lorena [17] e Azadivar e Wang [5].
Dependendo do tipo de atividades desenvolvidas na indústria e da área disponível,
o arranjo físico sofre uma série de restrições:
(a) a estrutura das áreas de circulação (corredores, passagens, desníveis e outros);
(b) o sistema de movimentação de materiais;
(c) a escolha da localização dos departamentos dentro da fábrica; e
(d) a localização dos pontos de entrada/saída.
Os layouts podem ser construídos a partir de dados básicos (algoritmos construtivos), ou melhorados, quando já existem (algoritmos de melhoramento) [19].
Dentre os algoritmos utilizados para a solução do PQA, destacam-se PLANET
(Apple e Deisenroth [3]) CORELAP (Lee e Moore [33]) e ALDEP (Seehof e Evans
[48]). Baseia-se em heurística construtiva, na qual cada departamento é alocado, um
de cada vez, na área disponível, até que se obtenha a solução ótima ou próxima dela.
Também são utilizados algoritmos de melhoramentos, nos quais, partindo-se de uma
solução inicial, procura-se a solução ótima ou ideal. Nesse último caso, pode-se citar,
dentre outros, os algoritmos: CRAFT (Armour e Buffa [4]), COFAD (Tompkins e Reed
Jr. [56]).
Estima-se que entre 20% a 50% do total de ações gastas na manufatura são
provenientes da movimentação de materiais. O gasto desta movimentação depende
do posicionamento entre os departamentos. A disposição lógica dos departamentos e
1.2
Motivação
8
das máquinas, quando oferece adequado arranjo físico, é capaz de reduzir os custos de
mão-de-obra entre 10% e 30% , potencializando a produtividade e conseguindo eliminar
fatores que não agregam valor ao produto (Savsar, M. [47]).
Os métodos utilizados nos últimos 20 anos ainda esbarram nas restrições comuns
encontradas no chão de fábrica, e os ajustes manuais ainda são necessários. Isto se
deve ao grande número de variáveis inerentes a cada tipo de problema.
Em função dos equipamentos utilizados, dos produtos a serem fabricados, dos
estoques necessários para a produção, dos materiais envolvidos e de qual cliente a ser
atendido, é possível dividir os arranjos físicos em três grandes grupos (Hassan, M. M.
D.[24]):
• Layout por produto: destinado às linhas de montagem;
• Layout por processo: para produção por lotes ou encomendas; e
• Layout por posição fixa: para a produção de projetos.
1.2
Motivação
A complexidade inerente a este tipo de problema e os desafios apresentados são
os principais motivos da atenção dedicada ao Problema de Arranjo Físico ótimo por
pesquisadores de todo o mundo. Isto porque é um dos mais difíceis problemas de
otimização combinatória. Mesmo quando as matrizes de distância e fluxo são simétricas. Esta dificuldade se torna maior quão maior seja o número de elementos envolvidos.
Por exemplo, para n > 15, este tipo de problema não pode ser resolvido, em geral, em
tempo computacional aceitável. Esta limitação serve para situações de procura de
mínimos globais usando algorítmos deterministas.
Um problema combinatorial, pertencente à classe NP-difícil, não possui algoritmo
capaz de resolvê-lo em tempo polinomial (M. Gondran, M. Minoux [20]). O PQA é
um exemplo de um problema pertencente a essa classe. A quantidade das possíveis
configurações aumenta fatorialmente com o número de instalações. O universo de
possibilidades possui elementos discretos, que dificulta o uso de ferramentas que têm
como base conjuntos contínuos e compromete a busca da solução no sentido de se obter
o ótimo global. Todos estes fatores contribuem para que os pesquisadores e estudiosos
1.4
Problemas de Arranjo Físico
9
o vejam como desafio nas implementações de novos algoritmos ou combinação deles.
A indústria, por outro lado, requer arranjos físicos otimizados, para aumentar o valor
agregado de seu produto.
1.3
Caracterização do Problema
Considere o problema de se designar objetos a locais, de modo que cada objeto
seja atribuído a um único local e, reciprocamente, cada local a um objeto, considerandose conhecidas as distâncias entre os pares de locais, os fluxos de algum tipo de demanda
entre os pares de objetos e, nos casos mais gerais, os custos fixos de cada atribuição
“objeto versus local”. O Problema Quadrático de Alocação (PQA) (Quadratic Assignment Problem - QAP, na literatura internacional) consiste em encontrar uma alocação
de custo mínimo dos objetos aos locais, sendo os custos obtidos pela soma dos produtos
distância-fluxo (Eliane Maria Loiola et al [37]).
É importante notar a diferença entre o problema de alocação linear e o problema
quadrático de alocação. O primeiro leva em consideração somente o custo de se alocar
um departamento em um local específico. O segundo, além desta última consideração,
verifica o fluxo de materiais entre os pares de departamentos resultante de algum tipo
de demanda entre eles (Chu, L.K. [36]).
1.4
Objetivos
Este trabalho tem como objetivo geral o estudo da solução do problema de ar-
ranjo físico industrial. Para isso, é objetivo a implementação de uma solução computacional para o mesmo, tendo como base algoritmo exato, heurística e redes neurais.
Especificamente, será estudado o treinamento de uma rede neural MLP, com base na
heurística SDPI, em instâncias nas quais algoritmos exatos não são aplicáveis. Com
isto, pretende-se obter ferramentas adequadas para aplicação nas diferentes instâncias
do problema.
Além disso, é objeto de interesse a verificação da qualidade dos resultados fornecidos pela rede neural, já que a base de dados para o seu treinamento terá origem na
heurística SDPI, uma vez que a quantidade de dados exatos disponíveis na literatura
1.6
10
são insuficientes para o treinamento, validação e teste da rede.
1.5
Proposta de Desenvolvimento
O problema de arranjo físico industrial é modelado como um problema de progra-
mação linear inteira. A técnica de solução se baseia na adoção de algoritmos enumerativos, nos quais a relaxação do problema principal é utilizada. Nesta fase, algumas
restrições são ignoradas, com o objetivo de facilitar a solução do problema. Eliminandose as restrições de integralidade das variáveis, o problema inteiro se transforma em um
problema linear padrão, que poderia ser resolvido pelo método simplex. Mas outros
algoritmos deverão ser usados face ao grande número de combinações possíveis.
De acordo com os valores de n, ou seja, quantidade de departamentos a serem
alocados, diferentes algoritmos serão utilizados: considerando a enumeração total, não
considerando enumeração total(Branch and Bound) e rede neural MLP, treinada com
base em dados gerados pela heurística SDPI. Ferramentas que se mostram adaptadas
em relação às restrições apresentadas, oferecendo maior flexibilidade na entrada dos
dados e futuras modificações nos arranjos físicos.
1.6
Organização do Trabalho
Este trabalho está organizado da seguinte maneira: as principais formulações
e a revisão bibliográfica a respeito de otimização de arranjos físicos industriais são
apresentadas no capítulo 2. No capítulo 3, serão apresentadas as revisões de métodos
exatos e heurísticos adotados para a solução do Problema de Arranjo Físico. Para cada
um destes métodos, os princípios matemáticos e principais teoremas que os sustentam
são discutidos. A abordagem da otimização do arranjo físico proposta é detalhada no
capítulo 4, onde as considerações dos dados de entrada são evidenciadas, bem como
são apresentados análises dos resultados alcançados quando da aplicação dos métodos
apresentados. Finalmente, a conclusão e perspectivas de futuros trabalhos são tratadas
no capítulo 5.
Capítulo 2
2.1
Introdução
As expressões facilities layout (arranjo físico de instalações), facilities location (lo-
calização de instalações), facilities design (projeto de instalações) e facilities planning
(planejamento de instalações) são termos usados principalmente na área industrial, que
designam problemas de planejamento de instalações de diversos tipos.
Uma ordem de classificação desses problemas foi proposta por Tompkins e White
[57], que subdividiu o planejamento de instalações em dois grupos principais:
• localização de instalações; e
• projeto de instalações.
O primeiro grupo faz referência à posição relativa da instalação com o mercado,
recurso, ambientes, clientes, etc. O segundo leva em consideração o grau de importância
desta instalação, dentro dos objetivos traçados pela instituição. É a este último conceito
que o projeto de arranjo físico pertence, consistindo no planejamento da produção ou
das áreas de trabalho, almoxarifado, estoque, pessoal, transporte de máquinas, matéria
prima, etc.
Considere n o número de setores a permutar. Assim, a quantidade de disposições
possíveis é n!. Se, além disso, for considerado os espaços para circulação, manutenção
e para novas instalações, o grau de complexidade aumenta e as possibilidades passam
11
2.2
Característica do Problema
12
a ser dadas por
P =
n!A
An
sendo A a área do departamento e An a área total ocupada por todos os departamentos.
Trata-se, portanto, de um problema combinatorial, discreto, da classe de problemas
NP-difícil.
2.2
Característica do Problema
Os objetivos qualitativos e os quantitativos têm sido considerados para otimização
de arranjos físicos de instalações. O primeiro trata da minimização de medidas de
avaliação da posição relativa entre os departamentos; o segundo, relaciona-se com o
manuseio de materiais. Na prática, ambos são usados isoladamente (Savsar, M. [47]).
A literatura apresenta os problemas de projeto em dois grandes grupos: projeto
de arranjo físico de instalações e projeto de arranjo físico de máquinas (Hassan, M. M.
D. [24]). Este último é dividido em projetos de máquinas em linha simples, em linha
múltipla e em malha.
A principal diferença entre estes dois grandes grupos é no que tange às áreas
ocupadas. No projeto relacionado às máquinas, as dimensões são relativamente pequenas e podem ser consideradas iguais ou mesmo desprezadas, não prejudicando a
qualidade do projeto. Já com referência ao projeto de arranjo físico de instalações, as
áreas ocupadas são as variáveis mais importantes a serem consideradas no projeto.
Em todo projeto de arranjo físico, o objetivo principal é oferecer condições adequadas de mobilidade na área de trabalho, tanto para pessoas quanto para equipamentos e produtos. Três situações devem ser analisadas na decisão de se fazer um projeto
de arranjo físico:
(a) a capacidade da instalação e a produtividade sofrerem alterações;
(b) implicações em despesas adicionais para realizar as mudanças necessárias;
(c) prováveis custos extras para futuras reversões.
Contudo, o responsável pelo projeto não deverá permitir a inflexibilidade do arranjo final e deve-se criar condições para mudanças, tão necessárias para o desenvolvi-
2.4
Formulações por Programação Booleana
13
mento.
2.3
Formulações por Programação Booleana
A formulação booleana foi proposta inicialmente por Koopmans e Beckman [28],
sendo utilizada mais tarde por Steinberg [53], Lawer [32], Gavett e Plyter [18], Elshafei
[13], Bazaraa e Kirca [7], Christofides e Benavent [9], Bos [8], Mans et al. [38], Jünger
e Kaibel [25, 26, 27] e, mais recentemente, por Liang [35], Torki et al. [58], Tsuchiya
et al. [60, 61] Siu e Chang [50], Fedjki e Duffuaa [14] e Yu e Sarker [64].
A variável de decisão xij recebe valores um ou zero, dependendo se o departamento
i está ou não na posição j. O modelo matemático é dado por Koopmans, T.C and
Beckman, M.J [28]:
min
suj. a
n
X
i,j=1
n
X
n
X
fij dkp xij xkp
(2.1a)
k,p=1
xij = 1, 1 ≤ j ≤ n
(2.1b)
xij = 1, 1 ≤ i ≤ n
(2.1c)
xij ∈ {0.1} , 1 ≤ i, j ≤ n.
(2.1d)
i=1
n
X
j=1
sendo:
n = número de departamentos;
fij = fluxo de material entre os departamentos i e j;
dkp = distância entre as localizações k e p ;

 1, se o departamento i está na posição j;
xij =
 0, para os outros casos.
As matrizes F = {fij }ni,j=1 e D = {dkp }nk,p=1 possuem dimensões n × n tais
que fij e dkp pertencem ao intervalo de números inteiros positivos {1, 2, 3, . . . , n}. O
produto xij xkp das variáveis de decisão em tela compõe todas as permutações possíveis
pertencentes ao espaço de soluções S.
2.4
2.4
Formulações por Recobrimento de Conjunto
14
O modelo quadrático de recobrimento de conjunto para o problema geral de
otimização de layouts foi apresentado por Bazaraa [6]. Neste modelo, a área total
ocupada por todos os departamentos é dividida pelo número de blocos.
As variáveis foram definidas como:
q = número de blocos nos quais a área total ocupada por todos os departamentos é
dividida;
I(i) = número de locais possíveis para o departamento i;
aij = o custo fixo para alocar o departamento i na posição j;
Ji (j) = conjunto de blocos ocupados pelo departamento i alocada na posição j;
d(ji , lk ) = distância entre centróides da posição j e l, quando o departamento i é
alocada na posição j e o departamento k é alocada na posição l;

 1, se o departamento i está na posição j;
xij =
 0, para os outros casos;
pijt

 1, se o bloco t ∈ J (j) ;
i
=
 0, para os outros casos.
O problema quadrático de cobertura de conjuntos (PQC) é :
min
I(i)
n
X
X
i=1
suj. a
I(i)
X
j=1
aij xij −
I(i) n I(k)
n X
X
XX
fik d(ji , lk )xij xkl
(2.2a)
i=1 j=1 k=1 l=1
xij = 1, i = 1, 2, . . . , n
(2.2b)
j−1
I(i)
n X
X
pijt xij ≤ 1, t = 1, 2, . . . , q
(2.2c)
i=1 j=1
xij ∈ {0, 1} , i = 1, 2, . . . , n; j = 1, 2, . . . , I(i)
(2.2d)
As restrições (2.2b) garantem que cada departamento seja alocado em um único
local e as restrições (2.2c) obrigam cada local a ser ocupado por apenas um departamento. As distâncias são medidas em relação aos centróides de cada localização.
2.5
15
Bazaraa [6] mostra uma maneira de medir estas distâncias por intermédio dos
fluxos entre as instalações, fazendo:
d0ik =
fik
Si Sk
sendo Si o número de locais ocupados pelo departamento i e d0jl a distância entre os
locais j e l. Usando este artifício, tem-se:
min
q
n X
X
i=1
q
suj. a
X
aij xij +
q
q
n X
n X
X
X
fik d0jl xij xkl
i=1 j=1 k=1 l=1
j=1
Si Sk
xij = Si , i = 1, 2, . . . , n
j=1
n X
n
X
xij ≤ 1, j = 1, 2, . . . , q
(2.3a)
(2.3b)
(2.3c)
i=1 i=1
xij ∈ {0, 1} , i = 1, 2, . . . , n; j = 1, 2, . . . , q
(2.3d)
A desvantagem desta formulação surge quando a área total ocupada por todos os
departamentos é dividida em pequenos blocos (Bazaraa, [6]).
As distâncias mencionadas anteriormente são as distâncias euclidianas definidas
pela fórmula:
dkp =
q
(xp − xk )2 + (yp − yk )2
sendo x e y as coordenadas dos centróides das localizações K e P .
Y
P
y(p)
Distância
K
y(k)
x(k)
x(p)
X
Figura 2.1: Distância Euclidiana
(2.4)
2.6
2.5
Formulações por Programação Inteira
16
Formulações por Programação Inteira
Esta proposta, feita por Lawer [32], envolve coeficientes de custo que não corres-
pondem necessariamente ao produto distância e fluxo. Seja a variável
yijkl = xij xkl
(2.5)
O modelo é dado por:
min
suj. a
n
n X
n X
n X
X
i=1 j=1 k=1 l=1
n
n X
n X
n X
X
bijkl yijkl
(2.6a)
yijkl = n2
(2.6b)
i=1 j=1 k=1 l=1
yijkl ≥ 0, i, j, k, l = 1, 2, . . . , n
(2.6c)
yijkl ∈ {0, 1} , i, j, k, l = 1, 2, . . . , n
(2.6d)
Essa formulação permite a linearização do modelo apresentado em (2.1), através
de um artíficio matemático. A matriz B ∈ <n×n representa o custo formado pelo
produto das matrizes de fluxo F e de distância D. Observe que n é o número de
departamentos em questão.
Segundo Kaku e Thompson [30], a desvantagem desta formulação é o número de
restrições que possui. O PQA tem n2 variáveis xij e 2n restrições, enquanto o problema
apresentado em (2.6) possui n2 variáveis xij , n4 variáveis yijkl e n4 +2n+1 restrições. As
restrições são necessárias para o estabelecimento da correspondência biunívoca entre
os departamentos e os locais a serem associados.
O acréscimo das restrições se deve à linearização do problema, já que várias
substituições deverão ser efetuadas nas expressões por conta do artifício matemático
utilizado: yijkl = xij xkl .
2.7
Formulações por Grafos
2.6
17
Formulações por Grafos
Nos modelos que utilizam a teoria de grafos [15], os locais de cada par de depar-
tamentos adjacentes devem ser conhecidos. O modelo é apresentado a seguir:
min
XX
wij xij
(2.7)
i∈E j∈E
suj. a
xij = 1, para (i, j) ∈ N
(2.8)
xij = 0, para (i, j) ∈ F
(2.9)
sendo:
G = (V, E) um grafo, no qual V é o conjunto de vértices, não-vazio, e E é o conjunto
de ligações disjuntas de V;
V: conjunto de departamentos;
N : conjunto de pares de departamentos adjacentes;
F: conjunto de pares de departamentos que não devem ser adjacentes;
wij : razão de proximidade ao departamento j;
(V, E 0 ∪ N ): grafo planar, para E 0 = {(i, j) : xij = 1, (i, j) ∈ E}
Evans et al.(1987) [48] divide o problema de arranjo físico em duas categorias,
sendo que uma utiliza modelos quadráticos de atribuição e a outra utiliza grafos com
base nos fluxos do processo.
As restrições mencionadas acima garantem a unicidade dos departamentos aos
locais e que cada local tenha somente um departamento.
2.7
Formulações por Permutações
Sabendo-se que o custo de alocar um par de departamentos a um par de localiza-
ções é proporcional ao fluxo e à distância entre eles, chega-se ao conceito de permutação,
apresentado por Hiller e Michael [23], Pierce e Crowston [44] e Cung et al.[10], dentre
vários outros.
2.8
Formulações Traço
18
Definindo S n como o conjunto de todas as permutações entre n departamentos, fij
como o fluxo entre os departamentos i e j e dπ(i) π(j) como a distância entre as localizações
π(i) e π(j) , dada pela permutação π ∈ sn , este modelo pode ser representado, para cada
permutação π, como sendo:
n
X
min
π∈S n
suj.
fij dπ(i)π(j)
(2.10)
i,j=1

 1, se π = j;
(i)
a xij =
 0, se π 6= j.
(i)
(2.11)
Os modelos apresentados anteriormente e este são equivalentes, dado que as restrições envolvidas definem matrizes de permutação X = [xij ], que fazem parte do
espaço S n .
2.8
Formulações Traço
Com base na teoria espectral de matrizes, este tipo de modelagem leva em conta
a soma dos elementos da diagonal principal da matriz, dado pela função traço, para
que seja determinado o limite inferior da solução ótima do problema. O valor deste
limite irá definir o quão ótima será a solução alcançada.
Proposta por Edwards [12], esta formulação considera Π como sendo o conjunto
das permutações possíveis, e é dada na forma:
min Tr (F XDX t )
suj. a
X∈Π
(2.12a)
(2.12b)
Nessa expressão, F é a matriz de fluxo, representando o grau de importância entre
os departamentos, e D é a matriz de distância entre as localidades. Ambas as matrizes possuem dimensão n × n. O conjunto Π representa o conjunto formado pelas
permutações das matrizes X.
Também como base nesta formulação, Karisch [29], Zhao [65], e Wolkowisz [62],
define relaxação do PQA tendo como suporte o dual do dual Lagrangeano. Assim,
sejam dados:
2.9
Conclusão
19
• e: vetor com todos os seus coeficientes iguais a unidade;
• X: matriz de permutação;
• B: matriz de custo fixo.
pode-se escrever:
min
suj. a
Tr (F XD − 2B) X t
(2.13a)
Xe = e
(2.13b)
X te = e
(2.13c)
xij ∈ {0, 1} , ∀ i, j
(2.13d)
Nesta expressão, tem-se que F ∈ <n×n é matriz de fluxo e D ∈ <n×n é a matriz
de distâncias. Estas restrições garantem que cada departamento esteja alocado em um
único local e cada local tenha um e somente um departamento.
Outra relaxação do PQA utilizando Programação Semidefinida(PSD), com base
na formulação traço, segundo Zhao [65], pode ser escrita como:
min trF.X.D.X t − 2BX t
s.a
XX t = X t X = 1,
(2.14)
Xe = X t e = e,
Xij2 − Xij = 0
2.9
∀i, j.
Conclusão
Neste capítulo, foram apresentadas várias formulações matemáticas para repre-
sentação do problema quadrático de alocação, desde aquelas com base em programação
booleana até as fundamentadas na teoria espectral de matrizes. Todas elas têm, como
suporte, as permutações das matrizes envolvidas, mesmo aquelas em que a linearização
do problema é proposta, aumentando consideravelmente o número de restrições.
Capítulo 3
Uma Revisão de Métodos Exatos e
Heurísticos para a Solução do
Problema de Arranjo Físico
3.1
Introdução
Neste capítulo, serão revisados o algoritmo Branch and Bound (divisão e con-
quista) e conceitos de Redes Neurais que serão utilizados no desenvolvimento deste
trabalho. Especial atenção será dedicada às redes neurais multilayer perceptron(MLP).
Será também revisada a heurística Steepest Descent Pairwise Interchange (SDPI). Esta
revisão tem como foco a solução de problemas de otimização de arranjo físico até a
dimensão compatível com o método utilizado, ou seja, em função do número de departamentos a ser considerado.
Na seção 3.2, é apresentada uma aplicação do algoritmo Branch and Bound e as
relaxações necessárias, evitando assim a enumeração completa do problema. Mostra
o caminho percorrido na árvore de Branch (ramificações) e as alterações ocorridas em
função do método de busca utilizado. A seção 3.3 apresenta a heurística do gradiente
descendente com trocas de pares (SDPI). Por fim, na seção 3.4, a base teórica e o
algoritmo de treinamento da rede neural MLP são apresentados.
20
3.2
3.2
Algoritmo Branch and Bound
21
Com base na estratégia de divisão e conquista, Land e Doig [52] propuseram
o método Branch and Bound para a solução de problemas de programação inteira.
Este algoritmo divide o espaço de soluções factíveis em subespaços, evitando, desta
maneira, verificar todas as soluções possíveis, permitindo ao método maior velocidade
e eficiência. É um algoritmo enumerativo, cuja estrutura de resolução baseia-se na
construção de uma árvore de busca, na qual os nós representam os problemas candidatos
e os ramos representam as novas restrições que devem ser consideradas. Por intermédio
dessa árvore, todas as soluções inteiras da região viável do problema são enumeradas,
de modo implícito ou explícito, o que garante que todas as soluções ótimas serão
encontradas. O seu princípio básico é o uso de estimativas no valor da solução ótima
de um subproblema, para evitar a inspeção de partes de seu conjunto de soluções. Esta
seção está fortemente fundamentada em Haffner[49].
Considere P um problema de programação linear inteira e S o seu conjunto de
soluções. Seja Pr o problema relaxado de P e S̄ o conjunto de soluções deste problema
relaxado, definido por:
S̄ = x ∈ <n+ : Ax ≥ b
(3.1)
A operação de Branching (ramificação) consiste na definição de k poliedros S̄1,...,k ,
todos contidos em S̄, de tal modo que
k
[
i=1
S̄ i ∩ Zn+ = S̄
Isso implica que o problema P no poliedro original pode ser resolvido através da resolução de k subproblemas inteiros em poliedros menores.
A operação de bounding (limitação) consiste em encontrar a melhor solução contida em cada subespaço, ou seja, em cada poliedro S̄ determinado através da operação
de branching. Aquela operação fornece um modo de se calcular uma estimativa inferior
para o valor de qualquer solução factível para o problema P em S̄ i , uma vez que, para
todo S̄ i ⊂ S̄, tem-se:
min f (x) = cx : x ∈ S̄ i ≤ min f (x) = cx : x ∈ S̄ ∩ S̄ i
(3.2)
O algoritmo Branch and Bound trabalha com iterações, mantendo uma coleção L de
subconjuntos de S̄, a melhor solução factível conhecida x∗ ∈ S e o seu valor z ∗ =
3.2
22
f (x∗ ) = cx∗ . Inicialmente, L = S̄ e z ∗ = ∞ . Assim, terminando o algoritmo e
sendo factível, x∗ será uma solução ótima.
Em uma dada iteração do algoritmo, um poliedro S̄ i é extraído de L e a relaxação
a seguir é resolvida:
z̄i = min f (x) = cx : x ∈ S̄ i
(3.3)
Se o problema da equação anterior é infactível, ou se z̄i ≤ z ∗ , então não existe nenhuma
solução factível x ∈ S ∩ S̄ i , cujo valor de f (x) seja menor do que o da melhor solução
encontrada. O próximo passo é analisar a iteração i + 1. Caso contrário, se o problema
de (3.3) for factível e z̄i ≤ z ∗ , então x∗ = xi e z ∗ = z̄i . Esse procedimento garante
que os subconjuntos S̄ j ∈ L tais que z̄i ≥ z ∗ sejam retirados de L. Se a solução
ótima x̄i não for solução factível de P , um branching é executado no conjunto S̄ i e os
subconjuntos resultantes desta ramificação são inseridos em L e a iteração i = i + 1 é
realizada. Quando não existir nenhum subconjunto no conjunto L, o algoritmo termina.
O problema P é infactível se z ∗ = ∞; caso contrário z ∗ é a solução ótima.
Com relação aos limites inferiores utilizados, heurísticas poderão ser empregadas
para melhorá-los, ou seja, fazê-los o mais próximo possível da solução ótima. Com
isto, a árvore de branch ficaria menor e o tempo para se encontrar a solução ótima
diminuiria.
A forma de escolha do subconjunto S̄ i ∈ L a cada iteração i pode depender
da estrutura do problema apresentado, e o modo como a árvore de enumeração é
percorrida também é fator importante, sendo vários critérios utilizados para este fim.
As estratégias mais comuns para seleção do próximo problema são: Best First, Breadth
First e Depth First.
Busca em largura (Breadth First) é um método de busca que expande e examina
sistematicamente todos os nós de uma árvore, em busca de uma solução. Este algoritmo
realiza uma busca exaustiva numa árvore inteira, sem considerar o seu alvo de busca,
até que o encontre. Todos os nós filhos obtidos pela expansão de um nó são adicionados
a uma fila (primeiro que entra é o primeiro que sai - FIFO). Em implementações típicas,
nós que ainda não foram examinados por seus vizinhos são colocados num container
(como, por exemplo, uma fila) que é chamado de “aberto”. Uma vez examinados, são
colocados num container “fechado”.
3.2
23
Figura 3.1: Breadth Search
Busca em profundidade (Depth First) é um algoritmo utilizado para se fazer uma
busca em uma árvore de busca, iniciando em um nó raiz (normalmente aquele que
estiver no topo), explorando o máximo possível os seus ramos. Este tipo de algoritmo
de busca progride através da expansão do primeiro nó filho, aprofundando-se cada vez
mais até que o alvo da busca seja encontrado ou até que ele se depare com um nó que não
possua filhos (nó folha). Então, a busca retrocede (backtrack ) e recomeça no próximo
nó. Numa implementação não-recursiva, todos os nós expandidos recentemente são
adicionados a uma pilha, para realizar a expansão.
Figura 3.2: Depth Search
Best-First consiste de uma busca em largura usando funções de avaliação. É uma
combinação dos algoritmos Breadth First e Depth First já mencionados.
A estrutura geral do algoritmo Branch and Bound apresenta três etapas princi-
3.2
24
Figura 3.3: Best Search
pais: separação, relaxação e sondagem.
Na etapa de separação (branching), o problema original P é separado em subproblemas, sujeitos às seguintes condições:
• toda a solução viável do problema principal é uma solução de somente um dos
subproblemas;
• uma solução viável de qualquer um dos subproblemas também é uma solução
viável do problema principal.
A forma habitual de separação de um problema de programação inteira é através de
restrições conflitantes em uma única variável inteira (variável de separação ou de ramificação). A medida que se percorre a árvore de busca, a região viável dos nós filhos
gerados vai ficando cada vez mais limitada.
A relaxação consiste em, provisoriamente, ignorar algumas restrições do problema
principal, visando torná-lo mais fácil de resolver. A condição que deve ser satisfeita
é que o conjunto de soluções viáveis do problema original esteja contido no conjunto
de soluções viáveis do problema relaxado Pr . Se o problema relaxado não tem solução
viável, então o mesmo é verdadeiro para o problema principal. O valor mínimo encontrado para o problema principal é menor que o valor máximo do problema relaxado.
Se uma solução ótima de Pr é viável em P , então ela é uma solução ótima de P .
Na sondagem, os problemas candidatos são analisados para se determinar quais
são os promissores e quais deverão ser rejeitados. O problema candidato é rejeitado se:
3.2
25
• o problema candidato relaxado Pcr não tem solução viável. Isto significa que o
problema candidato Pc também não tem solução viável.
• a solução ótima do problema candidato relaxado Pcr é pior (bounding) do que a
melhor solução atualmente conhecida para P (solução incumbente).
Deve-se observar que a solução ótima do problema candidato relaxado é sempre
melhor ou igual à solução do problema candidato e de seus descendentes. Uma solução
ótima do problema candidato relaxado também é viável em Pc . Neste caso, ela é ótima
em Pc e ela é também factível em P . Caso seja melhor que a incumbente atual, a
solução deste problema candidato passa a ser a nova incumbente.
Para melhor entedimento deste algoritmo, as seguintes ações devem ser observadas:
Inicialização.
> Fazer i = 0
> Definir a incumbente inicial
> Iniciar a lista dos sub-problemas candidatos
Teste de Convergência.
> Se lista de candidatos é vazia ⇒ Fim. A solucão ótima é a incumbente atual
> Caso contrário, verificar próximo passo.
Seleção do Candidato.
> Escolher qual o próximo subproblema a ser examinado dentre os candidatos.(Utilizar
teste de Sondagem).
> Resolver o PL relativo ao Pcrk (problema candidato relaxado).
k
> Definir como limite inferior para os seus descendentes a solução ótima encontrada.(vinf
=
vP∗ k ).
cr
Testes de Sondagem.
> A sondagem poderá ser realizada no subproblema candidato se:
3.2
26
. Pcrk não possuir solução factível.
k
. vinf
> v ∗ sendo v ∗ o valor da incumbente atual.
. Pcrk possuir solução ótima inteira factível também no subproblema candidato, e
ainda se esta solução for menor do que a incumbente.
> Se o subproblema candidato foi sondado, retornar ao item 2.
Separação.
> Com relação ao subproblema Pck , a variável de separação escolhida deverá ser
inteira dentre aquelas que apresentam valores contínuos.
> Sendo nj a variável escolhida, com valor atual n∗j , gera-se dois novos subproblemas
descendentes acrescentando ao problema candidato as restrições abaixo:
(Pci+1 ) :
nj ≤ [n∗j ]
(Pci+2 ) :
nj ≥ [n∗j ] + 1
sendo [n∗j ] o maior inteiro de n∗j .
> i = i + 2, voltar para o item 3.
Exemplo 3.1 Seja o problema de programação inteira apresentada em (3.4) e sua
versão relaxada mostrada em (3.5):



min
v = 5n12 + 2n13 + 2n23 + β






suj. a 350n12 + 400n13 + β ≥ 400





350n12 + 210n23 + β ≥ 200
P


β≥0






nij ≥ 0, ∀ i, j





n12 , n13 , n23 inteiros



min
v = 5n12 + 2n13 + 2n23 + β






suj. a 350n12 + 400n13 + β ≥ 400


Pr
350n12 + 210n23 + β ≥ 200





β≥0





nij ≥ 0 ∀i, j
(3.4)
(3.5)
3.2
27
Figura 3.4: Árvore Branch and Bound
Figura 3.5: Árvore Branch and Bound (caminho mais curto)
Com relação ao problema relaxado Pr , a solução apresenta duas variáveis não
inteiras: n12 = 4/7 e n13 = 0, 5. Assim, a separação deste problema se dá com a
3.3
SDPI (Steepest Descent Pairwise Interchange)
28
escolha de uma das variáveis anteriores, por exemplo, n12 . As restrições verificadas
n12 ≤ 0 (nó 1) e n12 ≥ 1 (nó 2) resultam em dois problemas de PL a serem resolvidos.
Supondo que se escolha o nó 2, o resultado do problema relaxado apresenta ainda
resultado não inteiro para a variável n13 = 0, 125.
Sendo assim, o nó 2 deverá ser separado, dando origem aos nós 3 e 4. Escolhendo
este último a ser examinado, encontra-se a primeira solução inteira para o problema
4
original v ∗ = vinf
= 7. Como o valor da incumbente foi alterado, os nós 1 e 3 deverão
ser avaliados. Escolhendo o nó 3, uma separação em torno da variável n12 se faz
necessária. Com esta última separação, os descendentes 5 e 6 também apresentam
soluções inteiras, mas são descartadas por possuírem soluções piores que a incumbente
atual. Verifica-se a lista de candidatos e seleciona-se o único nó disponível (nó 1).
Efetua-se a separação em torno da variável n13 , gerando seus descendentes 7 e 8.
8
Optando-se por este último, encontra-se a solução inteira v ∗ = vinf
= 4, que é atualizada
como incumbente, pois é melhor do que a anterior.
7
O nó 7 é descartado, já que a sua solução vinf
= 201 > v ∗ é pior do que a
incumbente atual. Os nós 9 e 10 são mostrados somente para completar a árvore.
Da maneira como se percorreu a árvore, foi necessário resolver nove problemas
lineares até se obter a solução final. Isto mostra que os métodos de busca, explicados
anteriormente, combinados com heurísticas para determinação de bons limites inferiores, são fatores decisivos no tempo e eficiência nas resoluções dos problemas. Optando
pelo caminho de melhor busca, a árvore mostrada na figura 3.4 poderia ser substituída
pela apresentada na figura 3.5.
Deste modo, a solução ótima é conseguida com apenas cinco Pls contra nove Pls
mostrados anteriormente.
3.3
Steepest Descent Pairwise Interchange(SDPI)
Heurística que realiza trocas entre pares de locais, comparando os custos atuais
com os anteriores, em função das permutações encontradas. Foi primeiramente proposta por G.C. Armour e E.S. Buffa em [4]. Os custos são calculados levando-se em
consideração apenas aquelas alterações provenientes da troca, ou seja, aqueles componentes que não são afetados pela troca não entram no cálculo do custo, diminuindo
3.3
29
sensivelmente o esforço computacional. Observe que, para n = 4, para cada rodada de
iterações (tomando com base uma permutação qualquer), tem-se C24 = 6 possibilidades
de mudanças de pares. A diferença no valor do custo é computada e comparada com
a anterior. Considera-se, então, uma nova permutação, e o processo continua. Esta
Figura 3.6: Fluxograma SDPI [36]
seção é fortemente baseada em [36].
Para desenvolvimento de uma rotina para implementação, a expressão que rege
a diferença entre os custos atuais e anteriores deve ser considerada, sendo dada por:
3.3
DCTuv (a) = CT (a) − CT (a0 )
30
(3.6)
sendo DCT a diferença dos custos totais e a0 a nova permutação, proveniente da troca
de pares u e v.
A soma de todos os termos envolvendo u e v em CT (a) é dada por:
n
X
wiu d (a(i), a(u)) +
i=1,i6=v
n
X
wiv d (a(i), a(v)) + wuv d (a(u), a(v))
(3.7)
i=1,i6=u
Com a troca de pares u e v, a nova soma passa a ser:
n
X
wiu d (a(i), a(v)) +
i=1,i6=v
n
X
wiv d (a(i), a(u)) + wuv d(a(v), a(u))
(3.8)
i=1,i6=u
A equação (3.7) pode também ser escrita, adicionando-se:
0 = wvu d(a(v), a(u)) + wvu d(a(u), a(v)) − wvu d(a(v), a(u)) − wvu d(a(u), a(v)) (3.9)
como:
n
X
wiu d(a(i), a(u)) +
i=1
n
X
wiv d(a(i), a(v)) − wuv d(a(u), a(v))
(3.10)
i=1
Usando o mesmo artíficio, a equação (3.8) pode ser escrita :
n
X
wiu d(a(i), a(v)) +
i=1
n
X
wiv d(a(i), a(u)) + wuv d(a(v), a(u))
(3.11)
i=1
O fluxograma para esse procedimento, conforme Chu, L.K., [36], é apresentado na
figura 3.6.
A mudança no custo em razão da troca de u e v é dada pela diferença (3.10) e
(3.11):
DCTuv (a) =
n
X
(wiu − wiv )[d(a(i), a(u)) − d(a(i), a(v))] − 2wuv d(a(u), a(v)) (3.12)
i=1
Observe que a condição:
DCTuv (a∗ ) > 0
(3.13)
induz à realização de troca de pares, pois garante que a nova permutação leva a um
custo menor que a permutação atual.
Com o exemplo abaixo para n = 6 podemos esclarecer o processo.
3.4
31
Consideremos as matrizes abaixo e a permutação inicial (2, 4, 5, 3, 1, 6). Os pares
trocados (2, 6) e (4, 5) nos dá a maior redução para o custo total, considerando a permutação inicial dada. Executando outros ciclos de iterações encontramos o custo mínimo
valendo 92, Chu, L.K. [36].
Figura 3.7: Matriz Distância
Figura 3.8: Matriz Fluxo
Figura 3.9: Pares Permutados
3.4
3.4
Redes Neurais
32
Redes Neurais
Modo de computação não algorítmica que busca emular a estrutura de funciona-
mento de neurônios humanos. As Redes Neurais Artificiais (RNAs) são compostas por
nós, ou seja, unidades de processamento simples capazes de calcular funções matemáticas. Estes são ligados entre si, formando várias conexões que poderão ser relacionadas
a pesos, com a capacidade de deter conhecimentos apresentados no modelo.
Apesar de existirem muitas diferenças entre as redes biológicas e as artificiais, as
características comuns, ou seja, computação paralela e distribuída comunicando por
intermédio de conexões sinápticas; a detecção de características; a redundância (com
grande relevância no aprendizado) e modularização das conexões, permitem que as
RNAs exerçam várias atividades só vistas nos seres humanos.
Esta seção é baseada em S. Haykin [1].
O primeiro modelo proposto por McCulloch e Pitts [39] é uma imitação simplificada do neurônio biológico. Seu modelo matemático consiste em N terminais de
entrada x1 , x2 , . . . , xn , que emulam os dendritos do cérebro humano. Estes dispositivos
têm, como função, receber as informações, ou impulsos nervosos, provenientes de outros
neurônios e levados até o corpo celular. Apenas um terminal de saída y foi proposto no
modelo, representando os axônios do cérebro. O ponto de contato entre a terminação
axônica de um neurônio e o dendrito de outro neurônio é chamado de sinapse. Estas,
trabalhando com se fossem capacitores, regulam as informações transmitidas entre os
nós da rede neural.
A imitação do comportamento das sinapses nas RNAs acontece atribuindo pesos,
w1 , w2 , ..., wn aos terminais de entrada. Os valores destes pesos poderão ser positivos ou
negativos, dependendo se as sinapses são excitatórias ou inibitórias. A ponderação xi wi
é o efeito de uma determinada sinapse no neurônio. Logo, os pesos wi determinam em
que momento os neurônios devem considerá-las naquela conexão. Os sinais recebidos
dos neurônios pré-sinápticos são passados para o corpo dos neurônios pós-sinápticos,
onde são comparados com os outros sinais recebidos pelo mesmo. O disparo de um
neurônio biológico acontece quando a soma dos impulsos recebidos é maior do que o seu
limite de excitação (threshold ). No neurônio artificial, este comportamento é imitado
por um sistema que realiza a soma ponderada xi wi , compara este somatório com o
3.4
Redes Neurais
33
Figura 3.10: Célula.[51].
limite de excitação e decide se o neurônio deve ou não disparar.
Neste modelo, a ativação do neurônio é regida por uma “função de ativação”,
que realiza ou não a saída, dependendo do valor da soma ponderada das entradas.
Chamando de θ o limiar (threshold ) do neurônio, o nó da rede neural em questão terá
a sua saída ativa quando:
n
X
x i wi ≥ θ
(3.14)
i=1
sendo n o número de entradas e wi o peso relacionado à entrada xi . De acordo com a
figura 3.11, para valores de entradas x1 , x2 , . . . , xm , com valores 0 (zero) ou 1 (um), a
saída yk assumirá valores 0 ou 1, de acordo com a comparação entre a soma ponderada
dos pesos e o limiar θ.
Algumas limitações deste modelo devem ser consideradas. Dentre estas, destacamse, principalmente, a referente à possibilidade de implementação de somente funções
linearmente separáveis, tendo pesos constantes, sem a possibilidade de qualquer tipo
de ajuste.
A solução de problemas não linearmente separáveis é obtida com o uso de redes
com uma ou mais camadas intermediárias, ou escondidas. O uso de duas camadas
intermediárias permite a aproximação de qualquer função. A preocupação que se deve
ter na implementação deste tipo de rede é quanto ao número de nós utilizados nas
camadas intermediárias, pois ele irá definir a precisão e a definição da função objetivo.
3.4
Redes Neurais
34
Figura 3.11: Modelo de Neurônio [51].
As redes de múltiplas camadas precisam utilizar funções de ativação que sejam
não lineares e diferenciáveis, para que o gradiente possa ser calculado, direcionando o
ajuste dos pesos. A função sigmoidal logística, mostrada abaixo, é a mais indicada,
conforme aponta A.P.Braga [1]:
y=
1
1 + e−x/T
(3.15)
O parâmetro T determina a suavidade da curva.
Dependendo do tipo de problema que deverá ser tratado, na arquitetura da rede
neural são parâmetros importantes: número de camadas da rede; número de nós em
cada camada; tipo de conexão entre os nós; e topologia da rede.
A figura 3.12 mostra diferenciações diversas quanto à estrutura de rede. Assim,
as redes neurais podem ser classificadas:[1]
(a) Quanto ao número de camadas:
(i) Redes de camada única (figura 3.12 (a) e (e));
(ii) Redes de múltiplas camadas (figura 3.12 (b), (c), (d)).
(b) Quanto às formas de conexões dos nós:
(i) Feedforward ou acíclica (figura 3.12 (a), (b), (c));
3.4
Redes Neurais
35
a
b
c
d
e
Figura 3.12: Arquiteturas Redes Neurais. [1]
(ii) Feedback, ou cíclica (figura 3.12 (d), (e)).
(c) Quanto à conectividade:
(i) Rede fracamente ou parcialmente conectada (figura 3.12 (b), (c), (d));
(ii) Rede completamente conectada: (figura 3.12 (a), (e)).
O uso de redes neurais na resolução de problemas deve passar, em primeiro lugar,
pela fase de aprendizagem, na qual a rede extrai padrões importantes do problema,
criando o seu próprio modelo. É um processo iterativo, pelo qual os parâmetros da
rede são ajustados, coletando-se informações do ambiente no qual está operando. O
método de aprendizado mais comum é o supervisionado, pelo fato das entradas e saídas
desejadas serem fornecidas por um supervisor. A figura 3.13 apresenta o modelo básico
desse método.
O que se espera encontrar é um padrão entre a entrada e a saída. A diferença
entre a saída calculada pela rede e a diferença da saída desejada tende a diminuir à
medida que o processo continua. Isto se deve aos ajustes realizados nos pesos das
conexões, com o objetivo de minimizar esta diferença a cada passo. O desempenho da
rede poderá ser medido, verificando-se a soma dos erros quadráticos de todas as saídas.
A forma geral para alteração dos pesos por correção de erros, segundo D.E.Rumelhart
3.4
Redes Neurais
36
Saída
Professor
RNA
Entrada
Erro
Figura 3.13: Modelo Aprendizado Supervisionado [1]
Figura 3.14: Aprendizado do Perceptron
3.5
Redes Neurais MLP
37
et al [46], é dada pela seguinte equação :
wi (t + 1) = wi (t) + ηe(t)xi (t)
(3.16)
sendo η a taxa de aprendizado e xi (t) a entrada para o neurônio i no tempo t. O termo
e(t) do erro equivale a:
e(t) = d(t) − y(t)
para d(t) a saída desejada e y(t) a resposta calculada no instante t.
Assim, a minimização da soma dos erros quadráticos das saídas poderá ser dada,
segundo D.E.Rumelhart [46], pela expressão :
k
F (w) =
1X
(di − yi (w))2
2 i=0
(3.17)
na qual k é o número de nós da saída da rede.
Na determinação da condição de erro mínimo, duas situações podem ocorrer:
• a superfície do erro, dada pela expressão (3.17), possui um único mínimo, quando
a rede é formada inteiramente por unidades de processamento lineares; ou
• a superfície do erro possuir, além do mínimo global, um ou mais mínimos locais,
quando a rede é formada por unidades de processamento não-lineares.
Neste último caso, nem sempre o mínimo global é atingido, já que as superfícies de
erro são irregulares, podendo levar à um mínimo local indesejado.
O interesse na utilização de redes neurais é resolver problemas não-linearmente
separáveis. Isto leva ao uso de redes neurais com uma ou mais camadas intermediárias
ou escondidas, de modo que seja possível a aproximação de qualquer função. Uma das
soluções para este problema seria subdividi-lo e aplicar, em cada um deles, uma rede
simples. Mas isto muita das vezes é impossível ou muito complicado.
3.5
Redes Neurais MLP
Nas redes Multilayer perceptrons (MLP), o processamento em cada nó é baseado
nos processamentos dos nós anteriores conectados a ele. As camadas intermediárias
geram uma codificação interna das camadas de entrada, servindo de definição da saída
3.5
Redes Neurais MLP
38
Figura 3.15: Mínimos locais e platôs em uma superfície de erro[1]
da rede. Não se pode deduzir que quanto maior for o número de camadas intermediarias
da rede, melhor será o resultado. Cada vez que o erro é medido durante o treinamento,
ele se torna menos preciso. A camada final recebe somente uma estimativa do erro. A
penúltima camada recebe a estimativa da estimativa do erro.
Existem, na literatura, vários algoritmos para treinamento das redes MLP. O mais
utilizado é o algoritmo back-propagation, que utiliza os pares entrada e saída da rede
para ajuste dos pesos. Duas fases são utilizadas neste mecanismo: na primeira, denominada forward, a rede é percorrida no sentido entrada/saída, na qual, em função dos dados de entrada, se define a saída; a segunda, chamada backward, sentido saída/entrada,
os pesos são atualizados nas conexões, utilizando as saídas desejada e fornecida pela
rede, procurando diminuir a diferença entre elas (G.Cybenko, [11]). A técnica de backpropagation está representada na figura 3.16.
A regra delta, proposta por Widrow e Hoff [1], serve de suporte para o algoritmo
backpropagation. A base deste algoritmo se prende nos ajustes dos pesos nos nós, de
modo a definir os erros das camadas intermediárias. Os ajustes destes pesos são calculados utilizando o método do gradiente, ou seja, para uma condição inicial qualquer
w(0) = wi , deseja-se obter a direção do ajuste a ser aplicado no vetor de pesos, de
forma a caminhar em direção à solução ótima. Este é o motivo pelo qual as funções
de ativação das redes MLP precisam ser diferenciáveis. O algoritmo backpropagation
é baseado nesta regra delta e por isso também é chamado de regra delta generalizada
3.5
Redes Neurais MLP
39
Figura 3.16: Fluxo processamento do Algoritmo Backpropagation.[1]
(A.P.Braga et al, [1]).
A medida do erro total é dada pela equação:
p
k
1 XX p
(d − yip )2
E=
2 1 i=1 i
(3.18)
sendo p o número de padrões, k o número de unidades de saída, di é a i-ésima saída
desejada e yi é a i-ésima saída calculada pela rede.
Como visto acima, é a soma dos erros dos nós de saída que deverá ser minimizada.
Sem risco de perda de generalidade, a minimização do erro para cada padrão levará
à minimização do erro total. Assim, tem-se (o desenvolvimento a seguir tem como
referência A.P.Braga et al,[1])
k
1X
(di − yi )2
E=
2 i=0
(3.19)
A variação do peso para um dado padrão (gradiente descendente do erro) é dado
por:
∆wji = −k
sendo k uma constante.
∂E
∂wji
(3.20)
3.5
Redes Neurais MLP
40
O ajuste de cada peso em cada nó da rede em busca do erro mínimo:
∂E ∂netj
∂E
=
∂wji
∂netj ∂wji
Sendo netij =
n
P
(3.21)
xi wji , tem-se
i=1
∂netj
=
wji
n
P
∂
xl wjl
l=1
(3.22)
= xi
wji
O lado direito da equação (3.21) mede o erro no nó j e geralmente é chamado de
δj :
δE
∂netj
(3.23)
∂E ∂yj
δE
=
∂netj
∂yj ∂netj
(3.24)
δj =
Aplicando a regra da cadeia temos:
δj =
contudo,
∂yj
∂f (netj )
=
= f 0 (netj )
∂netj
∂netj
(3.25)
Com relação ao erro no nó da última camada:
∂E
=
∂yi
∂( 21
k
P
(di − yi )2 )
i=1
(3.26)
∂yj
que é a fórmula da regra delta .
Com referência à equação 3.24, substituindo os dois termos do lado direito, temos:
δj = (dj − yj )f 0 (netj )
(3.27)
Se o nó de saída não for o nó j e utilizando a regra da cadeia:
M
M
X ∂E ∂netl X ∂E
∂E
=
=
∂yj
∂net
∂netl
l ∂yj
l=1
l=1
∂
n
P
wil yi
i=1
∂yj
=
M
X
∂E
wjl
∂net
l
l=1
(3.28)
sendo,
M
M
X
X
∂E
wjl =
δl wjl
∂net
l
l=1
l=1
(3.29)
3.5
Redes Neurais MLP
41
Com referência à equação (3.24), substituindo, mais uma vez, os dois termos do
lado direito, tem-se para a camada intermediária:
δj = f 0 (netj )
X
∂l wlj
(3.30)
l
Logo, a generalização da fórmula de ajuste de pesos é dada por:
∆wji = ηδj xi
(3.31)
wji (t + 1) = wji (t) + ηδj (t)xi (t)
(3.32)
que é o mesmo de:
Então, para o nó de saída, o erro δj será definido pela equação 3.27; caso contrário,
pela equação 3.30.
3.5.1
Algoritmo de Levenberg-Marquardt
Visando minimizar a equação (3.19), alguns algoritmos trabalham em conjunto
com o backpropagation. Dentre eles, destaca-se o algoritmo Levenberg-Marquardt, que
calcula as derivadas de segunda ordem do erro quadrático em relação aos pesos, o que
vale dizer o mesmo que derivar o algoritmo backpropagation tradicional. Esta ação faz
com que o treinamento seja mais rápido. Este algoritmo utiliza-se da matriz jacobiana
para o cálculo da matriz hessiana, nos mesmos moldes do método Quasi-Newton. Logo,
conforme [2]:
H=
∂ 2 ER (W )
∂W 2
(3.33)
∂e(W )
∂W
(3.34)
J=
sendo e(W ) definido como:
e(W ) =
n
X
(yi − yd )
(3.35)
i=1
yi representa a saída calculada e yd a saída desejada.
Como já se sabe, o treinamento da rede neural depende da soma dos erros
quadráticos, sendo assim, a matriz hessiana é calculada usando a matriz jacobiana
como artifício, já que esta última é de cálculo mais simples:
3.6
Colônia de Formigas
42
H = J T (W )J(W )
(3.36)
Os pesos são atualizados como é feito no método de Newton:
W (k + 1) = W (k) − H −1 gk
(3.37)
gk = 2J T (W )e(W )
(3.38)
A parcela gk vale:
Combinando as equações anteriores, o algoritmo de Levenberg-Marquardt, atualiza os seus pesos:
W (k + 1) = W (k) − [J T (W )J(W ) + µk I]−1 J T (W )e(W )
(3.39)
Sendo I a matriz identidade e µk a constante do algoritmo em questão (Anderson
Henrique Barbosa et al,[2])
3.6
Com base na interação de vários agentes autônomos, a colônia de formigas tra-
balha de forma cooperativa a procura de alimentos. Nesta ação de procura, com o objetivo de preservação da espécie, as formigas depositam no solo uma substância química
(feromônio), que serve como meio de comunicação entre elas. Na interação dos diversos agentes autônomos, na procura por alimento, a concentração do feromônio se torna
mais acentuada no caminho mais curto. Isto porque, a cada momento, mais formigas
utilizam este caminho, depositando cada vez mais feromônio. Esta meta-heurística de
inteligência coletiva possui as seguintes características (Leandro dos Santos Coelho et
al [34]):
• algoritmo não determinista, já que não garante um ótimo global.
• algoritmo paralelo e adaptativo, pois os diversos agentes agem de forma simultânea e independente.
3.7
Conclusão
43
• algoritmo cooperativo, visto que o caminho escolhido por cada agente tem como
referência as informações depositadas por outros agentes, quando da procura por
alimentos.
No problema quadrático de alocação, no caso de arranjos físicos, considere-se
uma população de m formigas, sendo k uma formiga qualquer. A probabilidade de que
a k-ésima formiga atribua o departamento j à localização i é dada por(Leandro dos
Santos Coelho et al [34]):
pkij (t)
=
[τ (t)]α [ηij ]β
P ij
[[τij (t)]α [ηij ]β
(3.40)
Nesta equação, α e β são ajustados heuristicamente, sendo α a ponderação
do feromônio (0 ≤ α ≤ 1); β a ponderação da informação heurística (0 ≤ β ≤ 1);
ηij =
1
dij
é a visibilidade entre as variáveis j e i e vice-versa; dij é distância euclidiana
entre as localizações; τij é a intensidade da trilha no caminho.
3.7
Conclusão
Limitações de cada método de resolução ficam evidentes. O método Branch and
Bound é melhor aplicado para problemas discretos, no qual se utilizam relaxações da
condição de integralidade para solucão dos problemas, necessitando de grande esforço
computacional à medida que o problema possui maior número de variáveis envolvidas.
As redes neurais MLP e o algoritmo SDPI, metaheurísticas que necessitam de ajustes
para fugir de mínimos locais, não garantem solução ótima e, no caso das redes neurais,
precisam de um banco de dados para o seu treinamento.
Capítulo 4
Aplicação de Redes Neurais MLP à
Solução do Problema de Arranjo
Físico
4.1
Introdução
Neste capítulo, é apresentado um estudo em uma fábrica de embalagem metálica,
no qual todos foram abordados todos os processos de fabricação e algumas necessidades
administrativas. Áreas de conhecimento inerentes a este processo são avaliadas, construindo uma base de informação essencial para a coleta de dados. O tipo de produto
que é fabricado nesta unidade industrial permite considerar cada módulo de fabricação
(departamento) como se fosse um equipamento específico. Esta consideração faz com
que as áreas das localizações dos módulos sejam iguais, predefinindo os corredores de
circulação, as distâncias entre as localizações, área total necessária para implantação do
projeto e as áreas individuais requeridas. A tabela 4.1 apresenta os fatores do projeto
e as áreas de conhecimento envolvidas (Torres, Isaías [59]).
As atividades envolvidas para fabricação do produto final requerem movimentação de pessoas e equipamentos, trocando informações e materiais entre os departamentos. Estas trocas representam as necessidades de comunicação entre os pares. No
problema tratado, as áreas responsáveis pelas operações de corte e repuxo do corpo,
tampa e fundo da embalagem metálica a ser produzida, devem estar próximas do es-
44
4.2
Desenvolvimento do Modelo de Projeto
45
Tabela 4.1: Áreas de conhecimento para projeto de arranjos físicos
Fatores de Projeto
Áreas e sub-áreas de conhecimentos envolvidas
Equipamento.
Eng. de Processos, Ergonomia, Organização
Operação (Transformação e
Eng. de Processos, Eng. de Materiais, Eng. de Máquinas,
Montagem).
Logística,Ergonomia, Eng. de Segurança, PCP.
Materiais.
Eng. de Materiais, Logística, Eng. de Segurança, Ergonomia.
Manutenção.
Eng. de Manutenção, Eng. de Máquinas, PCP.
Segurança e Saúde.
Eng. de Segurança, Eng. de Processos, Saúde Ocupacional,
do trabalho, Eng. de Máquinas, Eng. de Segurança.
Administração, Organização do Trabalho.
Almoxarifado/Estoque.
Logística, PCP.
Serviços auxiliares de Fábrica.
Eng. de Processos, Eng. de Máquinas, PCP.
Edificação
Arquitetura, Eng. Civil, Eng. Segurança, Ergonomia, PCP
Sistemas de Movimentação
PCP, Logística, Ergonomia, Eng. de Segurança.
Utilidades (Gás, Energia)
Eng. de Processos, Eng. de Máquinas, Eng. de Materiais.
Fluxo de Materias,
PCP, Logística, Eng. Econômica, Eng. de Segurança,
Pessoas e Informações.
Organização do Trabalho.
Espaço
Ergonomia, Eng. de Segurança, Eng. de Processos,
PCP, Arquitetura.
Serviços de Pessoal
Organização do Trabalho, Eng. de Segurança,
Arquitetura, Administração.
toque de matéria prima. Entre o setor de secagem e os aplicadores de vedante, existe um
alto grau de dependência, obrigando estas duas operações a ficarem próximas. Sendo
assim, a disposição física destes módulos deve oferecer, obedecendo às restrições, o
menor caminho para o maior fluxo entre os pares.
4.2
Otimizar o arranjo físico de uma planta industrial significa decidir de que maneira
as áreas de trabalho serão dispostas nesta instalação. Entende-se como área de trabalho
a ocupação de espaço físico por parte de, por exemplo, máquinas, pessoas, departamentos, área para estoques, oficinas, dispositivos de segurança, etc. O objetivo principal é
tornar lógicos os movimentos inerentes ao processo de produção, sejam movimentos de
pessoas, máquinas ou materiais.
Quando se trata de designar objetos a locais de tal maneira que cada local tenha
somente um objeto, conhecidas as distâncias entre os locais e os fluxos entre os de-
4.2
46
partamentos, o modelo baseado no problema quadrático de alocação permite encontrar
uma disposição de custo mínimo dos departamentos aos locais, sendo o custo dado pelo
produto distância e fluxo.
4.2.1
Variáveis de Interesse
A minimização do custo total de interconexão deverá ser regida pelas seguintes
variáveis:
• distância entre as localidades;
• fluxo entre os departamentos, que representa o grau de ligação entre eles, evidenciando a importância entre os pares no processo de fabricação;
• número de departamentos;
• número de localidades.
Figura 4.1: Distribuição espacial das localidades
A figura 4.1 mostra a distribuição espacial das localidades e as distâncias, em metros,
entre elas. Observe que o projeto possui vinte e dois departamentos e vinte e duas
4.2
47
Tabela 4.2: Relação dos Departamentos do Projeto.
Item
Departamento
Item
Departamento
Item
Departamento
1
Administração
9
Repuxo Tampa
17
Repuxo Fundo
2
Cont. de Qualidade
10
Vedante Tampa
18
Vedante Fundo
3
Est. Mat. Prima
11
Secagem Tampa
19
Estoque Fundo
4
Contabilidade
12
Estoque Tampa
20
Recravação
5
Expedição
13
Corte Corpo
21
Est. Prod. Acabado
6
Rec. de Materiais
14
Repuxo Corpo
22
Oficina Mecânica
7
Refeitórios
15
Estoque Corpo
8
Corte Tampa
16
Corte Fundo
localizações a serem associados, tendo a denominação dada na tabela 4.2.
4.2.2
Formulação Matemática Proposta
O problema a ser resolvido, ou seja, permutar departamentos em locais previamente conhecidos, de tal modo que o custo de transporte entre um departamento e
outro seja o mínimo possível, é inteiro e binário. Inteiro, porque os departamentos e
os locais não podem ser subdivididos. Binário, porque um dado departamento está
ou não está em um determinado local. Sendo assim, o modelo apresentado atende às
necessidades do projeto.
Seja fij o fluxo entre os departamentos i e j e dkp a distância entre as localizações
k e p. A função objetivo é definida por:
min
n
n
X
X
fij dkp xij xkp
(4.1)
i,j=1 k,p=1
sendo o produto cijkp = fij dkp o custo de transporte a considerar. Esta função está
sujeita às restrições:
n
X
xij = 1, 1 ≤ j ≤ n,
(4.2)
n
X
xij = 1, 1 ≤ i ≤ n,
(4.3)
xij ∈ {0, 1} , 1 ≤ i, j ≤ n
(4.4)
i=1
j=1
4.2
48
As restrições indicam a relação bijetora entre departamentos e localidades, ou
seja, cada departamento em um local e cada local somente com um departamento.
Observe que (4.1) é uma fun ção não-linear, visto a existência de produto entre as
variáveis xij e xkp . Uma técnica de resolução deste tipo de modelo não-linear é linearizálo, através de algum procedimento matemático, e resolvê-lo como um problema de
otimização linear. Uma forma de realizar esse intento é como segue. O produto fij dkp
é chamado custo de transporte cijkp entre os departamentos. O termo cijkp xij xkp da
função objetivo contém a não linearidade. Uma vez que as variáveis xij xkp são binárias,
possuindo os valores 0 ou 1, o custo somente terá valor diferente de zero quando estas
duas variáveis valerem 1. Assim, pode-se substituí-las por somente uma variável yijkp =
xij xkp , de modo que:
yijkp

 1, se x = 1 e x = 1
ij
kp
=
 0, caso contrário.
(4.5)
Com este artifício de linearização, o algoritmo Branch and Bound pode ser aplicado
até o limite de número de departamentos suportado pela plataforma utilizada.
O problema em análise consiste na alocação de 22 (vinte e dois) departamentos,
relacionados na tabela 4.2, em 22 (vinte e dois) locais, com as distâncias entre os
locais conhecidas. Estes departamentos guardam entre si graus de interconexão, que
podem ser medidos pelo fluxo de transporte existente entre eles. Os valores destes
fluxos variam para cada tipo de atividade industrial, representando as necessidades
de ligação entre os pares. Os valores de fluxo dependem, principalmente, do tipo de
produto e da quantidade a ser fabricada, diferenciando os departamentos em razão de
sua importância dentro da fábrica.
Para se resolver o problema com base no modelo proposto, o entendimento do
que a variável yijkp representa é essencial. Sabendo-se que se trata de um problema
inteiro binário, cada elemento representado por esta variável é um departamento a ser
alocado. O valor de yijkp será igual a 1 (um) se o departamento i estiver posicionado
em um determinado local e terá valor zero se não estiver.
Considere y como sendo um vetor. Para o primeiro departamento, este vetor varia
das posições y1 até y22 ; para o segundo departamento, serão atribuídas as posições de
y23 até y44 e assim sucessivamente. Portanto, o vetor y terá 484 posições no problema
abordado, já que deve-se posicionar vinte e dois departamentos para vinte e dois locais.
4.3
Aplicação do Algoritmo Branch and Bound
49
A matriz formada por estes vetores terá dimensão 22 × 22 e será construída com base
nas matrizes fluxo e distância, já definidas.
Em relação às restrições, cada departamento ocupará somente um local, ou seja, a
soma dos valores de y para este departamento deverá ser igual a unidade. Por exemplo,
66
P
xi = 1. Ao mesmo tempo, cada local deverá ter um
para o terceiro departamento,
e somente um departamento.
4.3
i=45
No caso específico da fábrica de embalagem, o número de departamentos con-
siderado (n = 22) é elevado para aplicação do algoritmo Branch and Bound, face
ao crescimento exponencial das variáveis e restrições envolvidas. Este problema será
devidamente tratado com a utilização de redes neurais MLP.
Sendo assim, será desenvolvida a lógica do algoritmo Branch and Bound para
n = 4 departamentos, oferencendo suporte para instâncias maiores (n ≤ 15).
Considere as matrizes aleatórias de fluxo (F ) e distância (D) entre os departamentos.


0 2 10 8




 2 0 4 12 

F =


 10 4 0 6 


8 12 6 0


0 1 9 7




 1 0 3 11 

D=


 9 3 0 5 


7 11 5 0
(4.6)
(4.7)
4.3
50
Tabela 4.3: Permutações possíveis
n
No. de Diagonais
Ordem Matriz Custo
Arranjos Possíveis
4
2
6
4!=24
5
5
10
5!=120
6
..
.
9
..
.
15
..
.
6!=720
..
.
12
54
66
12!=479.001.600
de modo que a matriz de custo resultante seja:


2 18 14 6 22 10




 10 90 70 30 110 50 




 8 72 56 24 88 40 

C=


 4 36 28 12 44 20 




 12 108 84 36 132 60 


6 54 42 18 66 30
(4.8)
Como pode ser visto, a dimensão da matriz de custo é 6×6. Isto se deve às diagonais existentes no polígono formado pelos departamentos. Logo, para n departamentos,
o número de ligações será dado por:
n(n − 3)
+n
2
(4.9)
A ordem da matriz-custo a considerar será igual ao número total de interconexões.
A tabela 4.3 mostra o número de permutações possíveis em problemas crescentes em
número de departamentos (n).
No exemplo em questão, o número de arranjos possíveis é mostrado na figura 4.2.
O resultado da aplicação do algoritmo Branch and Bound a esse exemplo particular é
mostrado na tabela 4.4. Como pode ser verificado no código do programa e na tabela
4.4, os arranjos 11 e 14 têm custo mínimo de 198, sendo portanto adequados para
localização dos quatro departamentos. Verificando os arranjos possíveis para n = 4 ,
os pares de arestas (1, 2), (3, 4) e (1, 4), (2, 3) não poderão ser adjacentes. O código para
sua obtenção está apresentado no apêndice A.1 e utiliza explicitamente as restrições
apresentadas no problema. A tabela 4.4 mostra a saída do exemplo mostrado, quando
aplicado ao código desenvolvido.
4.4
51
Figura 4.2: Arranjos para 4 departamentos
De acordo com a tabela 4.4, pode-se verificar o comportamento decrescente do gap
relativo entre os limites (GREL). Calculado em relação ao melhor limite inferior (MLI)
e o melhor ponto inteiro (MPI), esta medida demonstra o quão rápido o algoritmo
alcança o ótimo global. É calculado de acordo com a expressão: GREL =
para o nó sete, por exemplo, tem-se: GREL =
210−198
210
M P I−M LI
MP I
,
∼
= 8, 5%
Observando a primeira coluna, verifica-se que foi necessário explorar nove nós
da árvore de branch para alcançar a resposta desejada. Este valor está intimamente
ligado à estratégia utilizada para o "corte" (branching) desta árvore e o modo como
a percorremos. Para este caso exemplo, foi adotada a estratégia de corte mininfeas
(minimum integer infeasibility), ou seja, o corte é feito em relação à variável que possui
valores próximos a zero ou um, mas não igual a zero ou um. Quanto ao método
de procura, o best search foi aplicado. A alteração destas estratégias pode mudar
sensivelmente a quantidade de nós explorados.
A segunda coluna da tabela 4.4 exibe as relaxações que foram realizadas em torno
das variáveis inteiras para que se fosse possível utilizar o algoritmo Branch and Bound.
4.4
Aplicação da Rede Neural MLP
52
Tabela 4.4: Resultado Branch and Bound
Relaxação Melhor ponto
Nós não
Melhor limite
Nós
Gap relativo
Explorados
Linear
Inteiro
explorados
inferior
entre os limites(%)
1
186
-
2
186
-
2
222
222
1
186
16
3
186
222
2
186
16
4
222
222
1
186
16
5
192
222
2
186
16
6
210
210
1
192
8,5
7
196
210
2
192
8,5
8
198
198
1
196
1
9
220
198
0
196
1
4.4
O objetivo principal desta seção é mostrar a aplicação do algoritmo backpropaga-
tion em conjunto com o algoritmo Levenberg-Marquardt para treinamento de uma rede
neural MLP. Quatro etapas foram consideradas, a saber:
• Preparação dos dados;
• Criação da rede neural;
• Treinamento da rede; e
• Simulação da rede para o problema apresentado.
4.4.1
Preparação dos dados
Como já dito anteriormente, para valores n > 15, não é aplicável a utilização de
algoritmos enumerativos para a solução de problemas combinatoriais deste porte. O
uso de heurísticas se torna necessário para solução adequada do problema.
Como acontece no aprendizado dos seres humanos, as redes neurais também
necessitam de treinamento suficiente para aprender. Este treinamento depende diretamente da quantidade de informações disponíveis, formando uma base de dados
4.4
53
confiável. Mas, neste caso, a quantidade de dados à disposição não é suficiente para
treinamento da rede neural face a necessidade de validação da rede e a complexidade da
solução inerente a estes problemas. Logo, uma heurística foi utilizada para formar um
banco de dados capaz de treinar a rede neural adequadamente. Gradiente Descendente
com Trocas de Pares e um gerador de matrizes de entrada (22 × 22) construíram a base
de dados para treinamento da rede, ou seja, as matrizes fluxo e distância, bem com os
vetores permutação, que guardam valores da função objetivo tão próximo do mínimo
quanto possível.
É importante ressaltar que o uso desta heurística, tem como objetivo, apresentar
à rede as características inerentes aos dados de entrada relacionados com os dados de
saída, não se preocupando especificamente com o valor exato da resposta. Devemos
“ensinar” a rede neural a descobrir a lógica utilizada pela heurística.
Para cada departamento, existem fluxos relacionados com os demais departamentos, o mesmo acontecendo para as distâncias em relação aos locais. Com a vetorização
das matrizes fluxo e distância, necessária para configurar a rede neural, o número de
entradas teria a dimensão 968 × 1. Mas como estas matrizes são simétricas podem-se
eliminar as diagonais (valores iguais à zero) como também os elementos das matrizes
triangular superior(ou inferior), já que possuem os mesmos valores. Com este artifício,
diminui-se sensivelmente a quantidade de dados de entrada, descartando aqueles que
não contribuem para o treinamento. O objetivo é construir uma rede neural capaz
de determinar a melhor disposição dos departamentos nos locais, apresentando a esta
rede as matrizes fluxo e distância, de tal maneira que o custo seja o mínimo possível.
Tem-se um total de 100 pares de vetores de entrada, com 2 × 231 elementos cada par
(matriz fluxo e matriz distância), e 100 vetores de saída com 22 posições, indicando
quais as localizações dos departamentos. Neste ponto, é interessante verificar se existe
alguma redundância entre os dados de entrada, devido à possível correlação existente
entre eles. Para isto, aplica-se a análise de componentes principais, que consiste, basicamente, em eliminar aqueles componentes que pouco contribuem para a variação dos
dados. Em seguida, normaliza-se os dados de entrada [pn,meanp,stdp] = prestd(p), de
modo que a média dos valores seja zero e a variância um. Após o treinamento, a conversão dos dados normalizados para os dados originais é feita, com o auxílio da matriz
ptrans, [ptrans,transMat] = prepca(pn,0.01), sendo que o parâmetro 0,01 indica que
4.4
54
são eliminados aqueles elementos que contribuem com até 1% do total de variação do
conjunto.
Sendo Q o conjunto dos 100 pares de vetores de entrada mencionados anteriormente, dividiu-se este conjunto em quatro partes iguais, conforme figura 4.3. Reservouse um quarto para a validação , um quarto para o teste e dois quartos para o treinamento
da rede neural, garantindo, assim, que os dados sejam escolhidos de maneira uniforme
através dos dados originais.
Figura 4.3: Preparação dos Dados.
Agora pode-se criar a rede neural para o treinamento Neural (Network Toolbox
User’s Guide, [55]).
4.4.2
Criação da Rede Neural
Em primeiro lugar, definiu-se o número de camadas escondidas da rede. A escolha
para duas camadas se deve ao fato desta configuração conseguir mapear quaisquer
dados de quaisquer função, linear ou não-linear apresentada à rede. A utilização de
muitas camadas escondidas não é aconselhável, pois poderia comprometer as correções
dos erros, tão necessárias na retropropagação. O que se procura definir é um número
pequeno de camadas com número adequado de neurônios. Normalmente, o uso de uma
camada escondida é suficiente, mas para este caso do PQA, duas camadas escondidas
foram necessárias e a quantidade de neurônios por camadas foi determinada em função
da dimensão do problema. Este procedimento é empírico. Mesmo assim, existem
4.4
55
propostas para determinação do número de neurônios: calcula-se a média aritmética
ou mesmo a média geométrica entre as dimensões da entrada e saída da rede e atribui
este valor ao número de neurônios na camada escondida. Ou, de posse da quantidade
de exemplos disponíveis para o treinamento, utiliza-se um número de sinapses dez vezes
menor que este número. Se o número de exemplos for muito maior que o número de
sinapses, overfitting é improvável, no entanto pode ocorrer underfitting (a rede não
converge durante o seu treinamento).
Para este caso, a arquitetura da rede neural foi baseada em duas camadas intermediárias com função de transferência tan sigmoid [55] e uma camada de saída com
função de transferência linear. Foram usados cinco neurônios nas camadas escondidas
e esta rede deverá ter vinte e dois neurônios na camada de saída já que tem-se vinte e
dois objetivos a serem alcançados (vetor posição de cada departamento).
Figura 4.4: Estrutura Rede Neural
O esquema mostrado na figura 4.4 mostra a estrutura da rede com duas camadas
intermediárias trabalhando com cinco neurônios cada uma.
4.4.3
Treinamento da Rede Neural MLP
Grande cuidado deve ser tomado na escolha dos parâmetros para treinamento
do algoritmo backpropagation na configuração de uma rede neural MLP. Pequenas
diferenças na escolha destes parâmetros podem levar às grandes diferenças no tempo
de treinamento e comprometer a generalização desejada. Não existe um método para
estas escolhas, somente a experiência e dados históricos ou gerados servem como base.
4.4
56
O meio termo entre um modelo muito rígido e um extremamente fléxivel seria o
ideal, a ponto de não modelar fielmente os dados ou modelar também o ruído. Não
se deseja que a rede responda aos valores exatos dos dados de entrada, e sim, às
características inerentes à eles.
As sinapses dos neurônios de cada camada armazenam as informações do procedimento a ser aprendido pela rede, e as saídas de cada camada alimentam as entradas
da camada seguinte durante a fase de treinamento. Para que este treinamento seja bem
efetuado, o parâmetro taxa de aprendizado foi bem definido. Este valor variou entre
0, 1 e 1 e que não permita um aprendizado muito lento e oscilações no treinamento,
prejudicando a convergência do processo. Um dos objetivos foi escapar de mínimos locais, conseguindo um treinamento rápido e seguro. O algoritmo Levenberg-Marquardt
(trainlm) foi utilizado em conjunto com o backpropagation.
Figura 4.5: Código para o Treinamento Rede MLP
4.4.4
Simulação da Rede Neural MLP
Feitas as etapas anteriores, a função ”Sim”(figura 4.7) simula a rede neural,
atribuindo à entrada os valores das matrizes distância e fluxo devidamente vetorizadas,
ou seja, dimensão [231 × 1] para cada uma delas, totalizando 462 elementos.
Matriz triangular superior equivale às distâncias e matriz triangular inferior aos
fluxos entre os departamentos.(ver tabela 4.5)
O vetor permutação gerado pela rede neural deverá ser ajustado para representar
as posições dos departamentos nos locais. Os valores deste vetor apresentam variações
em torno dos números inteiros pertecentes ao intervalo [1, 22], já que a convergência
da rede não é absoluta. Deve-se aproximá-los para o inteiro mais próximo. O primeiro
4.4
Figura 4.6: Treinamento (Normalizado) Rede Neural
Figura 4.7: Código para Simulação da Rede Neural MLP
57
4.4
58
Tabela 4.5: Matriz de Entrada: Fluxo e Distância
.
20
45
68
88
25
36
65
85
112
48
62
71
87
117
127
68
92
95
115
118
148
8
.
26
48
69
35
32
47
68
96
52
58
58
79
105
114
71
95
90
115
111
138
9
1
.
22
43
58
46
33
54
81
71
66
55
80
99
105
86
109
96
125
110
135
6
7
8
.
21
78
63
31
46
71
88
77
58
83
96
98
101
121
102
133
111
130
6
7
7
1
.
96
78
38
42
60
103
87
63
86
91
90
112
131
107
139
110
124
4
1
1
1
1
.
24
60
81
105
23
44
60
71
103
115
44
67
74
91
100
131
1
6
1
1
1
1
.
43
58
82
25
29
37
51
82
93
41
64
59
83
82
112
1
5
1
1
1
1
7
.
21
49
67
49
27
52
67
72
75
93
72
103
80
101
1
6
1
1
1
1
3
7
.
28
78
54
27
46
50
52
81
95
67
99
68
84
1
5
1
1
1
1
3
5
8
.
99
72
46
52
36
30
96
105
72
101
60
65
1
2
3
6
1
1
3
4
1
1
.
28
53
55
89
102
21
45
54
69
82
114
1
6
1
1
1
1
1
1
1
1
1
.
28
28
61
74
27
44
33
59
57
88
1
5
1
1
1
1
1
1
1
1
1
7
.
25
45
57
54
69
45
76
55
80
1
6
1
6
1
1
1
1
1
1
1
1
1
.
34
47
46
52
21
53
32
61
1
6
1
1
1
1
1
1
1
2
1
1
1
1
.
15
79
80
45
70
25
34
1
6
1
1
1
1
1
1
1
2
1
1
1
1
7
.
94
95
60
84
38
35
1
6
1
1
1
1
1
1
1
7
1
1
1
1
6
7
.
24
37
48
66
99
1
5
3
6
1
1
1
1
1
1
1
1
1
1
4
4
2
.
35
27
61
91
1
5
1
1
1
1
3
1
7
1
7
6
6
5
1
1
1
1
.
32
29
61
1
2
4
7
1
1
2
2
4
1
3
2
2
3
3
2
1
1
1
.
46
72
1
1
1
1
1
1
2
3
2
1
2
2
2
1
2
1
1
1
1
1
.
32
3
4
3
1
5
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
3
.
valor deste vetor indica que o departamento 14 (quatorze) está na posição 1 (um), o
segundo valor indica que o departamento 16 (dezesseis) está na posição 2 (dois)e assim
sucessivamente até a posição 22 (vinte e dois).Ver figura 4.9.
Figura 4.8: Arranjo obtido com a Rede Neural MLP
4.5
Análise dos resultados
4.5
59
Análise dos resultados
4.5.1
Introdução
Para fins de comparação de resultados, foram desenvolvidos um algoritmo exato
baseado em matrizes de permutação, rede neural MLP e algoritmo Branch and Bound.
As heurísticas SDPI e Colônia de Formigas foram extraídas de bibliografia sobre o
assunto.
Os testes realizados tiveram como objetivo obter resultados comparativos nas
instâncias apresentadas.
4.5.2
Experimento
Para treinamento da rede neural MLP, várias simulações foram realizadas, alterando, em cada uma delas, o número de camadas intermediárias, a quantidade de
neurônios destas camadas e o algoritmo de treinamento. A configuração final resultante, 2 camadas intermediárias, 5 neurônios, e algoritmo Levenberg Marquardt para
treinamento, responderam adequadamente às expectativas.
As dimensões das matrizes de entrada foram reduzidadas eliminando valores
repetidos face à simetria dos seus dados. Com isto, evitou-se a redundância desnecessária,
tão prejudicial ao treinamento da rede neural. Este procedimento foi responsável pelo
decréscimo no tempo de treinamento e estabilidade na convergência.
O conjunto de dados formados pelas matrizes de entrada deve ser suficiente para
treinamento da rede neural. Com isto, foi necessário formar um banco de dados para
esta finalidade, já que o volume de dados na literatura é insuficiente. Com base em um
gerador randômico de matrizes, para n = 22 , a heurística SDPI construiu 100 (cem)
vetores de saída para a rede neural . Sendo assim, dividiu-se este conjunto em quatro
partes iguais, cabendo duas delas para o treinamento da rede e as duas restantes para
teste e validação, respectivamente.
4.5.3
Resultados Obtidos e Limitações
Para as instâncias até n = 9, os algoritmos exatos e Branch and Bound demonstraram-se eficientes no resultado da função objetivo, garantindo, em tempo aceitável,
4.6
Análise
60
o ótimo local. Mas, para instâncias maiores do que 15, estes dois algoritmos não apresentaram desempenho viável: tempo de processamento muito alto com a plataforma
utilizada.
Para o caso específico em estudo, n = 22 , os algoritmos exatos não foram capazes
de resolver. A rede neural, treinada com base na Heurística SDPI, forneceu vetor de
saída (22 × 1) com valores não inteiros pertencentes ao intervalo [1, 22]
4.6
Análise
O vetor de saída desejado, em comparação com o vetor de saída real, apresentou
diferenças em relação aos valores absolutos deste último. Isto se deve a não convergência
absoluta da rede. A interpretação da resposta dada pela rede foi fator importante no
resultado final. Os valores esperados são inteiros e pertencem ao intervalo [1, 22], logo
foi preciso ajustar a saída da rede com base nestes valores (ver figura 4.9).
Figura 4.9: Vetor Saída Rede Neural
Com relação ao PQA exato, foram testadas todas as possibildades de disposição
dos departamentos. Este algoritmo somente obteve respostas para instâncias até n = 9,
com tempo de processamento 314 minutos, sendo este tempo alterado a cada simulação
4.7
Análise
61
Tabela 4.6: Comparação dos Resultados
Número de Departamentos (n)
Rna MLP
Branch and Bound
QAP Exato
SDPI
4
7
9
15
22
VFO
208393
194230
379782
4203
32040
ITER
7
10
12
11
11
TEMPO(s)
2,35
2,29
3,16
2,76
3,27
VFO
203711
189152
357163
-
-
ITER
9
1210
5230
-
-
TEMPO(s)
0,34
0,63
111,05
-
-
VFO
234015
192312
359276
4198
31215
ITER
1000
1000
10000
10000
100000
TEMPO(s)
0,87
1,02
1,01
67,58
197,34
VFO
203711
189152
357163
-
-
ITER
24
5040
362880
-
-
TEMPO(s)
1,38
2,41
1864,68
-
-
VFO
237615
198030
357163
4219
50030
ITER
86
70
64
110
120
TEMPO(s)
0,52
0,41
0,43
3,71
12,71
em virtude da aleatoriedade das matrizes de entrada usadas. Para valores maiores do
que nove, não se consegue obter qualquer resposta, face à capacidade de processamento
da plataforma utilizada.
O algoritmo Branch and Bound, com auxílio da função Bintprog do MatLab,
resolveu instância até n = 13 em 22, 7 minutos. Não foi possível resolver para instâncias
maiores, mesmo alterando o limite inferior para valores próximos àqueles encontrados
pela rede neural.
Com o uso do algoritmo baseado em colônia de formigas, o valor da função objetivo de 31215 atendeu às necessidades do projeto obtendo redução no custo de transporte em comparação com o arranjo físico inicial. Tempo de processamento de 6, 3
minutos foi aceitável em comparação com os outros algoritmos.
4.7
Análise
4.7
62
Conclusão
Neste capítulo foi apresentado o modelo matemático para o problema proposto
com base no PQA. As variáveis de interesse foram definidas de acordo com o estudo de
caso proposto, ou seja, arranjo físico em uma fábrica de embalagem com vinte e dois
departamentos.
Foi desenvolvido um exemplo para n = 4 departamentos para esclarecer a lógica
utilizada pelo algoritmo Branch and Bound, utilizando a toolbox do Software MaTlab
especificamente a função Bintprog. Algoritmo exato foi desenvolvido produzindo resultados exatos até para n = 9 departamentos, a partir deste valor não foi possível
obter resultados com a plataforma utilizada. (Pentium IV, 2.8 GHz, 512 Mb memória
RAM).
O uso de Rede Neural MLP, teve como banco de dados para o seu treinamento,
validação e teste, dados gerados pela heurística SDPI. Esta heurística forneceu à rede
neural cem matrizes 22 × 22 (matrizes de distâncias e fluxo), bem como os vetores
resposta desejados que serviram de suporte ao algoritmo Backpropagation e LevenbergMarquardt.
Capítulo 5
Conclusão Geral e Trabalhos Futuros
Para se resolver problemas combinatoriais, em primeiro lugar deve-se verificar
a dimensão do espaço solução, para se definir a melhor ferramenta para resolusão do
problema. No caso de otimização de arranjo físico, o número de departamentos (n) a
serem alocados serve de parâmetro para escolha do algoritmo adequado.
Para valores de n <10 , algoritmos com base na enumeração completa do espaço
solução poderá ser utilizado em tempo aceitável. Para valores de n menores do que
15(quinze), o algoritmo Branch and Bound é aplicável, retornando solução ótima para
o problema. Mas, no estudo realizado, com n =22 departamentos, o uso de heurística
é o aconselhável, já que o número de possibilidades de solução torna desaconselhável
o uso de algoritmos exatos. A solução procurada é um ótimo local, que atenda às
necessidades do projeto.
Redes Neurais apresentam-se como ferramentas promissoras para situações que
envolvem a indústria, onde se encontra o mesmo problema que deverá ser resolvido
várias vezes, alterando apenas algumas situações de contorno.
A escolha de uma rede neural MLP esbarrou na limitação de dados históricos
que servissem de suporte para treinamento da rede, já que deve-se ensiná-la com base
em exemplos. Apesar do treinamento ter como base um banco de dados gerado pela
heurística SDPI, o resultado foi satisfatório, garantindo melhor custo em relação ao
arranjo físico inicial. Isto demonstra que o treinamento da rede neural não se preocupou
com os valores absolutos dos dados apresentados a ela e, sim, com as características
destes dados.
63
5.0
Conclusão
64
A arquitetura da rede neural é tão importante quanto a base de dados que ela
utiliza para treinamento e ainda de como esta base de dados é apresentada para a rede.
A simplificação deste conjunto de dados, normalizando-os e aproveitando a simetria das
matrizes, foi fator importante no tempo e na qualidade do treinamento. A comparação,
em um mesmo gráfico, do treinamento, da validação e do teste permitiu acompanhar o
progresso do treinamento. Com base neste gráfico, pode-se concluir que o resultado é
aceitável, já que os erros do teste e da validação têm comportamentos similares e não
existe nenhum sinal de overfitting. O importante a ser ressaltado é a resposta obtida
pela rede neural em comparação com os outros algoritmos, mesmo sendo treinada com
dados não exatos, conseguiu-se bons resultados.
Também foi verificado que a implementação de camadas intermediárias, com
o objetivo de diminuir o tempo de treinamento e aumentar o aprendizado da rede,
obteve sucesso, já que o arranjo físico resultante atendeu às necessidades da unidade
de negócio, oferecendo diminuição nos custos operacionais e agregando valor ao produto
final.
Já o desempenho dos algoritmos exatos, enumerativos ou não, ficam comprometidos, à medida que o valor de n cresce.
Para desenvolvimento de trabalhos futuros, novas arquiteturas de redes neurais
poderão ser aplicadas, combinando com algoritmos evolutivos, para se tentar melhorar,
ainda mais, a qualidade do arranjo físico final.
Apêndice A
Implementações MaTlab
A.1
Código para algoritmo Branch and Bound
Matrizcusto =
c = Matrizcusto(:);














2
18
14
6
22
10



70 30 110 50 


8 72 56 24 88 40 


4 36 28 12 44 20 


12 108 84 36 132 60 

6 54 42 18 66 30
10
90
(A.1)
A primeira restrição do problema obriga cada departamento ocupar somente um
lugar. A soma dos valores dos vetores xi correspondente à um departamento deverá
ser um.
numLocais = 6;
numDep = 6;
numDim = numLocais * numDep;
onesvector = ones(1,numLocais);
Aeq = blkdiag(onesvector,onesvector,onesvector,onesvector, onesvector,onesvector);
beq = ones(numDep,1);
A segundo grupo de restrições obriga cada local ter um e somente um departamento.
e = eye(1,numLocais);
65
A.1
Apêndice: Implementações MaTlab
66
A = repmat(e,numLocais,numDep);
for i = 2:6
A(i,:) = circshift(A(i-1,:),[0,1]);
end
b = ones(numLocais,1);
O terceiro grupo de restricões faz referência às arestas não adjcentes mencionadas
anteriormente. Em primeiro lugar a matriz de pesos D é criada tomando como base a
posição relativa entre os locais. Aqueles próximos atribui-se a unidade, e aqueles que
não estão próximos, valores maiores que a unidade.
D = zeros(numLocais);
D(1,2:end) = [1 5 5 5 5 ];
D(2,3:end) = [1 5 1 5 ];
D(3,4:end) = [1 5 1 ];
D(4,5:end) = [5 5]; D(5,end) =1;
D = triu(D)’ + D;
Com esta rotina impomos que as arestas não adjacentes não poderão ser vizinhas.
[localA,localB]= find(D < 2);
numPares = length(localA) numlinhas = 2*numPares + numLocais;
A((numLocais+1):numlinhas, 1:numDim) = zeros(2*numPares,numDim);
for i = 1:numPares
A23 = 2;
A14 = 4;
A23NolocalA = sub2ind([numLocais numDep],localA(i),A23);
A14NolocalB = sub2ind([numLocais numDep],localB(i),A14);
A(i+numPares+numLocais, [A23NolocalA, A14NolocalB]) = 1;
A12 = 1;
A34 = 3;
A(i+numPares+numLocais, [A12NolocalA, A34NolocalB]) = 1;
A24 = 6;
A13 = 5;
A.2
67
A(i+numLocais, [A24NolocalA, A13NolocalB]) = 1;
end
b(numLocais+1:numLocais+2*numPares) = ones(2*numPares,1); x0 =[];
Utilização da Toolbox BINTPROG, Matlab, para determinação do custo mínimo.
f = c;
options = optimset(’Display’,’iter’,’NodeDisplayInterval’,1);
[x,fval,exitflag,output] = bintprog(f,A,b,Aeq,beq,x0,options);
fval exitflag output ;
options = optimset(options,’BranchStrategy’,’mininfeas’);
fval exitflag output;
options = optimset(options,’NodeSearchStrategy’,’df’);
fval exitflag output;
A.2
Gerador de Matrizes
%-------------------------------------------------------%Gerador das Matrizes de Entrada para heurística SDPI
%-------------------------------------------------------%Gera 100 vetores de entrada
for zz=i:100
%Número de Departamentos
n=22
%Matriz Fluxo Assimétrica
mrf=randint(n,n,[0,100]);
%Matriz Distância Assimétrica
A.3
68
mrd=randint(n,n,[1,100]);
%Preparação das Matrizes Simétricas.
t=mrf+mrf’; u=mrd+mrd’; v=tril(t,-1); x=triu(t,1);
%Matriz Fluxo
W=v+x; g=tril(u,-1); h=triu(u,1);
%Matriz Distância
D=g+h; end
A.3
SDPI(Steepest Descent Pairwise Interchange)
%*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.
%Com base nas matrizes fluxo e distância, esta rotina calcula o vetor
%saída de posição dos departamentos.
%*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.
function [TCout,aout] = sdpi(W,D)
%SDPI Steepest Descent Pairwise Interchange para QAP.
% [TC,a] = sdpi(W,D)
%
m = número de localizações
%
W = m x m matriz fluxo
%
D = m x m mmatriz distância
%
a = vetor permutação randômico inicial
%*********************************************************************
%Verificação de erros
error(nargchk(2,5,nargin));
if nargin < 3 || isempty(a0), a0 = 1; end if nargin < 4, C = [];
end if nargin < 5, XY = []; end
A.3
69
[m,cW] = size(W); [rD,cD] = size(D);
if length(a0(:)) == 1, nruns = a0; a0 = []; else nruns = 1; end
if m ~= cW
error(’W deve ser matriz quadrada’)
elseif rD ~= cD
error(’D deve ser matriz quadrada’)
elseif m ~= rD
error(’W e D devem ter a mesma dimensão’)
elseif ~isempty(a0) && (length(a0(:)) ~= m || any(sort(a0) ~=
1:m))
error(’a0 não é um vetor permutação factível’)
elseif ~isempty(C) && any(size(C) ~= [m m])
error(’C deve ter dimensão m x m’)
elseif ~isempty(XY) && any(size(XY) ~= [m 2])
error(’XY deve ter dimensão m x 2’)
end
%************************************************************************
TC = Inf;
if ~isempty(XY)
sdpiplot(XY), title(’’), pauseplot(Inf)
defpause = 1;
end
if nargout == 0 && nruns > 1, disp(’ ’), end
for k = 1:nruns
TC0 = Inf;
A.3
70
if isempty(a0), ak = randperm(m); else ak = a0; end
TCk = sum(sum(W(ak,ak).*D));
%TC Inicial
if (nargout == 0 || ~isempty(XY)) && nruns == 1
if isint(TCk), s = ’d’; else s = ’f’; end
str1 = sprintf([’TC inicial = %’ s],TCk);
str2 = [’
a =’ sprintf(’ %d’,ak)];
if nargout == 0, fprintf(’\n%s\n%s\n’,str1,str2), end
if ~isempty(XY)
sdpiplot(XY,W,ak), title(str1), pauseplot(defpause)
end
end
while TCk < TC0
TC0 = TCk;
a0k = ak;
for i = 1:m-1
for j = i+1:m
aij = a0k;
aij([j i]) = aij([i j]);
if isempty(C)
TCij = sum(sum(W(aij,aij).*D));
else
D = D + diag(diag(ones(m)));
TCij = sum(sum((W(aij,aij) + diag(diag(C(aij,:)))) .* D));
end
if TCij < TCk
TCk = TCij;
ak = aij;
ik = i; jk = j;
end
A.3
71
end
end
if ~isequal(a0k,ak)
if (nargout == 0 || ~isempty(XY)) && nruns == 1
str1 = sprintf([’Troca %d and %d: TC = %’ s],jk,ik,TCk);
str2 = [’
a =’ sprintf(’ %d’,ak)];
if nargout == 0, fprintf(’%s\n%s\n’,str1,str2), end
if ~isempty(XY)
sdpiplot(XY,W,ak), title(str1), pauseplot(defpause)
end
end
if TCk < TC && nruns > 1 && ~isempty(XY)
sdpiplot(XY,W,ak)
title([’Min TC = ’,num2str(TCk)])
pauseplot(defpause)
end
end
end
if nargout == 0
if nruns == 1
disp([sprintf([’
TC Final = %’ s ’\n
a =’],TCk) ...
sprintf(’ %d’,ak)])
disp(’ ’)
else
disp([sprintf([’Run %d: Min TC = %’ s ’\n
k,TCk) sprintf(’ %d’,ak)])
TCsave(k) = TCk;
a = ’],...
A.4
72
end
end
if TCk < TC
TC = TCk
a = ak;
end
end
if nargout == 0 && nruns > 1
nTC = sum(TCsave == TC);
TCpercent = round(100*(nTC/nruns));
if isint(TC), s = ’d’; else s = ’f’; end
disp([sprintf([’\nMin TC = %’ s ...
’
(Found in %d of %d runs (%d%%))\n
a =’], ...
TC,nTC,nruns,TCpercent) sprintf(’ %d’,a)]), disp(’ ’)
end if nargout > 0
TCout = TC;
aout = a;
end
A.4
% Ant Algorithm for the Quadratic Assignment Problem
% By Kyriakos Tsourapas
% You may contact me through the Mathworks site
% University of Essex 2002
clc; clear; disp(’Please wait...’); disp(’ ’);
ENTRA COM AS MATRIZES FLUXO E DISTÂNCIA.
A.4
pr_size = size(DF, 1);
ants = 5; % NUMBER OF ANTS
max_assigns = 10000; % NUMBER OF ASSIGNMENTS (WHEN TO STOP)
optimal = 107; % OPTIMAL SOLUTION
a = 1; % WEIGHT OF PHEROMONE
b = 5; % WEIGHT OF HEURISTIC INFO
lamda = 0.8; % EVAPORATION PARAMETER
Q = 10;
% CONSTANT FOR PHEROMONE UPDATING
AM = ones(ants,pr_size); % ASSIGNMENTS OF EACH ANT
min_cost = -1;
% HEURISTIC INFO - SUM OF DISTANCES BETWEEN SITES
for i=1:pr_size
D(i) = sum( DF(1:i-1,i) ) + sum( DF(i,i+1:pr_size) );
end
% START THE ALGORITHM
assign = 1; while (assign <= max_assigns) & ( (min_cost > optimal)
| (min_cost == -1) )
% =============== FIND PHEROMONE ===============
% AT FIRST LOOP, INITIALIZE PHEROMONE
if assign==1
% SET 1 AS INITIAL PHEROMONE
pher = ones(22);
% IN THE REST OF LOOPS, COMPUTE PHEROMONE
else
for i=1:pr_size
for j=1:pr_size
73
A.4
tmp = zeros(ants,pr_size);
tmp( find(AM==j)) = 1;
tmp = tmp(:,i);
tmp = tmp .* costs’;
tmp( find(tmp==0) ) = [];
tmp = Q ./ tmp;
delta(i,j) = sum(tmp);
end
end
pher = lamda * pher + delta;
end
% ============ ASSIGN DEPTS TO SITES ============
% EACH ANT MAKES ASSIGNMENTS
for ant=1:ants
% GET RANDOM DEPT ORDER
depts = rand(pr_size, 2);
for i=1:pr_size
depts(i,1) = i;
end
depts = sortrows(depts,2);
% KEEP AVAILABLE SITES IN A VECTOR
for i=1:pr_size
free_sites(i) = i;
end
pref = ones(pr_size,1); % PREFERENCE FOR EACH SITE
prob = ones(pr_size,1); % PROBABILITIES FOR EACH DEPT
for dept_index=1:pr_size
% GET SUM OF THE PREFERENCES
74
A.4
75
% AND THE PREFERENCE FOR EACH SITE
pref_sum = 0;
for site_index=1:size(free_sites,2)
tmp_pher = pher(depts(dept_index), free_sites(site_index));
pref(site_index) = tmp_pher^a * ( 1/D(free_sites(site_index)) )^b;
pref_sum = pref_sum + pref(site_index);
end
% GET PROBABILITIES OF ASSIGNING THE DEPT
% TO EACH FREE SITE
prob = free_sites’;
prob(:,2) = pref / pref_sum;
% GET THE SITE WHERE THE DEPT WILL BE ASSIGNED
prob = sortrows(prob,2);
AM(ant,dept_index) = prob(1);
% ELIMINATE THE SELECTED SITE FROM THE FREE SITES
index = find(free_sites==prob(1));
prob(1,:) = [];
free_sites(index) = [];
pref(index) = [];
end
% GET THE COST OF THE ANT’S ASSIGNMENT
costs(ant) = 0;
for i=1:pr_size
for j=1:i-1
dept_flow = DF(i,j);
site1 = AM(ant,i);
site2 = AM(ant,j);
if site1 < site2
A.5
sites_distance = DF(site1, site2);
else
sites_distance = DF(site2, site1);
end
costs(ant) = costs(ant) + dept_flow * sites_distance;
end
end
if (costs(ant) < min_cost) | (min_cost == -1)
min_cost = costs(ant);
ch_assign = AM(ant,:);
end
if mod(assign,100) == 0
end
assign = assign + 1;
end
end
clc;
disp( sprintf(’Cheapest Cost : %d’, min_cost));
disp( sprintf(’Assignments
: %d’, assign-1));
disp(’ ’); disp(’Assignment’); disp(’----------’); ant_index =
find(costs==min(costs)); for i=1:pr_size
disp( sprintf(’Dept %d to Site %d’, i, ch_assign(i)));
end
A.5
Algoritmo Exato
tic
n=9%Número de Departamentos
mrf=randint(n,n,[0,100]);%Matriz Fluxo Assimétrica
76
A.5
mrd=randint(n,n,[1,100]);%Matriz Distância Assimétrica
%Preparação das Matrizes Simétricas.
t=mrf+mrf’; u=mrd+mrd’; v=tril(t,-1); x=triu(t,1); W=v+x;
g=tril(u,-1); h=triu(u,1); D=g+h; for c=1:10
mf=W;
md=D;
end custoi=inf; perm=perms(1:n); for p=1:factorial(n)
b=perm(p,:);
mfp=mf([b],[b]);
mcp=mfp.*md;
custo(p)=sum(mcp(:))/2;
if custo(p)<custoi
custoi=custo(p);
end
end vfo=custoi; ind=find(custo==custoi); vr=perm(ind,:);
[l,z]=size(vr); for r=1:l
s=vr(r,:);
mfp=mf([s],[s]);
vr;
mf;
md;
mfp;
end q=0; i=0; j=0; for j=1:n
for i=1:n
if i>j
q=q+1;
f(q,1)=mf(i,j);
d(q,1)=md(i,j);
fp(q,1)=mfp(i,j);
end
end
end
77
A.5
mc=f*d’
mctp=fp*d’
mru=zeros(n);
z=0;
for z=1:n
mru(vr(z),z)=1;
end; mru vr vfo toc
78
Bibliografia
[1] A.P.Braga, André P.L.F de Carvalho, Tereza Bernada Ludermir Redes Neurais
Artificiais. Teoria e Aplicações (2000)
[2] Anderson Henrique Barbosa; Marcílio Sousa da Rocha Freitas; Francisco de Assis
das Neves, Confiabilidade estrutural utilizando o método de Monte Carlo e
redes neurais Revista Escola de Minas Print ISSN 0370-4467,(2005)
[3] APPLE, J. M.; DEISENROTH, M. P A computerized plant layout Analysis and
evaluation technique (PLANET). Proceedings of the 23rd Annual Conference
and Convention, AIIE. California, p. 121-127,(1972)
[4] Armour, G.C. e Buffa, E.S. Heuristic algorithm and simulation approach to relative
location of facilities. Management Science, 9(2), 294-309.(1963)
[5] AZADIVAR, F.; WANG, J. Facility layout optimization using simulation and genetic algorithms. International Journal of Production Research, v. 38, n. 17,
p. 4369-4383(2000)
[6] BAZARAA, M. S Computerized layout design: a branch and bound approach. AIIE
Transactions, v. 7, n. 4, p. 432-437(1975)
[7] Bazaraa, M.S. & Kirca, O. A branch-and-bound based heuristic for solving the
quadratic assignment problem Naval Research Logistics Quarterly, 30, 287304.,(1983)
[8] Bos, J. A quadratic assignment problem solved by simulated annealing.Journal of
Environmental Management, 37(2), 127-145.,(1993)
[9] Christofides, N. & Benavent, E. An exact algorithm for the quadratic assignment
problem Operation Research, 37(5), 760-768.,(1989)
79
Bibliografia
80
[10] Cung,V.D A scatter search based approach for the quadratic assignment problem
IEEE international Conference on Evolutionary Computation,165-169.(1997)
[11] G.Cybenko. Aproximation by superpositions of a sigmoidal function.Mathematics
of Control, Signal and Systems,2:303-314.(1989)
[12] Edwards,C.S The derivationof a greedy aproximator for a Koopmans Beckman
quadratic assignment problemProceedings of 77-th Combinatorial Programming Conference(CP77),55-86.(1977)
[13] Elshafei, A.N. Hospital layout as a quadratic assignment problem. Operations
Research Quarterly, 28(1), 167-179.,(1977)
[14] Fedjki, C.A. & Duffuaa, S.O. An extreme point algorithm for a local minimum
solution to the quadratic assignment problem. Operational Research, 156(3),
566-578.,(2004)
[15] Robinson, D.F and Foulds, L Comparison of phylogenetics treesMathematical Biosciences, 53:131-147,(1981)
[16] Gidas, B., Ni, W. M. e Nirenberg, L., Symmetry and related properties via the
maximum principle, Comm. Math. Phys., 68, 209-243 (1979).
[17] João Carlos Furtado e Luiz Antônio Nogueira Lorena OTIMIZAÇÃO EM PROBLEMAS DE LEIAUTE LAC/INPE - Instituto Nacional de Pesquisas Espaciais
(1997)
[18] Gavett, J.W. & Plyter, N.V. The optimal assignment of facilities to locations by
branch-and-bound. Operations Research, 14, 210-232.(1966)
[19] Valdair Candido MartinsI; Leandro dos Santos CoelhoII; Marco Antonio Barbosa
CândidoII; Ricardo Ferrari Pacheco Otimização de layouts industriais com base
em busca tabu doi: 10.1590/S0104-530X2003000100006,(2003)
[20] M. Gondran, M. Minoux. Graphes et Algorithmes. Collection des Études et
Recherches d´Électricité de France, Eds. Eyrolles, 1995.
[21] Hartman, P., “Ordinary Differential Equations”, Baltimore 369-402.
[22] Kusiak, A. and SS Heragu The Facility Layout Problem European Journal of ...
91-76, Faculty of Management, Laval University, Québec, Canada(1991)
Bibliografia
81
[23] Hiller, F.S and Michael, M.C Quadratic Assignment Problem algorithms and location of indivisible facilities. Manegement Science,13,44-57,(1966)
[24] Hassan, M. M. D. Machine Layout Problem in Modern Manufacturing Facilities
Int. J. of Production Research, Vol. 32, no. 11, pp2559-2584,(nov 1994)
[25] Jünger, M. & Kaibel, V On the qap polytope. Technical Report 96.241, Angerwandte Mathematik und Informatik, Universität zu Köln.(1996a)
[26] Jünger, M. & Kaibel, V A basic study of the QAP polytope. Technical Report
96.215, Angerwandte Mathematik und Informatik, Universität zu Köln.(1996b)
[27] Jünger, M. & Kaibel, V The qap-polytope and the star transformation. Discrete
Applied Mathematics, 111(3), 283-306.(2001)
[28] Koopmans, T.C and Beckman, M.J Assignment problens and the location of economic activities Econometrica, 25,53-76.
[29] Karisch,S.E Trust regions and relaxations for the quadratic assignment problem
Series in Discrete Mathematics and Theoretical Computer Science, 16,199-219,
AMS,Rhode Island.(1994)
[30] Kaku, B.K. & Thompson, G.L. An exact algorithm for the general quadratic
assignment problem. European Journal of Operational Research, 2, 382390.(1986)
[31] Andrew KUSIAK and Sunderesh S. HERAGU The facility layout problem Department of Mechanical and Industrial Engineering, University of Manitoba,
Winnipeg, Manitoba, Canada R3T2N2,(1987)
[32] Lawer, E.L The quadratic assignment problem Management Science, 9, 586599.(1963)
[33] LEE, R. C.; MOORE, J. M. computerized relationship layout planning Industrial
Engineering, v. 18, p. 195-200,(1967)
[34] Leandro dos Santos Coelho & Roberto Fernandes Tavares Neto Colônia de Formigas: Uma Abordagem Promissora para Aplicações de Atribuição Quadrática
e Projeto de Layout XXIV ENEGEP Florianópolis, SC, Brasil, 03 a 05 de
novembro de 2004
Bibliografia
82
[35] Liang, Y. Combinatorial optimization by Hopfield networks using adjusting neurons. Information Sciences, 94(1-4), 261-276.,(1996)
[36] Chu, L.K., Facilities Design Layout Analysis, The University of Hong
Kong, Department of Industrial and Manufacturing Systems Engineering,September,
(2005),
em http://http://www.imse.hku.hk/lkchu/IEIM-
download/BEng-MFA.pdf.
[37] Eliane Maria Loiola, Nair Maria Maia de Abreu, Paulo Oswaldo Boaventura Netto
it Uma revisão comentada das abordagens do problema quadrático de alocação
Pesquisa Operacional Print ISSN 0101-7438,(2004)
[38] Mans, B.; Mautor, T. & Roucairol, C. A parallel depth first search branch and
bound algorithm for the quadratic assignment problem. European Journal of
Operational Research, 81, 617-628.,(1995)
[39] W.S.McCulloch and W.Pitts. A Logical Clculus of the ideas immanent in nervous
activity. Bulletin of Mathematical Biophysics, 5:115-133.(1943)
[40] RD Meller and K.-Y. Gau. The facility layout problem: Recent trends and perspectives, J. of Manufacturing Systems, vol. 15, no. 5, pp. 351–366 (1996)
[41] MONTREUIL, B. A modeling framework for integrating layout design and flow
network design. Proceeding of the Material Handling Research Colloquium,
Hebron, KY, p. 43-58(1990)
[42] MONTREUIL, B.; VENKATADRI, U.; RATLIFF, H. D. Generating a layout
from a design skeleton. IIE Transactions, v. 25, n. 1, p. 3-15(1993)
[43] Nugent, C.E.; Vollmann, T.E. e Ruml, J.. An experimental comparison of techniques for the assignment of facilities to locations. Operations Research, 16,
150-173.(1968)
[44] Pierce,J.F and Crowston, W.B Tree-search algorithms for quadratic assignment
problem naval Reseach Logistics Quarterly,18,136.(1971)
[45] Rangel,M.C e Abreu,N.M.M Ordenações parciais nos conjuntosdas soluções dos
problemas de alocação linear e quadrático. Pesquisa Operacional,23(2),265-284
(2003).
Bibliografia
83
[46] D.E.Rumelhart, G.E Hinton, andR.J.Willians. Learning represetation by backpropagation erros. Nature,323:533-536.(1986)
[47] Savsar, M. , Effects of Random Material Flow Volumes on Layout Flexibility ,International Journal of Industrial Engineering ,Vol.12 ,pp.234-243 ,June ,(2005).
[48] SEEHOF, J. M.; EVANS, W. O.Automated layout design program. Industrial Engineering , v. 18, p. 690-695,(1967)
[49] Sérgio Haffner Técnicas de Otimização (94430-03) Introdução à Otimização em
Engenharia.
[50] Siu, F. & Chang, R.K.C Effectiveness of optimal node assignments in wavelength
division multiplexing networks with fixed regular virtual topologies. Computer
Networks, 38(1), 61-74.,(2002)
[51] S. Haykin, Neural Networks, 2nd ed ., Prentice Hall, Upper Saddle River, New
Jersey, (1999).
[52] A. H. Land e A. G. Doig, An automated method for solving discrete programming
problems, Econometrica, 28, 497-520, 1960.
[53] Steinberg, L.The backboard wiring problem: A placement algorithm. SIAM Review, 3, 37-50.(1961)
[54] KY Tam and SG Li A hierarchical approach to the facility layout problem Int. J.
of Production Research, vol. 29, no. 1, pp. 165–184(1991)
[55] Neural Network Toolbox User’s Guide Ó COPYRIGHT 1992 - 2000 by The MathWorks, Inc.
[56] TOMPIKINS, J. A.; REED Jr., R. An applied model for the facilities design
problem International Journal of Production Research, v. 14, n. 5, p. 583595(1976).
[57] John A.White Facilities Planning ISBN:0471032999 (1984).
[58] Torki, A.; Yajima,Y. & Enkawa,T. A low-rank bilinear programming approach for
sub-optimal solution of the quadratic assignment problem. European Journal
of Operational Research, 94(2), 384-391.,(1996).
Bibliografia
84
[59] Torres, Isaías Integração de ferramentas computacionais aplicadas ao projeto e desenvolvimento de arranjo físico de instalações industriais. São Carlos: UFSCar,
154p, 2001.
[60] Tsuchiya, K.; Bharitkar, S. & Takefuji, Y. A neural network approach to facility layout problems. European Journal of Operational Research, 89(3), 556563.,(1996)
[61] Tsuchiya, K.; Nishiyama, T. & Tsujita, K. A deterministic annealing algorithm
for a combinatorial optimization problem using replicator equations. Physica
D: Nonlinear Phenomena, 149(3), 161-173,(2001)
[62] Wolkowisz,H. Semidefinite programming aproaches to the quadratic assignment
problem Nonlinear Assignment Problem:Algorithms and Aplicationsedited by
P.M Pardalos and L.Pitsoulis, Combinatorial optimization Series,7,143-174,
Kluwer Academic Publishers,(2000b)
[63] Vollmann, T.E. Buffa, E.S. The Facilities Layout Problem in Perspective
[64] Yu, J. & Sarker, B.R. Directional decomposition heuristic for a linear machinecell location problem European Journal of Operational Research, 149(1), 142184.,(2003).
[65] Zhao,Q. Semidefinite programming relaxations for the quadratic assignment problem Journal Combinatorial Optimization,2,71-109.(1998)

- Modelagem Matemática e Computacional / CEFET-MG

Transcrição

Documentos relacionados

Apresentação

Lista 4

Ficha prática - Departamento de Engenharia Electrotécnica

Participação Qualificada

Minimum Spanning Tree Algoritmos de Prim e Kruskal Algoritmo de

restaurantes - Hotel da Cuia

asndt

Caminho mais curto a partir de um nó Algoritmos de Dijkstra e

Atualização de algoritmo da app Google Goggles

Modelos Neurais para Dispositivos Ativos Semicondutores de GaAs