XXX ENCONTRO NACIONAL DE ENGENHARIA DE PRODUÇÃO
Maturidade e desafios da Engenharia de Produção: competitividade das empresas, condições de trabalho, meio ambiente.
São Carlos, SP, Brasil, 12 a15 de outubro de 2010.
OTIMIZAÇÃO POR ENXAME DE
PARTÍCULAS APLICADA AO
PROBLEMA GERAL DE
DIMENSIONAMENTO DE LOTES E
PROGRAMAÇÃO DA PRODUÇÃO
Claudio Fabiano Motta Toledo (ufla)
[email protected]
Thiago Fialho de Queiroz Lafitá, (ufla)
[email protected]
Márcio da Silva Arantes (ufla)
[email protected]
Renato Resende Ribeiro de Oliveira (ufla)
[email protected]
Paulo Morelato França (unesp)
[email protected]
O presente artigo propõe um método baseado em Otimização por
Enxame de Partículas (OEP) associado à programação matemática
para resolução do Problema Geral de Dimensionamento de Lotes e
Programação da Produção (PGDLPP). A OEP fixa as variávveis
binárias do modelo enquanto um método exato é utilizado na
determinação das variáveis contínuas. O PGDLPP estudado também
considera penalização para demandas não atendidas, onde uma
formulação matemática é apresentada para essa variante do problema.
Instâncias são solucionadas por uma ferramenta de modelagem
matemática cujas soluções servem para avaliação do desempenho da
OEP proposta. A OEP também é comparada a um AG anteriormente
utilizado para resolver o mesmo problema. Os resultados revelam o
melhor desempenho obtido pela OEP proposta.
Palavras-chaves: Programação da Produção, Dimensionamento de
Lotes, Enxame de Partículas, Otimização
1. Introdução
O presente artigo propõe um método baseado em Otimização por Enxame de Partículas (OEP)
associado à programação matemática para resolução do Problema Geral de Dimensionamento
de Lotes e Programação da Produção (PGDLPP). A OEP fixa as variáveis binárias do modelo
enquanto um método exato é utilizado na determinação das variáveis contínuas. O PGDLPP
estudado também considera penalização para demandas não atendidas, onde uma formulação
matemática é apresentada para essa variante do problema. Instâncias são geradas para o
PGDLPP estudado seguindo os critérios propostos por Haase (1996) para o mesmo problema.
Todas as instâncias geradas são solucionadas usando a ferramenta de modelagem matemática
AMPL/CPLEX. As soluções obtidas servem como ponto de partida na avaliação de
desempenho da OEP proposta. Além disso, os resultados obtidos são comparados aqueles
encontrados pelo Algoritmo Genético com estrutura hierárquica de indivíduos proposto em
Toledo et al (2009) para o mesmo problema. Estudos considerando o PGDLPP com máquinas
paralelas são descritos em Kang et al. (1999) e Meyr (2002). O primeiro trabalho trata o
PGDLPP com máquinas paralelas usando um método baseado em geração de coluna e branch
& bound. O segundo trabalho utiliza a metaheurística simulated annealing para determinar as
variáveis binárias (atribuição de produtos às linhas e períodos) do PGDLPP e um algoritmo
exato para determinar as variáveis contínuas (dimensionamento de lotes e definição dos
estoques). O dimensionamento de lote e a programação da produção com restrição de
capacidade é um problema de otimização NP–Difícil (BITRAN E YANASSE, 1982). O
problema de dimensionamento de lotes e programação da produção multi-item também é um
problema NP-Difícil (CHEN e THIZY, 1990). A complexidade desse problema faz com que
sejam propostas heurísticas ou metaheurísticas como método de resolução. Jans e Degraeve
(2007) apresentam uma revisão da literatura considerando o uso de metaheurística na
resolução de problemas de dimensionamento de lote e programação da produção.
A otimização por Enxame de Partícula (OEP) foi introduzida por Kennedy & Eberhart (1995)
que propuseram uma abordagem baseada no comportamento de enxames de abelhas,
cardumes de peixes ou bando de pássaros quando procuram por alimentos (CHEN, T. & CHI,
T., 2010). Ali e Kaelo (2008) e Siarry et al (2007) utilizam OEP na otimização de funções
multi-modais. Chen & Zhao (2009) propõe uma OEP adaptativa, onde o tamanho da
população varia segundo uma função do tipo escada. O método é aplicado na otimização de
funções e no treinamento de redes neurais. Algoritmos Genéticos (AG) são métodos de
computação evolutiva que simulam processos biológicos (Holland, 1975). Goren et al (2008)
apresenta uma revisão da literatura para problemas de dimensionamento de lotes considerando
o uso de Algoritmos Genéticos. Um algoritmo genético multi-populacional foi utilizado por
Toledo et al (2009) para solucionar o mesmo PGDLPP aqui apresentado. Os autores
utilizaram uma representação em árvore ternária, onde indivíduos são separados em clusters
com uma ordem de hierarquia entre os indivíduos. O AG proposto foi capaz de encontrar boas
soluções, obtendo melhor desempenho em instâncias do PGDLPP com máquinas paralelas. A
próxima seção descreve o modelo matemático para o PGLDPP estudado neste trabalho. A
Seção 3 apresenta a OEP proposta. Os resultados computacionais são descritos na Seção 4. As
conclusões obtidas neste trabalho estão na Seção 5.
2. Modelo matemático para o PGDLPP
Toledo et al (2009) apresentaram o modelo matemático para o PGDLPP considerando
máquinas paralelas e penalização das demandas não atendidas. Esse modelo será detalhado
2
nesta seção. A formulação proposta segue a modelagem descrita por Meyr (2002) para o
PGDLPP com máquinas paralelas. A principal diferença está na inserção de variáveis que
acumulam as demandas não atendidas para cada produto. Essas variáveis são incluídas na
equação de balanço de estoque no primeiro período de produção e também são penalizadas na
função objetivo do modelo.
O problema é modelado dividindo o horizonte de planejamento em T macro-períodos. Por sua
vez, cada macro-período t possui um número fixo de micro-períodos S. Um aspecto
interessante neste tipo de modelagem é que o tamanho de cada micro-período s varia de forma
proporcional ao tamanho do lote do produto a ele atribuído. Assim, as variáveis de
dimensionamento dos lotes e de atribuição de produtos às linhas e períodos estão indexadas
por produtos e micro-períodos. O modelo assume que um único produto é atribuído e
produzido em cada micro-período.
A Figura 1 apresenta um exemplo dessa situação, supondo três produtos e três microperíodos em cada macro-período em uma linha L1. O tamanho dos micro-períodos s1, s2, s3,
s4, s5 e s6 varia de forma proporcional à quantidade produzida. Por exemplo, o lote em s2 de
P2 é maior que o lote de P2 em s4 na Figura 1. Assim, os micro-períodos s1, s4 e s6 ocupam 1
unidade de tempo, s2 ocupa 2 unidades e s5 ocupa 3 unidades de tempo.
Macro-período 1
s1
P1
L1
0
s2
P2
1
Macro-período 2
s3
s5
s4
P1
3
5
s6
P1
P3
P2
6
9
10
Tempo
Figura 1 – Variação dos micro-períodos (Toledo et al, 2009).
Um total de J produtos e L linhas são considerados. Abaixo são listados os demais parâmetros
do problema

Ct:

TPl,j: Tempo de processamento do produto j na linha l.

Minj: Lote mínimo do produto j.

Hj:
Custo de estoque do produto j.

CTij:
Custo de troca do produto i para o produto j.

Dit:
Demanda do produto i no macro-período t.

Ij0:
Estoque inicial do produto j no início do horizonte de tempo.

Yl,j,0:
1, se o produto j está ajustado inicialmente para a linha l; 0 caso contrário.

M:
Penalização por unidade de demanda não atendida.
Capacidade em unidades de tempo disponível no macro-período t.
As variáveis do modelo são apresentadas a seguir:

Ijt ≥ 0: Estoque do produto j ao final do macro-período t.

qljs ≥ 0: Quantidade do produto j produzido no micro-período s da linha l.

q0j ≥ 0: Quantidade de demanda do produto j que não foi produzida.
3

yl,j,s : 1 Se o produto j é atribuído à linha l no micro-período s; 0 caso contrário.

zlijs ≥ 0: zlijs = 1 se há troca do produto i para j no micro-período s da linha l; zijs = 0,
caso contrário.
O modelo matemático para o PGLDPP com máquinas paralelas e penalização de demandas é
descrito a seguir:
A função objetivo minimiza os custos de estoque e os custos de troca envolvendo produtos.
Os custos de troca foram considerados como dependentes da sequência dos produtos, mas
independentes das linhas. As demandas não atendidas são acumuladas nas variáveis q0j e
penalizadas na função objetivo. O estoque de cada macro-período é determinado pelas
equações (2a) e (2b). Observe que a demanda não atendida é acumulada na equação de
balanço de estoque do primeiro período (2a). Isso permite que as demandas não atendidas nos
demais períodos continuem satisfazendo a restrição de balanço de estoque já que são
acumuladas em q0j. Considera-se que essas demandas foram produzidas em um período t=0
com capacidade ilimitada. A restrição (3) garante que a capacidade disponível dentro do
período t não seja violada. A capacidade disponível por macro-período é a mesma para todas
as linhas, mas cada linha pode ter diferentes tempos de processamento por produto (TPl,j). O
tamanho máximo do lote de um produto em um micro-período é dado pela restrição (4). Essa
restrição também impõe que nada seja produzido, caso não ocorra atribuição do produto ao
micro-período (yl,j,s = 0). A restrição (5) assegura que um lote mínimo será produzido
quando ocorre efetivamente a atribuição de um novo produto a um micro-período (yl,j,s = 1).
Por outro lado, se o mesmo produto é atribuído a dois micro-períodos consecutivos, não
necessariamente haverá produção na segunda atribuição. A equação (6) permite que somente
um produto seja produzido em um micro-período. As trocas de produtos são determinadas
pela restrição (7).
3 Otimização por Enxame de Partícula
3.1 Representação das soluções
A representação utilizada é a mesma proposta por Toledo et al (2009) para o Algoritmo
Genético (AG). Trata-se de uma extensão para máquinas paralelas da representação proposta
em Fleischmann e Meyr (1997) para o PGDLPP com uma única máquina. Essa representação
consiste em uma lista de máquinas ou linhas de produção, onde cada linha armazena uma
4
matriz com informações sobre sua seqüência de produtos. Trata-se de uma matriz do tipo t x
n, onde t é o número de macro-períodos e n é o número de micro-períodos (Figura 2).
Figura 2 – Matriz de seqüência.
Cada entrada (t,n) corresponde ao produto que ocupa determinado micro-período dentro de
um macro-período. Duas entradas consecutivas não podem ser ocupadas pelo mesmo produto.
A única exceção ocorre para a última entrada de um macro-período e a primeira entrada do
macro-período seguinte que podem ser idênticas. Também não pode haver uma entrada sem
produto entre duas entradas ocupadas em um mesmo macro-período. Suponha uma instância
do problema com duas linhas, quatro produtos e dois macro-períodos divididos em quatro
micro-períodos cada.
A Figura 3 exemplifica a representação de uma possível solução ou partícula na OEP
proposta. Observe que a linha L1 possui três produtos alocados no macro-período T1 e dois
alocados em T2. A ordem dos produtos em cada período representa a sequência em que serão
produzidos. Na linha L2, um único produto será produzido em T1 e três produtos em T2.
Figura 3 – Exemplo da representação da solução.
3.2 Decodficação da representação da solução.
A avaliação de uma solução consiste no cálculo do valor da função objetivo (equação 1)
apresentada na seção 2. Esse processo exige a determinação dos custos de troca, estoque e a
penalização por demanda não atendida. Os custos de troca são calculados a partir da
sequência de produtos existentes em cada linha na representação da solução. Os custos de
estoque e a penalidade por demanda não atendida exigem a determinação do
dimencionamento dos lotes a partir das informações codificadas na representação da solução.
Esse dimensionamento é feito através do método apresentado no pseudocódigo a seguir
(Figura 4). Esse método é baseado no algoritmo greedy-mod proposto em Fleischmann &
Meyr (1997) para o PGDLPP com máquinas simples. O método de decodificação é
determinístico e define o tamanho dos lotes, minimizando o custo de estoque. Os parâmetros
do algoritmo são descritos abaixo:
 Xljt - armazena o lote do produto j produzido na linha l no macro-período t.
 Yljt - número de lotes do produto j no macro-período t na linha l.
5
 Dj – demanda acumulada (total) do produto j.
 ACjt - demanda acumulada do produto j até o macro-periodo anterior ao t.
 LSjt - limite superior estimado considerando que toda a capacidade disponível fosse
utilizada para produzir o produto j em períodos anteriores ao t.
para t=1 e
para t>1
 Xljs – lote do produto j produzido na linha l no micro-período s.
 Qj – quantia de demanda do produto j não alocada pelo metodo de decodificação.
Método de dimensionamento de lotes
t=T
Enquanto (t≥1) faça
//-----Garantindo lote mínimo-----Para toda linha l
Para todo produto com (Yljt>0)
p = Mínimo( Minj * Yljt ; Dj - ACjt );
Atualiza Xljt, Klt, Dj;
Se Klt < 0 então Penalizar capacidade violada
//Calcula a parcela a ser produzida
//-----Evitando infactibilidades-------------Para todo produto j
Q = Dj - LSjt;
Para toda linha l com (Yljt>0 e Q > 0)
p = Mínimo( Dj - ACjt ; Klt/TPlj ; Q );
Atualiza Xljt, Klt, Dj;
//------Distribui em uma ordem gulosa----Para toda linha l e produto j com (Yljt > 0 ) em ordem decrecente de Hj/TPlj
p = Mínimo( Dj - ACjt ; Klt/TPlj );
Atualiza Xljt, Klt, Dj;
t = t-1
fim Enquanto
Qj = Dj, para todo j.
//----Distribui as demandas dos macro-período para os micro-períodos----Para todo l,j,t e s pertencente a St
Se Yljt > 0 então
Xljs = Xljt / Yljt;
Senão
Xljs = 0;
fim do método.
Figura 4 – Pseudo-código Método de Decodificação.
O algoritmo trabalha preenchendo as quantias dos lotes em ordem decrescente de macroperíodo. Primeiro aloca o lote mínimo para os produtos atribuídos a micro-períodos na matriz
de sequência das linhas. Em seguida, dimensiona os lotes para produtos que, se não forem
produzidos no macro-período corrente, não haverá capacidade disponível para sua produção
ou o produto não aparecerá em outra posição na matriz de sequência das linhas. O objetivo é
evitar infactibilidades. Por último, todos os produtos alocados na matriz de sequencia das
linhas têm seus lotes redimensionados, seguindo a ordem decrescente do quociente Hj/TPlj. A
Figura 5 abaixo demonstra como são atualizadas as quantias Xljt, Klt e Dj pela parcela p de
demanda que será produzida.
6
Atualiza Xljt, Klt, Dj dada uma parcela de demanda p calculada
Xljt = Xljt + p;
//Adiciona a parcela, a quantia a ser produzida
Klt = Klt - p * TPlj;
//Subtrai a capacidade para produzir a quantia p.
Dj = Dj - p;
//Nova demanda do produto que deverá ser atendida.
Figura 5 – Atualizar Xljt, Klt, Dj
3.3 Algoritmo OEP
A Figura 6 e 7 apresentam o pseudocódigos para a OEP proposta. Uma partícula pode assumir
diversas representações da solução durante a execução do método. Neste contexto, cada
representação da solução de uma partícula é a posição assumida por esta no espaço de busca.
No pseudocódigo, Pi é o conjunto com a posição (representação da solução) atual das
partículas i. Mi é o conjunto que armazena a melhor posição onde as partículas Pi já
estiveram. O pseudo-código força que essa melhor posição seja reinicializada após um certo
número de iterações. O objetivo é não ficar preso a uma mesma melhor posição durante todo
o código. Pg é a melhor posição alcançada pelo enxame de partículas. Prand é uma partícula
aleatória, que pode ser totalmente aleatória ou gerada pela recombinação de partículas
existentes através de mudanças aleatórias. Pesos(j) define a probabilidade de escolher a
partícula j para recombinação. A atualização dos pesos é dinâmica, ou seja, fica variando
entre um valor mínimo e máximo. Essa variação é ditada pelo parâmetro d(j) que determina a
quantia adicionada ou subtraída de Peso(j):
o PesoMáximo(j) ≥ Pesos(j) ≥ PesoMínimo(j)
OEP
Inicializa as particulas Pi, Mi.
Pg = Melhor(Pi);
Enquanto critério não for atingido
Escolhe um tipo Prand usada na recombinação.
Restarta Mi
Para cont=1 até 20
Pi = Ocila(Pi,Mi,Pg, Prand);
// para toda partícula
Atualiza Pg e Mi;
Atualiza os pesos(j) dos vetores de recombinação.
Fim OEP
Figura 6 – Pseudocódigo para OEP
Ocila(Pi)
m = Reconbinação(Pi, Mi, Pg, Prand);
//para toda partícula
Para cont = 1 até 40
aux = Reconbinação(Pi, Mi, Pg, Prand);
//para toda partícula
Se avaliação(aux) < avaliação (m)
//para toda partícula
m = aux;
//armazena partícula com melhor valor em Pi
Retorne m;
Fim Ocila
Figura 7 – Pseudocódigo para o método Oscila
Cada partícula oscila em torno de um ponto antes de efetuar um movimento. O objetivo é
garantir que seu próximo movimento tenha um ganho significativo ou garantir pelo menos
que o movimento não piore muito a posição atual da partícula. Para efetuar o movimento de
uma partícula, o método proposto utiliza uma recombinação envolvendo quatro vetores que
armazenam posições (representações da solução) de partículas. O primeiro vetor armazena a
posição atual das partículas (Pi), o segundo vetor armazena a melhor posição alcançada pelas
partículas (Mi), o terceiro vetor armazena a melhor posição já obtida por todo o enxame (Pg)
e o quarto vetor armazena uma posição aleatória (Prand). A recombinação gera novas
posições para as partículas baseada em sequências de produtos herdadas das representações
7
armazenadas nos quatro vetores (Figura 8). A seleção de qual vetor irá contribuir segue uma
probabilidade de escolha definida como:
Probabilidade de escolher o vetor j.
Recombinação(Pi, Mi, Pg, Prand)
Para cada partícula
Para cada linha-l
Para cada macro-periodo-t
Seleciona um vetor j de acordo com Probabilidade(j).
Preeche uma nova particula com a sequencia em l e t do vetor selecionado..
Atualiza particula em Pi com nova partícula;
Retorna Pi com partículas atualizadas.
Fim Recombinação
Figura 8 – Pseudocódigo para recombinação
Duas abordagens são propostas para execução da OEP. A primeira chamada OEP1 permite
que os valores dos pesos Pesos(j) variem no decorrer da execução do método. Para isso,
valores máximos e mínimos são ajustados para cada peso. Também são ajustados o valor
inicial dos pesos e a taxa de decréscimo ou acréscimo relacionada. Durante a execução, os
pesos irão aumentar ou diminuir sem ultrapassar os valores máximos e mínimos
estabelecidos. Na segunda abordagem chamada OEP2, não há variação dos pesos e o método
é executado com o valor inicialmente atribuído a cada Peso(j).
4. Resultados computacionais
Os testes computacionais foram executados em instâncias do PGDLPP com máquina simples
e máquinas paralelas. As instâncias são as mesmas definidas e solucionadas em Toledo et al
(2009). No PGDLPP com máquinas simples, os autores utilizaram um total de 4 conjuntos
com 10 instâncias cada com os parâmetros apresentados na Tabela 1. Os valores dos
parâmetros foram estabelecidos por Haase (1996) na resolução do PGDLPP com máquinas
simples, onde U(%) é a porcentagem de utilização da capacidade disponível. Todos os demais
parâmetros do problema também foram ajustados pelos mesmos valores utilizados por Haase
(1996): djt{0,1,...,100}, Hj=1,TP1j=1, CTij{100,...,200} para i≠j e CTij=0 para i=j,
M=10000 e Minj = 1. O modelo matemático da seção 2 e as instâncias geradas foram
codificados utilizando o pacote computacional AMPL e solucionados pelo solver CPLEX
11.0 com tempo de execução de 1 hora.
Conjuntos
S1
S2
S3
S4
Macro-Períodos (T)
6
6
5
5
Micro-Períodos (S)
4
4
4
5
Produtos (J)
4
4
4
5
Capacidade (Ct)
200
200
200
250
U(%)
80
90
90
90
Tabela 1 – Conjuntos de Instâncias para o PGDLPP com uma única máquina.
Os resultados obtidos pela OEP são comparados aos retornados pelo AMPL/CPLEX e pelo
Algoritmo Genético (AG) também apresentados em Toledo et al (2009). O AG foi executado
utilizando uma população com 13 indivíduos, 2,5 de taxa de crossover e 0,7 de taxa de
mutação. OEP1 foi executada com 30 partículas, onde o vetor com a posição atual foi
ajustado com peso inicial 0, taxa de crescimento 0,8 e limitante superior para o valor do peso
em 10. O vetor com a melhor posição da partícula recebeu peso inicial 90, taxa de decaimento
8
1,6 e limitante inferior 0. O vetor com a melhor posição de todo o enxame recebeu peso
inicial 0, taxa de crescimento 0,8 e limitante superior 80. O vetor aleatório recebeu valor
inicial 10 e era ajustado durante a execução de forma que a soma dos pesos resultasse em 100.
OEP2 foi executada todo o tempo com o mesmo valor inicial atribuído aos pesos da OEP1.
Todos os testes foram realizados em um processador Intel Corel 2 Duo, 2,66 GHz e 1,95 GB
RAM. As metaheurísticas executaram 10 vezes em cada uma das 10 instâncias de cada
conjunto. O tempo de execução por instância foi limitado a 0,5h, ou seja, metade do tempo
dado ao método exato. As Tabelas 2 e 3 apresentam os resultados para os quatro conjuntos de
instâncias do PGDLPP com máquinas simples.
S1
S1-0
AMPL
1658*
S1-1
1421*
S1-2
1700*
S1-3
1459*
S1-4
1543*
S1-5
1402*
S1-6
1477*
S1-7
1463*
S1-8
1480*
S1-9
1626*
AG
1658
0.0
1421
0.0
1700
0.0
1459
0.0
1551,4
0.5
1402
0.0
1486,5
0.6
1463
0.0
1487
0.5
1633,4
0.5
OEP1
1658
0.0
1421
0.0
1703
0.2
1471
0.8
1543
0.0
1402
0.0
1480
0.2
1463
0.0
1487
0.5
1628
0.1
OEP2
1658
0.0
1421
0.0
1703
0.2
1471
0.8
1543
0.0
1402
0.0
1480
0.2
1463
0.0
1487
0.5
1628
0.1
S2
S2-0
AMPL
1729*
S2-1
1758*
S2-2
2162*
S2-3
1747*
S2-4
1638*
S2-5
1534*
S2-6
1533*
S2-7
1822*
S2-8
1863*
S2-9
1751*
AG
1746
1.0
1758
0.0
2162
0.0
1748,2
0.1
1638
0.0
1534
0.0
1533
0.0
1833,8
0.6
1864,7
0.1
1751
0.0
OEP1
1729
0.0
1758
0.0
2162
0.0
1747
0.0
1638
0.0
1539
0.3
1533
0.0
1822
0.0
1863
0.0
1751
0.0
OEP2
1729
0.0
1758
0.0
2162
0.0
1747
0.0
1638
0.0
1539
0.3
1533
0.0
1822
0.0
1863
0.0
1751
0.0
Tabela 2 – Resultados obtidos para o PGDLPP com uma única máquina em S1 e S2.
S3
S3-0
AMPL
1269*
S3-1
1491*
S3-2
1338*
S3-3
1530*
S3-4
1663*
S3-5
1542*
S3-6
1553*
S3-7
1518*
S3-8
1526*
AG
1269
0,0
1491
0,0
1338
0,0
1530
0,0
1667
0,3
1542
0,0
1553
0,0
1532,1
0,9
1526
OEP1
1279
0.8
1491
0.0
1338
0.0
1530
0.0
1663
0.0
1542
0.0
1553
0.0
1518
0.0
1526
OEP2
1279
0.8
1491
0.0
1338
0.0
1530
0.0
1663.4
0.02
1542
0.0
1553
0.0
1518
0.0
1526
S4
S4-0
AMPL
1833
S4-1
1986
S4-2
1825
S4-3
1674
S4-4
1974
S4-5
1994
S4-6
1790
S4-7
1786
S4-8
2150
AG
1861,5
1,6
1989,6
0,2
1827,2
0,1
1681,8
0,5
1974
0,0
2011,3
0,9
1793,3
0,2
1784,8
-0,1
2195,4
OEP1
1833
0.0
1986
0.0
1805
-1.1
1779
6.3
1974
0.0
1994
0.0
1790
0.0
1777
-0.5
2139
OEP2
1833
0.0
1986
0.0
1806,9
-1.0
1779
6.3
1974
0.0
1995,5
0.1
1790
0.0
1777
-0.5
2139
9
S3-9
1441*
0,0
1441
0,0
0.0
1441
0.0
0.0
1441
0.0
S4-9
1782
2,1
1788,7
0,4
-0.5
1782
0.0
-0.5
1782
0.0
Tabela 3 – Resultados obtidos para o PGDLPP com uma única máquina em S3 e S4.
As Tabelas 2 e 3 listam os resultados obtidos pelo AMPL/CPLEX e o valor médio da solução
final obtida nas 10 execuções das metaheurísticas. Também é apresentado o desvio
Desv(%)=100*(Z-Z*)/Z*, onde Z é o valor médio da solução final obtida pela metaheurística e
Z* é o valor da solução final retornada pelo AMPL/CPLEX. Os valores na coluna AMPL
sinalizados com * indicam solução ótima. AMPL/CPLEX retornou a solução ótima ao final
de todas as execuções em S1, S2 e S3. No conjunto S4, o AMPL/CPLEX retornou a melhor
solução factível encontrada após 1 hora de execução. OEP1 e OEP2 foram capazes de
encontrar a solução ótima na maioria das instâncias em S1, S2 e S3. Os valores negativos de
alguns desvios em S4 indicam que as metaheurísticas retornaram em média soluções melhores
que aquelas encontradas pelo AMPL/CPLEX. O AG também apresenta soluções melhores
que o AMPL/CPLEX. Todavia, OEP1 e OEP2 superam os resultados médios do AG em 3
instâncias no conjunto S1, sendo um desses resultados (S1-3) com valor médio no ótimo
(Desv(%)=0.0). Nas instâncias do conjunto S2, OEP1 e OEP2 superam os resultados do AG
em 4 instâncias com 4 médias no valor ótimo (S2-0, S2-3, S2-7 e S2-8). O AG supera OEP1 e
OEP2 em apenas 1 instância tanto em S1 quanto em S2. Nos demais resultados os métodos
obtiveram os mesmos resultados. OEP1 e OEP2 superam AG em S3 com 2 resultados (S3-4 e
S3-7) no valor ótimo. O AG obtém o melhor resultado em 1 instância no conjunto S3. Não há
instâncias com solução ótima no conjunto S4, onde OEP1 e OEP2 superam AG em 7
instâncias. AG supera esses métodos novamente em uma única instância. Todos os 7 melhores
resultados obtidos por OEP1 e OEP2 são iguais ou melhores que aqueles obtidos pelo
AMPL/CPLEX. A Figura 9 apresenta os desvios total médio obtidos por cada método
considerando os conjuntos de instâncias. Observe que OEP1 e OPE2 apresentam praticamente
o mesmo desvio em todos os conjuntos e superam o desempenho médio do AG.
Figura 9 – Desvio médio em S1, S2, S3 e S4.
O PGDLPP com máquinas paralelas foi solucionado usando os mesmos três conjuntos de
instâncias (P1, P2 e P3) apresentados em Toledo et al (2009). Os parâmetros utilizados na
geração dessas instâncias foram T=6, S=4, J=4, Ct=200, onde apenas o número de linhas
variou com L=2 em P1, L=3 em P2 e L=4 em P4. Os demais parâmetros permaneceram como
antes, exceto TPlj e U. Agora TPlj [0,1] passa a variar por produto e linha e a taxa de
10
utilização foi fixada em U= 80%. Um total de 5 instâncias foi gerado para cada um desses
conjuntos. O AMPL/CPLEX também foi utilizado na resolução exata dessas instâncias com
tempo de execução de 1 hora. As metaheurísticas foram executadas por 0,5h; Assim com nas
maquinas simples, tiveram metade do tempo destinado ao método exato. As Tabela 4 e 5
apresentam os resultados obtidos.
P1
AMPL
AG
OEP1
OEP2
P2
AMPL
AG
OEP1
OEP2
P1-0
5819,8
P2-1
5364,3
P1-2
4371,5
P2-2
6375,3
P1-3
5043,8
P2-3
7045,4
P1-4
4536,9
4291,4
-26.3
4245,2
-23.7
3673,7
-16.0
4019,9
-20.3
4161,4
-8.3
5730,2
5561,0
4241,3
-27.1
4169,6
-25.0
3650,5
-16.5
3998,4
-20.7
4153,3
-8.5
P2-0
P1-1
4869,1
-16.3
4653,4
-16.3
4052,3
-7.3
4380,5
-13.1
4411,8
-2.7
P2-4
6666,0
4711,4
-17.8
4913,7
-8.4
5183,6
-18.7
5326,4
-24.4
5552,1
-16.7
3793
-33.8
3899,6
-27.3
4244,8
-33.4
4091
-41.9
4186,1
-37.2
3811,4
-33.5
3900,4
-27.3
4302
-32.5
4126
-41.4
4258,9
-36.1
Tabela 4 – Resultados obtidos para o PGDLPP com máquinas paralelas em P1 e P2.
P3
AMPL
P3-0
5679,6
AG
OEP1
OEP2
4711,4 3711,8 3797,7
-17.0
-34.6
-33.1
P3-1 7713,1 4913,7 3726,5 3863,3
-36.3
-51.7
-49.9
P3-2 7806,1 5183,6 3695,3 3865,9
-33.6
-52.7
-50.5
P3-4 7836,7 5552,1 3798,7 3973,4
-29.2
-51.5
-49.3
P3-5 7130,8 5530,8 3690,5 3771,9
-22.4
-48.2
-47.1
Tabela 5 – Resultados obtidos em P3.
O AMPL/CPLEX não foi capaz de retornar soluções ótimas ao final de 1 hora de execução
em P1, P2 e P3. Por outro lado, as metaheurísticas propostas superaram os valores das
soluções finais obtidas pelo AMPL/CPLEX na maioria das instâncias. OEP1 e OEP2 superam
o AG em todas as instâncias do PGDLPP com máquinas paralelas. OEP1 obtém os melhores
resultados em todos os conjuntos.
A Figura 10 apresenta os resultados médios em cada conjunto. O desempenho médio de OEP1
não é muito diferente do obtido por OEP2. Isso indica que a abordagem de ajuste dos pesos,
durante a execução, representou uma pequena melhoria no desempenho do método OEP1. Por
outro lado, as duas abordagens mativeram desempenho bastante superior ao AG.
11
Figura 10 – Desvio médio em S1, S2, S3 e S4.
5. Conclusões
O presente trabalho propôs métodos de resolução para o Problema Geral de
Dimensionamento de Lotes e Programação da Produção (PGDLPP) com e sem máquinas em
paralelo, e com penalização por demandas não atendidas. Um modelo matemático foi
apresentado e duas abordagems baseadas em otimização por enxame de partículas foram
propostas. A primeira utiliza um ajuste dinâmico dos pesos dos vetores de posição das
partículas (OEP1). A segunda é executada todo o tempo com os mesmos pesos. Um total de 7
conjuntos de instâncias são solucionados e comparados aos resultdados obtidos pelo
AMPL/CPLEX e por um algoritmo genético com estrutura hierarquica de indivíduos. Nas
instâncias do PGDLPP com máquinas simples, tanto OEP1 quanto OEP2 apresentam desvios
abaixo de 0.5% em relação ao AMPL/CPLEX. Os métodos superam ou igualam a maioria dos
resultados obtidos pelo AG. Não há uma diferença relevante de desempenho médio entre
OEP1 e OEP2 nessas instâncias. Isso se repete durante a resolução dos conjuntos de instâncias
do PGDLPP com máquinas paralelas. OEP1 consegue melhores resultados que OEP2 na
maiora das instâncias, mas a diferneça desses resultados na média de cada conjunto é
pequena. Dessa forma, o ajuste de pesos durante a execução melhorou o desempenho do
método mas não de forma expressiva. Os resultados obtidos permitem concluir que as duas
abordagens baseadas em otimização por enxame de partícula conseguem melhores resultados
que o AG, anteriormente proposto para o mesmo problema. Além disso, o desempenho médio
de OEP1 e OEP2 foi bastante superior ao AG principalmente nos conjuntos de instâncias mais
complexos.
Referências
ALI, M.M. & KAELO, P. Improved particle swarm algorithms for global optimization. Applied Mathematics
and Computation Vol. 196, p.578-593, 2008.
BITRAN, G. R. & YANASSE, H. H. Computational complexity of the capacitated lot size problem.
Management Science Vol. 28, n. 10, p.1174-1186, 1982.
CHEN, W.H. & THIZY, J.M. Analysis of relaxations for the multi-item capacitated lot-sizing problem. Annals
of Operations Research Vol. 26, p. 29-72, 1990.
CHEN, T. & CHI, T. On the improvements of the particle swarm optimization algorithm. Advances in
Engineering Software. Vol. 41, p. 229-239, 2010.
CHEN, D. & ZHAO, C. Particle swarm optimization with adaptive population size and its application. Applied
Soft Computing Vol. 9, no. 1, , p. 39-48, 2009.
12
DE CASTRO, L.N. & VON ZUBEM, F.J. IEEE Learning and Optimization Using the Clonal Selection
Principle. IEEE Transactions on Evolutionary Computation, Special Issue on Artificial Immune Systems, Vol. 6,
no. 3, p. 239-251, 2002
FLEISCHMANN, B. & MEYR, H. The general lotsizing and scheduling problem. ORSpektrum Vol. 19, p.1121, 1997.
GOREN, H.G; TUNALLI, S. & JANS, R. A review of applications of genetic algorithms in lot sizing. Journal
of Intelligent Manufacturing, Published online: 04 December 2008.
HAASE, K. Capacitated lot-sizing with sequence dependent setup costs. ORSpektrum Vol. 8, p.51-59, 1996.
HOLLAND, J.H. Adaptation in natural and artificial systems. The University of Michigan Press, 1975.
JANS, R. & DEGRAEVE, Z. Metaheuristics for dynamic lot sizing: A review and comparison of solution
approaches. European Journal of Operational Research Vol. 177, p.1855-1875, 2007.
KAELO, P. & ALI, M.M. Integrated crossover rules in real coded genetic algorithms. European Journal of
Operational Research Vol. 176, p.60-76, 2007.
KANG, S., MALIK, K. & THOMAS, L.J. Lotsizing and scheduling on parallel machines with sequencedependent setup costs. Management Science Vol. 45, p.273-289, 1999.
KENNEDY, J. & EBERHART, R.C. Particle swarm optimization. In: Proceedings of IEEE International
Conference in neural networks, p.1942-1948, 1995.
KENNEDY, J., EBERHART, R. & SHI, Y. Swarm Intelligence. Morgan Kaufmann Publishers Inc, San
Francisco, CA, 2001.
MEYR, H. Simultaneous lotsizing and scheduling on parallel machines. European Journal of Operational
Research Vol. 139, p. 277-292, 2002.
TOLEDO, C.F.M., FERREIRA, J. E., SIMEONE, F. & ROSA, G.P. Metaheurísticas Aplicadas ao
Problema Geral de Dimensionamento de Lotes e Programação da Produção. In: XLI SBPO Simpósio Brasileiro
de Pesquisa Operacional, Porto Seguro, BA. 2009.
13