Home   |   Structure   |   Research   |   Resources   |   Members   |   Training   |   Activities   |   Contact

EN | PT

EuPTCEEx0874-51612006000200001

EuPTCEEx0874-51612006000200001

National varietyEu
Country of publicationPT
SchoolEx-Tech-Multi Sciences
Great areaExact-Earth Sciences
ISSN0874-5161
Year2006
Issue0002
Article number00001

Javascript seems to be turned off, or there was a communication error. Turn on Javascript for more display options.

Algoritmos de partição e geração de colunas para dimensionamento de lotes de produção

1 Introdução Neste artigo aborda-se o problema de lotes de produção multi-artigo capacitado com tempos de preparação (LPMAC). Este problema ocorre no âmbito do planeamento da produção de médio prazo, e tem como objectivo a determinação de um plano de produção para vários artigos, habitualmente produtos acabados, ao longo de um determinado horizonte temporal. O plano resultante deverá satisfazer a procura dos clientes e respeitar os limites de capacidade e por outro lado minimizar os custos envolvidos. Visto na perspectiva dos sistemas de planeamento da produção, este problema corresponde ao plano mestre de produção (Pochet, 2001) e pertence à classe de problemas de lotes de produção de nível único, multi-artigo, capacitado e com procura determinística e dinâmica.

Neste trabalho apresentam-se dois métodos de resolução exacta do problema LPMAC baseados em duas decomposições. Em ambas, parte-se de um modelo clássico de Programação Inteira Mista (PIM) e aplica-se o princípio de decomposição de Dantzig-Wolfe (Dantzig and Wolfe, 1960), definindo de diferentes formas os subproblemas. Na primeira decomposição as restrições de capacidade são mantidas no problema mestre, estando cada subproblema associado a um artigo. Para esta decomposição foi desenvolvido um algoritmo de partição e geração de colunas (Jans, 2002). O nosso trabalho difere na forma como as regras de partição são compatibilizadas com o subproblema. Na segunda decomposição as restrições de equilíbrio de stocks são mantidas no problema mestre, estando cada subproblema associado a um período. Uma contribuição fundamental deste trabalho é o desenvolvimento de um algoritmo de partição e geração de colunas baseado nesta decomposição.

Para resolver a relaxação linear dos modelos reformulados utiliza-se o método de geração de colunas (column generation) e para resolver o problema inteiro aplica-se o método de partição e geração de colunas (branch and price).

A motivação para a utilização de métodos de decomposição neste trabalho está relacionada com a potencial vantagem destes métodos em termos da qualidade dos limites inferiores que produzem, comparativamente com os limites que se obtêm resolvendo directamente a formulação clássica de PIM para o LPMAC. Do aumento da qualidade das soluções, resulta potencialmente a redução dos tempos de resolução do problema. Uma outra contribuição deste trabalho está associada à comparação experimental entre dois modelos de decomposição alternativos e entre estes e a formulação clássica resolvida pelo software comercial Cplex 8.1 (ILOG, 2002).

No que respeita à organização do artigo, na Secção 2 apresenta-se uma revisão de bibliografia relativa aos modelos e métodos de resolução para o problema. Na Secção 3 descreve-se o problema LPMAC e apresenta-se uma formulação clássica de PIM para este problema. Na Secção 4 aplicam-se duas decomposições de Dantzig-Wolfe ao problema e definem-se os problemas mestres e subproblemas associados, bem como a estratégia usada para a obtenção de soluções inteiras. Na Secção 5 apresentam-se resultados computacionais para um conjunto de instâncias com diferentes características, que permitem estabelecer comparações entre os dois modelos de decomposição e um software comercial de PIM e por último, na Secção 6 apresentam-se as conclusões deste trabalho.

2 Revisão Bibliográfica O primeiro modelo de Programação Inteira para problemas de lotes de produção deve-se a Wagner e Whitin (Wagner and Whitin, 1958), que apresentaram para o problema de lotes de produção de artigo único não capacitado, conhecido na literatura por ULS Uncapacitated Lot Sizing Problem, uma formulação de programação matemática e um algoritmo de programação dinâmica, conhecido como algoritmo de Wagner-Whitin.

Existem na literatura (ver, por exemplo, (Drexl and Kimms, 1997) e (Kuik et al., 1994)) quatro modelos principais de PIM para a classe de problemas de lotes de produção de nível único, multi-artigo, com procura determinística e dinâmica e capacitado: o modelo CLSP Capacitated Lot Sizing Problem, o modelo DLSP Discrete Lot Sizing and Scheduling Problem, o modelo CSLP Continuous Setup Lot Sizing Problem e o modelo PLSP Proportional Lot Sizing and Scheduling Problem.

Nos problemas de lotes de produção multi-artigo capacitados é habitual estabelecer-se a distinção entre small bucket problems (SBP) e big bucket problems (BBP). Nos BBP permite-se a produção de vários artigos em cada período de planeamento enquanto que nos SBP considera-se que em cada período de planeamento apenas um artigo pode ser produzido. Os SBP permitem modelar as decisões de escalonamento e são adequados para situações em que existe a necessidade de controlar com rigor a capacidade consumida na preparação enquanto que os BBP utilizam-se ao nível do dimensionamento de lotes, onde normalmente se tomam decisões com base em recursos agregados.

O problema CLSP é uma extensão do problema ULS para o caso capacitado e consequentemente multi-artigo e é um BBP. Os modelos DLSP e CSLP são ambos SBP e integram as decisões de dimensionamento de lotes com as decisões de escalonamento.

Enquanto que no CSLP, a produção realizada em cada período pode variar, mas é limitada pela restrição de capacidade, no DLSP, a quantidade produzida em cada período ou é nula, ou tem de ser igual à capacidade total desse período. O PLSP é também um SBP e surgiu na sequência do CSLP. Neste modelo permite-se a produção de dois artigos em cada período com o objectivo de se utilizar toda a capacidade disponível em cada período.

O problema abordado neste artigo (LPMAC) é um CLSP com tempos de preparação. Os trabalhos pioneiros, sobre métodos de resolução para o problema LPMAC devem-se a Manne (Manne, 1958), a Dzielinski e Gomory (Dzielinski and Gomory, 1965) e a Lasdon e Terjung (Lasdon and Terjung, 1971). Em (Manne, 1958) apresenta-se um modelo aproximado de programação linear para o problema. Em (Dzielinski and Gomory, 1965) é aplicada a decomposição de Dantzig-Wolfe ao problema e determina-se o limite inferior do problema reformulado pelo método de geração de colunas. Em (Lasdon and Terjung, 1971) reformula-se o modelo de programação linear proposto por (Manne, 1958) e resolvese esse novo problema pelo método de geração de colunas. Estas abordagens estão directamente relacionadas com a decomposição por artigo a apresentar na subsecção 4.1, sendo de salientar que, tal como a generalidade das abordagens baseadas em relaxação Lagrangeana ((Chen and Thizy, 1990), (Diaby et al., 1992b), (Merle et al., 1999), (Thizy and Wassenhove, 1985) e (Trigeiro et al., 1989)), apenas conduzem à obtenção de limites inferiores e não a uma solução óptima inteira. Uma excepção é o trabalho de (Jans, 2002) que aplica a decomposição de Dantzig-Wolfe e o método de geração de colunas para resolver a relaxação linear do problema LPMAC e aplica o método de partição e geração de colunas para determinar a sua solução óptima inteira. Este trabalho está relacionado com o trabalho aqui apresentado no âmbito da decomposição por artigo. Aquilo que o distingue do algoritmo baseado na decomposição por artigo aqui desenvolvido é a utilização de regras de partição diferentes.

Diaby et al. (Diaby et al., 1992a) abordam o problema LPMAC através de uma relaxação Lagrangeana alternativa, baseada na relaxação das restrições de equilíbrio de stocks. Essa abordagem está relacionada com a decomposição por período apresentada na subsecção 4.2. Embora aqui também se aborde uma decomposição em que os subproblemas estão associados a períodos, os métodos aplicados na resolução do problema reformulado, são diferentes. Neste trabalho utiliza-se a decomposição de Dantzig-Wolfe e técnicas de partição e geração de colunas.

Outros métodos específicos, não directamente relacionados com os apresentados neste artigo, têm sido aplicados no LPMAC, sendo de salientar métodos de planos de corte ((Barany et al., 1984), (Belvaux and Wolsey, 2000), (Miller et al., 2000) e (Pochet and Wolsey, 1991)), redefinição de variáveis (Eppen and Martin, 1987) e métodos heurísticos (Karimi et al., 2003).

3 O problema de lotes de produção multi-artigo capacitado com tempos de preparação O planeamento da produção é uma importante área em qualquer organização industrial, pois permite-lhe lidar de uma forma mais eficiente com as decisões associadas ao fluxo de materiais e com a utilização de pessoas e equipamentos, entre outros. Em qualquer sistema de produção existe normalmente um número extremamente elevado de artigos (ou encomendas) a produzir num conjunto limitado de recursos, aos quais estão associadas datas de entrega acordadas com os clientes que se podem sobrepor e que devem ser cumpridas. O planeamento da produção encarrega-se de planear os recursos e actividades necessárias de modo a permitir a entrega atempada daquilo que é pedido. É neste contexto que o problema LPMAC se torna relevante. Este problema diz respeito às decisões tomadas ao nível do plano mestre de produção, no sistema de planeamento da produção. Em linhas gerais, neste problema procura-se determinar um plano de produção para um conjunto de artigos finais, faseado no tempo, através da consideração de um conjunto de períodos de planeamento. Esse plano indica para cada artigo final as quantidades a produzir desse artigo (que definem um lote) e os períodos em que essas quantidades devem ser produzidas, atendendo a um conjunto de restrições.

Associado a cada plano de produção, existe um custo que engloba três componentes: custos de produção, custos de armazenagem e custos de preparação. O custo de produção pode variar com o artigo e com o período e representa o custo incorrido por cada unidade produzida. O custo de armazenagem representa o custo que se incorre por unidade armazenada e por período de armazenagem, sempre que a decisão é a de produzir antecipadamente para satisfazer procuras de períodos posteriores. Por último, o custo de preparação representa um custo fixo do lote.

No modelo mais estudado do problema de lotes de produção multi-artigo capacitado apenas se consideram os custos de preparação, sendo a preparação contabilizada apenas na função objectivo. Como o tempo de preparação (de máquinas, pessoas, materiais, etc.) consome parte da capacidade de produção disponível, nesse modelo a capacidade realmente utilizada é necessariamente subestimada. Para muitos dos autores que consideram na formulação do problema apenas o custo de preparação, a inclusão deste tempo no modelo é vista como uma extensão simples. Esta posição é contrariada em (Trigeiro et al., 1989), onde se mostra que o problema com a consideração dos tempos de preparação se torna num problema muito mais difícil de resolver. Com vista à modelação mais precisa do problema, é este último modelo que é abordado neste artigo, considerando-se directamente no modelo a capacidade gasta com a preparação, ao invés de esta ser considerada implicitamente no custo de preparação.

Nos parágrafos que se seguem, apresenta-se a formulação clássica de PIM para o problema LPMAC.

Considerem-se os seguintes conjuntos e parâmetros: I que representa o conjunto de artigos, indexados por i=1,...,n; J que representa o conjunto de períodos de produção, indexados por j=1,...,m; pij que representa o custo unitário de produção do artigo i no período j; qij que representa o custo fixo de preparação do artigo i no período j; hij que representa o custo unitário de armazenagem do artigo i no final do período j; dij que representa a procura do artigo i no período j; cj que representa a capacidade de produção no período j; aij que representa a capacidade consumida na produção de uma unidade do artigo i no período j e bij que representa a capacidade consumida na preparação do artigo i no período j.

Considerem-se ainda as seguintes variáveis de decisão: xij que representa a quantidade a produzir do artigo i no período j; yij que é uma variável binária que assume o valor 1 se o artigo i é produzido no período j, e assume o valor 0 caso contrário e sij que representa o nível de inventário do artigo i no final do período j.

Para um determinado horizonte temporal o objectivo é o de determinar as quantidades a produzir de cada artigo em cada período e as quantidades a armazenar de cada artigo para períodos posteriores, que minimizam os custos de produção, de preparação e de armazenagem e que garantem a entrega atempada dos artigos, a ocorrência de uma preparação sempre que se produza e que a capacidade disponível não é ultrapassada.

Matematicamente podemos concretizar este objectivo através da formulação de PIM que se apresenta de seguida, que se designa por formulação clássica.

n

m

n

m

n

m

Z C = Min p ij x ij + q ij y ij + h ij s ij i =1 j =1

i =1 j =1

(C)

i =1 j =1

sujeito a: x1i = d1i + s1i ,

s

i j −1

i j

∀i I i j

i j

+x =d +s ,

n

n

i =1

i =1

(1) ∀i I, ∀j J \ {1}

a ij x ij + b ij y ij c j , ∀j J

⎧⎪c j b ij m i ⎫⎪ i x ij min , dt ⎬y j , i t= j ⎪⎭ ⎪⎩ a j s ij 0 , ∀i I, ∀j J i j

x 0,

∀i I, ∀j J

y ij {0 ,1},

∀i I, ∀j J .

(2) (3)

∀i I, ∀j J

(4) (5) (6) (7)

A função objectivo minimiza o custo total. As restrições (1) e (2) são as restrições de equilíbrio de stocks, que garantem que a procura dos clientes em cada período é satisfeita e que relacionam os níveis de inventário de um determinado período com os níveis de inventário do período imediatamente anterior. As restrições (3) são as restrições de capacidade, que forçam o consumo do recurso com a produção e a preparação a não exceder a capacidade disponível no período j. As restrições (4) garantem que uma preparação ocorre se o artigo i for produzido no período j. Estas restrições poderiam ser substituídas por xij≤Myij, sendo M um valor constante elevado. Deste modo garantir-se-ia que, sempre que se decidisse produzir o artigo i no período j, deveria ocorrer uma preparação. Para tornar a formulação mais forte, o coeficiente M pode ser substituído por c j b ij , ou seja, pela quantidade máxima que é possível produzir do artigo i um lado por a ij m

no período j, e por outro lado por dti , ou seja, pela soma da procura desde o período em t=j

análise (período j) até ao último período de planeamento. Entre os dois coeficientes referidos, deve escolher-se aquele que tiver menor valor, uma vez que a quantidade a produzir do artigo i no período j será limitada por esse valor. As restrições (5) e (6) impõem a condição de não negatividade das variáveis e as restrições (7) forçam as variáveis de preparação a assumir valores binários.

A formulação clássica é constituída por 2nm variáveis contínuas, nm variáveis binárias e m+2nm restrições, sem considerar as condições de integralidade e de não negatividade. Relembra-se que n representa o número de artigos e m o número de períodos de planeamento.

4 Decomposições para o problema LPMAC A qualidade dos limites inferiores de um modelo é um aspecto crucial na resolução de modelos de PIM. É nesse sentido que se aplica aqui a decomposição de Dantzig-Wolfe (Dantzig and Wolfe, 1960), que esta permite a obtenção de formulações mais fortes para o problema. Do aumento da qualidade do modelo podem resultar melhores intervalos de integralidade e melhores tempos de resolução dos problemas.

A um problema de PIM podem aplicar-se diferentes decomposições de Dantzig-Wolfe, de acordo com as restrições que se considerem na definição do subproblema e do problema mestre. Após a análise da estrutura da formulação clássica do problema LPMAC, identificaram-se duas decomposições de Dantzig-Wolfe alternativas, que se estudaram com o objectivo de aferir a sua eficiência e de estabelecer algumas comparações entre ambas, bem como compará-las com a formulação clássica resolvida através de um software comercial de PIM. Nas subsecções seguintes apresentam-se as duas decomposições.

4.1 Decomposição por Artigo Na formulação clássica do problema LPMAC apresentada na secção anterior, apenas as restrições de capacidade (3) interligam os artigos a produzir. Se se deixar de considerar estas restrições, o problema decompõe-se num conjunto de (sub)problemas independentes, cada um correspondendo a um problema de lotes de produção de artigo único não capacitado (ULS). Para tirar partido desta estrutura, nesta decomposição, as restrições (3) definem as restrições de ligação, que ficam no problema mestre. O subproblema é composto pelas restrições (1)-(2) e (4)-(7) e cada subproblema está associado ao problema ULS, existindo n subproblemas diferentes.

4.1.1 Problema Mestre Para a definição do problema mestre, considere-se o conjunto H que representa o conjunto de planos de produção indexados por k=1,...,t e os parâmetros: β ijk, α ijk e δ ijk. β ijk assume o valor 1 caso exista uma preparação do artigo i no período j no plano de produção k, e assume o valor 0 caso contrário; i=1,...,n ; j=1,...,m ; k=1,...t. αijk representa a quantidade a produzir do artigo i no período j, no plano de produção k; i=1,...,n ; j=1,...,m ; k=1,...t e δ ijk representa o nível de inventário do artigo i no final do período j, no plano de produção k; i=1,...,n ; j=1,...,m ; k=1,...t. Considere-se ainda a variável zik que representa o peso do plano de produção k do artigo i; i=1,...,n ; k=1,...t e os parâmetros e variáveis de decisão definidas na Secção 3, relativas à formulação clássica.

Da aplicação da decomposição de Dantzig-Wolfe à formulação clássica, resulta um novo problema, que se designa por problema mestre, que tem associadas variáveis de decisão que representam o peso dos pontos extremos dos subproblemas (como o poliedro definido pelas restrições que definem o subproblema é limitado, no problema mestre existirão apenas pontos extremos). Qualquer solução do problema mestre pode então ser expressa através de uma combinação convexa e não negativa dos pontos extremos dos subproblemas. O problema mestre, da decomposição por artigo é do tipo: n t ⎡m Z PMI = Min∑∑ ⎢∑ (q ij β ijk + p ijα ijk + hijδ ijk )zki i =1 k =1 j =1

(PMI)

sujeito a: t

z ki = 1, ∀i I

(π i )

(8)

k =1

n

t

( b ij β ijk + a ij α ijk ) z ki c j , ∀j J

i =1 k =1

i z k 0 , ∀i I , ∀k H .

( μj )

(9) (10)

Nesta decomposição, a solução dos subproblemas (variáveis de decisão do problema mestre) correspondem a planos de produção. Para um determinado artigo, cada plano de produção indica em que períodos se deve produzir e em que quantidades. As variáveis de decisão zik representam assim a proporção da procura do artigo i que é satisfeita através do plano de produção k. A função objectivo minimiza a soma dos custos totais. As restrições (8) são as restrições de convexidade. Existe uma restrição de convexidade para cada artigo, na qual se força a escolha de uma combinação de planos de produção.

Associada a cada restrição de convexidade está uma variável dual π i. O segundo conjunto de restrições, conjunto (9), diz respeito às restrições de capacidade. Neste conjunto forçase a que a combinação de planos de produção escolhida respeite a capacidade disponível em cada período. Este segundo conjunto tem associadas as variáveis duais μj. As restrições (10) forçam as variáveis de decisão a tomarem valores não negativos.

Em termos de dimensão, o problema PMI, comparativamente com o problema C, tem um número mais reduzido de restrições. Enquanto que na formulação clássica existem como vimos anteriormente m+2nm restrições, no problema mestre PMI, este número reduz-se para n+m. em termos de variáveis, o problema PMI, comparativamente com o problema C, tem um número gigantesco de variáveis, pelo que se utiliza o método de geração de colunas para o resolver. A ideia subjacente à geração de colunas pode definirse do seguinte modo: em vez de considerarmos todos os planos de produção dos subproblemas no problema mestre PMI, vamos considerar apenas um conjunto restrito desses planos, definindo um problema mestre restrito (PMR) e avaliar se existem planos que não estão actualmente no problema PMI, que caso fossem incluídos no problema poderiam melhorar o valor da função objectivo. Os planos de produção que se revelarem atractivos devem ser adicionados ao problema mestre.

Para iniciar o processo iterativo de geração de colunas, o PMR tem de ser um problema válido, visto ter de fornecer variáveis duais aos subproblemas, para fazer a avaliação dos planos de produção atractivos. Para garantir a admissibilidade do PMR incluiu-se nas restrições (8) um conjunto de variáveis artificiais, vi, associadas a cada n

artigo e na função objectivo o termo f iv i , onde f i representa uma penalidade elevada, i =1

que torna qualquer solução com variáveis artificiais positivas de pior qualidade que uma solução óptima em termos das variáveis zik. Foram ainda incluídos no primeiro PMR um subconjunto de planos de produção do conjunto de todos os planos de produção dos n subproblemas.

Para recuperar a solução do problema C, a partir de uma solução do problema PMI basta aplicar as expressões: x ij = y ij =

t

α ijk z ki

(11)

k =1 t

β ijk z ki

(12)

k =1

Conhecido o valor das variáveis xij, através das equações (1) e (2), é imediata a determinação do valor das variáveis de decisão auxiliares sij.

4.1.2 Subproblemas Se μj representar o vector de variáveis duais associado ao conjunto de restrições de capacidade (9) e π i a variável dual associada à restrição i do conjunto de restrições de convexidade (8), os n subproblemas a resolver são definidos por: m

Z SPI = Min p ij x ij + j =1

m

m

m

m

j =1

j =1

j =1

j =1

q ij y ij + h ij s ij ( b ij y ij ) μ j ( a ij x ij ) μ j π i (SPI)

sujeito a: x1i = d1i + s1i ,

s ij −1 + x ij = d ij + s ij ,

(13) ∀j J \ {1}

⎧⎪c j b ij m i ⎫⎪ i x ij min , dt ⎬y j , i t=j ⎪⎭ ⎪⎩ a j x ij 0 ,

∀j J

∀j J

(14) (15) (16)

y ij {0 ,1}, ∀j J

(17)

s ij 0 ,

(18)

∀j J .

Para resolver os subproblemas da decomposição por artigo, pode utilizar-se o algoritmo de programação dinâmica proposto por (Wagner and Whitin, 1958), que resolve em tempo polinomial o problema. Cada subproblema tem associados 2m-1 planos de produção e a solução óptima de cada um dos n subproblemas representa um plano de produção relativo ao artigo i. Como no subproblema não existem restrições de capacidade, em todos os planos de produção, quando se toma a decisão de produzir num determinado período, produz-se para satisfazer a procura de um número inteiro de períodos. Estes planos são conhecidos por planos de Wagner-Whitin.

Durante o processo de geração de colunas, enquanto o valor óptimo da função objectivo do subproblema (custo reduzido associado a um plano de produção) for menor do que zero, deverá adicionar-se ao problema mestre uma nova coluna ou variável, que corresponde à solução do subproblema (plano de produção). Em cada iteração, podem portanto ser adicionadas ao problema mestre n novas colunas, caso cada subproblema contribua com uma coluna atractiva.

4.2 Decomposição por Período Nesta subsecção aborda-se uma decomposição alternativa à decomposição por artigo, que consiste em deixar no problema mestre as restrições de equilíbrio de stocks (1) e (2) e em passar para o subproblema as restrições (3), (4), (6) e (7). Com esta decomposição os subproblemas passam a estar associados aos períodos de planeamento. No nosso melhor conhecimento, esta decomposição foi apenas estudada por (Diaby et al., 1992a), que utilizaram a relaxação Lagrangeana e resolveram o problema reformulado pelo método do subgradiente. Neste trabalho, aplica-se a decomposição de Dantzig-Wolfe e a resolução do problema reformulado é feita pelo método de geração de colunas, que quando combinado com o método de partição e avaliação, permite ainda a obtenção de soluções óptimas inteiras.

4.2.1 Problema Mestre Para definir o problema mestre da decomposição por período, considerem-se os parâmetros e variáveis da formulação clássica apresentada na Secção 3, o conjunto H que representa o conjunto de padrões de produção indexados por k=1,...,t e os parâmetros: β ijk e α ijk. β ijk assume o valor 1 caso exista uma preparação no período j do artigo i, no padrão de produção k e assume o valor 0 caso contrário; i=1,...,n ; j=1,...,m ; k=1,...t e αijk representa a quantidade a produzir no período j do artigo i, no padrão de produção k; i=1,...,n ; j=1,...,m ; k=1,...t. Considere-se também a variável de decisão zjk que representa o peso do padrão de produção k do período j; j=1,...,m ; k=1,...t.

O problema mestre que na decomposição por período resulta da aplicação da decomposição de Dantzig-Wolfe, é tal como o da decomposição por artigo constituído por variáveis de decisão que representam pesos de pontos extremos dos subproblemas, pois neste caso o poliedro definido pelas restrições do subproblema é também um conjunto limitado . A diferença é que agora as variáveis representam padrões de produção que estão associados a um período. Cada padrão de produção indica para um determinado período a quantidade que deve ser produzida do mix de artigos a processar.

A solução da relaxação linear do problema LPMAC, quando se aplica a decomposição por período, pode ser obtida resolvendo o seguinte problema mestre, aqui designado por PMJ: n m m t n Z PMJ = Min h ij s ij + ⎡⎢∑ (q ij β ijk + p ijα ijk )z jk ⎤⎥ i =1 j =1 j =1 k =1 i =1

(PMJ)

sujeito a: t

z jk 1, ∀j J

k =1

(π j )

t

α1ik z1k = d1i + s1i , ∀i I

k =1

s ij −1 +

(19) ( μ1i )

(20)

t

α ijk z jk = d ij + s ij , ∀i I, ∀j J \ {1} ( μ ij )

(21)

k =1

s ij 0 ,

z jk 0 ,

∀i I, ∀j J

(22)

∀j J, ∀k H .

(23)

As variáveis de decisão zjk podem ser vistas como a proporção da procura do período j que é satisfeita pelo padrão de produção k. A função objectivo do problema mestre minimiza a soma dos custos totais. As restrições (19) representam as restrições de convexidade. Existe uma restrição de convexidade associada a cada período na qual se força a escolha de uma combinação de padrões de produção. Associada a cada restrição de convexidade está uma variável dual πj. No caso da decomposição por período, as restrições de convexidade podem ser escritas como uma desigualdade do tipo , em vez da sua forma habitual, na qual estas restrições são escritas como uma igualdade. Esta alteração é possível, devido ao espaço de soluções admissíveis do subproblema SPJ (que será definido na subsecção seguinte) incluir a origem. Com esta modificação, excluem-se do problema mestre os padrões de produção que indiquem que para um determinado período nada deve ser produzido. O conjunto de restrições (20) e (21), são as restrições de equilíbrio de stocks. Neste conjunto força-se a que a combinação de padrões de produção escolhida respeite a procura de cada artigo em cada período. Este conjunto tem associadas as variáveis duais μ ij . As restrições (22) e (23) impõem a condição de não negatividade das variáveis de inventário e das variáveis de peso, respectivamente.

Quanto à dimensão, o problema PMJ tem m+nm restrições. Nesta decomposição o número de variáveis do problema mestre é extremamente elevado, pelo que também se recorre ao método de geração de colunas para resolver o problema PMJ.

Devido ao conjunto de restrições de equilíbrio de stocks do primeiro período de planeamento, restrições (20), o primeiro PMR pode não ser válido. Para o validar, associou-se uma variável artificial, vi, a cada restrição deste conjunto. Estas variáveis podem ser interpretadas como sendo o inventário existente no início do primeiro período n

de planeamento. À função objectivo, adicionou-se o termo f iv i , onde f

i

é um escalar

i =1

com um valor muito elevado, para garantir que qualquer solução com variáveis artificiais positivas é pior que uma solução óptima em termos das variáveis de peso zjk.

A solução do problema C, pode ser obtida por aplicação das seguintes expressões:

x ij = y ij =

t

α ijk z jk

(24)

k =1 t

β ijk z jk

(25)

k =1

4.2.2 Subproblemas Cada um dos m subproblemas da decomposição por período é definido por: n

n

n

i =1

i =1

i =1

Z SPJ = Min p ij x ij + q ij y ij x ij μ ij π j

(SPJ)

sujeito a: n

n

i =1

i =1

a ij x ij + b ij y ij c j ,

⎧⎪c j b ij m i ⎫⎪ i x ij min , dt ⎬y j , i t=j ⎪⎩ a j ⎪⎭ x ij 0 ,

∀i I

y ij , {0 , 1} ∀i I ,

(26) ∀i I

(27) (28) (29)

onde πj representa a variável dual associada à restrição j do conjunto de restrições de convexidade (19) e μ ij representa o vector de variáveis duais associado ao conjunto de restrições de equilíbrio de stocks (conjunto de restrições (20) e (21)).

A função objectivo de cada subproblema representa o custo reduzido associado ao padrão de produção j. No processo de geração de colunas, enquanto os custos reduzidos dos subproblemas forem menores do que zero, deverão adicionar-se ao problema mestre restrito os padrões de produção correspondentes.

Os subproblemas da decomposição por período estão associados ao problema da mochila contínuo com preparações (continuous knapsack problem with setups). Este problema foi recentemente abordado em (Perrot and Vanderbeck, 2004), onde é apresentado um algoritmo de programação dinâmica e um algoritmo de partição e avaliação para o problema.

4.3 Pesquisa de Soluções Inteiras Ao resolver os problemas mestres definidos nas subsecções 4.1.1 e 4.2.1 por geração de colunas, estamos a determinar a solução óptima da relaxação linear dos modelos de decomposição. O valor da solução que se obtém representa portanto um limite inferior para o valor do óptimo inteiro. Como os subproblemas que resultam de ambos os modelos de decomposição não possuem a propriedade da integralidade (Geoffrion, 1974), o limite inferior que se obtém na resolução dos problemas mestres é melhor ou igual que o obtido pela solução da relaxação linear da formulação clássica.

Para recuperarmos uma solução expressa em termos das variáveis de peso para uma solução em termos das variáveis originais da formulação clássica, basta aplicarmos as expressões (11) e (12) no caso da decomposição por artigo e as expressões (24) e (25) caso se trate da decomposição por período. Se, nessa solução, existirem variáveis de preparação, as variáveis yij, que não sejam binárias, esta solução não corresponde à solução óptima do problema C. Para determinar a solução óptima inteira do problema deverá então recorrer-se ao método de partição e geração de colunas. Este método combina o método de partição e avaliação com o método de geração de colunas (Barnhart et al., 1998) e assenta na resolução de um problema mestre em cada nodo da árvore de pesquisa através do método de geração de colunas.

A estratégia de partição usada neste trabalho, consiste em adicionar ao problema mestre restrições de partição que forçam as variáveis originais de preparação a assumir valores binários. Esta estratégia tem a vantagem de ser geral, podendo ser aplicada a qualquer tipo de problema, garantindo a preservação da estrutura do subproblema nos nodos da árvore de pesquisa.

Quando a solução da raiz da árvore de pesquisa, ou a solução de um determinado nodo não é inteira, e existe interesse em explorá-lo, devem adicionar-se dois novos nodos ao problema. Cada um destes nodos passa a definir um novo problema, no qual para além de se considerar o problema mestre actual, se considera também uma das restrições de partição, a seguir apresentadas:

β ijk z ki = 0 ou β ijk z ki = 1

se decomposição por artigo

β ijk z jk = 0 ou β ijk z jk = 1

se decomposição por período

k ∈H

k ∈H

k ∈H

k ∈H

onde H representa o conjunto de planos de produção (se decomposição por artigo) ou de padrões de produção (se decomposição por período) que fazem parte desse problema mestre actual.

Após a adição da restrição de partição, para que os custos reduzidos dos subproblemas a resolver no processo de geração de colunas sejam correctamente determinados, deve alterar-se a função objectivo desses subproblemas, na qual se deve passar a considerar a variável dual associada à restrição de partição que foi adicionada.

No caso da decomposição por artigo, se ηij representar a variável dual associada à restrição de partição que foi adicionada ao nodo, na função objectivo de cada um dos n subproblemas, apresentada na subsecção 4.1.2, deve subtrair-se o termo seguinte: m

y ijη ij . Se se tratar da decomposição por período e se for τ ij a variável dual associada à j =1

restrição de partição, na função objectivo de cada um dos m subproblemas apresentados n

na subsecção 4.2.2 deve subtrair-se o termo: y ijτ ij .

i =1

5 Resultados Computacionais Com o objectivo de avaliar e comparar o desempenho de ambos os algoritmos de partição e geração de colunas e de os comparar com a formulação clássica resolvida pelo software Cplex 8.1 realizaram-se testes computacionais, cujos resultados se apresentam neste capítulo. Para medir o desempenho de cada um dos três métodos, utilizaram-se os seguintes critérios: qualidade dos limites inferiores (medida através do cálculo dos intervalos de integralidade) e eficiência. Os resultados computacionais foram obtidos através da resolução de um conjunto de 180 instâncias usadas por (Trigeiro et al., 1989), as quais foram geradas com base na variação de quatro características: variabilidade da procura, capacidade utilizada, periodicidade de encomenda (time between orders) e tempo de preparação. Na mesma referência podem encontrar-se informações pormenorizadas acerca da forma como estas instâncias foram obtidas. Todas as instâncias consideram 10 artigos e 20 períodos de planeamento.

Em ambos os modelos de decomposição, os problemas mestres quer da raiz da árvore de pesquisa quer de qualquer nodo da árvore, são resolvidos até à optimalidade pelo algoritmo dual do simplex, através do Cplex. Os subproblemas da decomposição por artigo e da decomposição por período são também resolvidos até à optimalidade, usando o Cplex. Os primeiros problemas mestres restritos são definidos através de um conjunto de variáveis artificiais que asseguram a admissibilidade dos mesmos e de um subconjunto de planos de produção no caso da decomposição por artigo e em cada iteração do método de geração de colunas resolvem-se todos os subproblemas até optimalidade e todas as colunas atractivas são adicionadas ao problema mestre restrito.

No método de partição e geração de colunas, quer na decomposição por artigo, quer na decomposição por período, fizeram-se alguns testes preliminares onde se testaram duas estratégias de pesquisa da árvore. Na primeira estratégia utilizou-se a pesquisa primeiro em profundidade e deu-se prioridade ao nodo que tem associado a restrição de partição do tipo e na regra de partição utilizou-se uma estratégia baseada na escolha da variável com parte fraccionária mais próxima de 1. Na segunda estratégia de pesquisa da árvore, também se utilizou a pesquisa primeiro em profundidade, mas deu-se prioridade ao nodo de pesquisa que tem associada a restrição de partição do tipo e na regra de partição utilizou-se uma estratégia baseada na escolha da variável com parte fraccionária mais próxima de 0. Como a primeira estratégia foi a que produziu melhores resultados, na realização dos testes que aqui se apresentam foi esta a estratégia seguida.

Os algoritmos de partição e geração de colunas foram implementados em C++ utilizando a ferramenta ADDing Automatic Dantzig-Wolfe Decomposition for INteger column Generation (Alvelos, 2005). Os testes foram realizados num computador pessoal com um processador Pentium 4 a 2 GHz e com 1 GB de memória.

Na tabela 1 apresentam-se os tempos de resolução da relaxação linear dos dois modelos de decomposição e da formulação clássica resolvida pelo Cplex. Esses tempos estão expressos em segundos e referem-se aos tempos médios de resolução do conjunto de 180 instâncias.

Na resolução do problema inteiro, limitou-se o tempo de resolução a 3600 segundos.

Usando a decomposição por período, não se consegue atingir a solução óptima em nenhuma das 180 instâncias no tempo limite estabelecido, encontrando-se apenas soluções incumbentes. Em 109 das 180 instâncias testadas não se consegue determinar a solução óptima usando quer a decomposição por artigo, quer o Cplex. Existem portanto 71 instâncias que são resolvidas até à optimalidade, considerando o Cplex e/ou a decomposição por artigo. Desta análise concluí-se que em cerca de 40% das instâncias testadas se consegue determinar a solução óptima do problema em menos de uma hora.

Com o Cplex consegue-se determinar a solução óptima de 61 instâncias num tempo médio de 307.90 segundos enquanto que com a decomposição por artigo se consegue determinar a solução óptima de 59 instâncias, num tempo médio de 381.90 segundos.

em termos de soluções incumbentes, em 49 das 109 instâncias em que não se consegue determinar a solução óptima o Cplex apresenta melhores incumbentes que os modelos de decomposição. Nas restantes 60 instâncias, é a decomposição por artigo que apresenta as melhores soluções incumbentes. As soluções incumbentes da decomposição por período são sempre piores que as soluções incumbentes da decomposição por artigo e do Cplex. Na tabela 2 sumariam-se estes resultados. A segunda coluna da tabela refere-se ao número de instâncias que são resolvidas até à optimalidade por cada um dos métodos e na terceira coluna apresentam-se os tempos médios de resolução dessas instâncias. Na quarta coluna apresentam-se os intervalos médios de integralidade ou GAP’s médios de integralidade em percentagem. Os GAP’s foram determinados através da seguinte Z Z LI , representando ZPI o valor da solução óptima inteira e ZLI o valor do expressão: PI Z PI limite inferior (o valor da solução óptima do nodo da raiz da árvore) de cada um dos três métodos. Nesta análise consideraram-se as 71 instâncias para as quais se obteve a solução óptima inteira. Por último, na quinta coluna quantifica-se o número de instâncias, do conjunto das 109 que não são resolvidas até à optimalidade, em que cada método apresenta melhores soluções incumbentes.

Analisando os resultados da tabela 1, conclui-se que na decomposição por artigo os tempos médios de resolução da relaxação linear são bastante inferiores aos obtidos com a decomposição por período. Entre a decomposição por artigo e o Cplex, a diferença não é tão significativa, mas o Cplex consegue resolver a relaxação mais rapidamente. A diferença de tempos médios entre a decomposição por artigo e a decomposição por período ronda os 19.50 segundos e entre a decomposição por artigo e o Cplex ronda os 2 segundos. Da análise da tabela 2 depreende-se que em termos do número de instâncias resolvidas até à optimalidade, a diferença entre a decomposição por artigo e a decomposição por período é enorme. Entre a decomposição por artigo e o Cplex considerase que essa diferença não é significativa. Quanto aos tempos médios de resolução do problema inteiro, como na decomposição por período não se obtém nenhuma solução óptima, nesta análise apenas se consideraram os tempos médios de resolução do conjunto de 59 instâncias da decomposição por artigo e do conjunto de 61 instâncias da decomposição por período. O Cplex é o método que em média apresenta melhores tempos de resolução, não sendo contudo significativa a diferença entre os tempos médios deste método e os tempos médios da decomposição por artigo. Essa diferença é de 74 segundos.

Quanto aos GAP’s de integralidade, esta é para nós uma medida de desempenho fundamental, pois permite-nos aferir acerca da qualidade dos modelos desenvolvidos, independentemente da implementação utilizada para os resolver. O modelo da decomposição por artigo é claramente mais forte que o modelo da decomposição por período e que a formulação clássica. Comparando o GAP da decomposição por período com o do Cplex, concluí-se que são ambos semelhantes, embora o GAP da decomposição por período seja um pouco melhor. Para além da análise dos GAP’s, a análise das melhores soluções incumbentes, permite-nos também atestar a qualidade das soluções.

Quanto mais baixo for o valor da solução incumbente mais próximo estamos do valor da solução óptima inteira. Para o conjunto das 109 instâncias, para as quais não se obtém a solução óptima inteira em 3600 segundos, compararam-se as soluções incumbentes obtidas pelos três métodos na altura em que o tempo limite foi atingido. Dessa análise verificou-se que a decomposição por artigo é a que apresenta para um maior número de instâncias as melhores soluções incumbentes.

Depois de efectuada a análise geral dos resultados obtidos na resolução do conjunto das 180 instâncias, fez-se a análise dos resultados atendendo à variação dos quatro parâmetros das instâncias de teste. Nesta fase consideraram-se como medidas de desempenho os tempos médios de resolução do problema inteiro e os GAP’s médios de integralidade. Para o cálculo dos GAP’s de integralidade consideraram-se as 71 instâncias para as quais se obteve a solução óptima e consideraram-se os três métodos de resolução.

Para o cálculo dos tempos médios de resolução apenas se considerou a decomposição por artigo e o Cplex, que na decomposição por período não se obteve a solução óptima inteira de nenhuma das instâncias. No caso da decomposição por artigo utilizaram-se as 59 instâncias para as quais se obteve a solução óptima e para o Cplex, utilizaram-se as 61 instâncias que são resolvidas até à optimalidade com este método. Os resultados que se apresentam na tabela 3 e na tabela 4 referem-se a esta análise.

Da análise da tabela 3 verifica-se que quando a utilização de capacidade é alta, poucas instâncias que são resolvidas e que à medida que aumenta a utilização de capacidade o GAP quer da decomposição por período quer do Cplex baixa, sendo que em relação à decomposição por artigo à medida que aumenta a utilização de capacidade, também aumenta o GAP. O efeito no GAP, quando se varia a procura e quando se varia o tempo de preparação, não é significativo se se considerar a decomposição por período e o Cplex. Na decomposição por artigo as diferenças são mais acentuadas, verificando-se que a passagem de um nível para o nível imediatamente superior, leva a um aumento do GAP.

Em relação à variação na periodicidade de encomenda, pode dizer-se que à medida que aumenta a periodicidade de encomenda aumenta significativamente a dificuldade do problema, sendo esse aumento mais acentuado para a decomposição por período e para o Cplex. Esta análise pode ser baseada nas instâncias com periodicidade baixa e média, que em nenhuma das instâncias com periodicidade alta se conseguiu obter resultados.

Por último, salienta-se que relativamente aos GAP’s de integralidade em termos gerais o comportamento da decomposição por período e do Cplex é muito idêntico, face às variações nos parâmetros.

Na análise dos tempos de resolução do problema inteiro, deverá notar-se que os resultados apresentados na tabela 4 não dizem respeito exactamente às mesmas instâncias, pelo que as comparações que se apresentam de seguida poderão estar enviesadas. Idealmente deveriam considerar-se as mesmas instâncias, mas nesse caso a amostra seria relativamente baixa.

Quando a utilização de capacidade é alta, poucas instâncias que são resolvidas até à optimalidade e quando a periodicidade de encomenda é alta nenhum dos métodos consegue encontrar soluções óptimas inteiras. Verifica-se que os tempos médios de resolução aumentam significativamente quando se passa de uma utilização de capacidade baixa para média, assim como quando se passa da variabilidade da procura média para a alta e quando se passa da periodicidade de encomenda baixa para a média. Em termos gerais o desempenho da decomposição por artigo é idêntico ao do Cplex, sendo de realçar que nas instâncias com variabilidade da procura média e com periodicidade de encomenda média, os tempos médios de resolução são mais baixos na decomposição por artigo comparativamente com os tempos do Cplex.

6 Conclusões Neste artigo apresentaram-se e compararam-se dois algoritmos de partição e geração de colunas para a obtenção de soluções óptimas inteiras do problema de lotes de produção multi-artigo capacitado com tempos de preparação. Ambos os algoritmos baseiam-se na aplicação da decomposição de Dantzig-Wolfe a uma formulação de Programação Inteira Mista clássica para o problema. Num deles, os subproblemas estão associados a períodos e, no outro, os subproblemas estão associados aos artigos.

O modelo de decomposição por artigo permite obter intervalos de integralidade muito baixos, o que nos leva a considerar que existiriam vantagens em investir-se no aumento da eficiência deste modelo em abordagens futuras, nomeadamente ao nível do algoritmo de partição e geração de colunas. Certamente os tempos de resolução poderiam ser reduzidos através da implementação do algoritmo de programação dinâmica proposto por Wagner-Whitin, para resolver os subproblemas e através da implementação de heurísticas para a obtenção de soluções admissíveis de melhor qualidade, quer na raiz da árvore de pesquisa quer nos nodos da árvore.

Para a pesquisa de soluções inteiras propôs-se um esquema de partição baseado nas variáveis originais de preparação, no qual se adicionam restrições de partição ao problema mestre, garantindo-se deste modo a preservação da estrutura do subproblema.

Este esquema tem a vantagem de ser geral e de poder ser aplicado a qualquer tipo de problema de Programação Inteira ou de Programação Inteira Mista.

Os testes computacionais realizados mostraram que a decomposição por artigo tem um desempenho claramente superior ao da decomposição por período e que entre a decomposição por artigo e a formulação clássica resolvida pelo Cplex a vantagem da decomposição por artigo em termos de intervalos de integralidade é significativa. em termos de tempos de resolução ambos os métodos têm um desempenho similar, embora com o Cplex 8.1 se obtenham em média resultados um pouco melhores.


Download text