%% Antes de processar este arquivo LaTeX (LaTeX2e) deve %% verificar que o arquivo TEMA.cls estah no mesmo %% diretorio. O arquivo TEMA.cls pode ser obtido do %% endereco www.sbmac.org.br/tema. \documentclass{TEMA} \usepackage[brazil]{babel} % para texto em Português %\usepackage[english]{babel} % para texto em Inglês \usepackage[latin1]{inputenc} % para acentuação em Português %\input{P-margin.inf} \usepackage[dvips]{graphics} \usepackage{subfigure} \usepackage{graphicx} \usepackage{epsfig} \newcommand{\B}{{\tt\symbol{92}}} \newcommand{\til}{{\tt\symbol{126}}} \newcommand{\chap}{{\tt\symbol{94}}} \newcommand{\agud}{{\tt\symbol{13}}} \newcommand{\crav}{{\tt\symbol{18}}} \begin{document} %******************************************************** \title {Relaxação Lagrangiana Aplicada ao Problema de Dimensionamento de Lotes em Máquinas Paralelas: Limitantes Inferiores\thanks{Este trabalho teve o apoio financeiro da CAPES, CNPq e FAPESP; Os autores agradecem a professora Franklina M. B. Toledo, por fornecer o código computacional de seu método, bem como, as instâncias utilizadas;}} \author {D. J. Fiorotto% \thanks{diego\_fiorotto@hotmail.com;}\,, Departamento de Ciências de Computação e Estatística, IBILCE, UNESP - Univ Estadual Paulista, 15054-000 São José do Rio Preto, SP, Brasil \\ \\ S. A. Araujo% \thanks{saraujo@ibilce.unesp.br;}\,, Departamento de Ciências de Computação e Estatística, IBILCE, UNESP - Univ Estadual Paulista, 15054-000 São José do Rio Preto, SP, Brasil.} \criartitulo \runningheads {Fiorotto e Araujo}{Limitantes Inferiores para Dimensionamento de Lotes} \begin{abstract} {\bf Resumo}. Este trabalho aborda o problema de dimensionamento de lotes monoestágio em um ambiente com máquinas paralelas distintas. Cada item pode ser produzido em qualquer máquina, acarretando um tempo de preparação que é gasto antes de começar a produção. O objetivo do trabalho consiste em obter li-\linebreak mitantes inferiores de boa qualidade para este problema. Para tanto, é desenvolvido um método de solução baseado numa reformulação do problema e na relaxação Lagrangiana de um conjunto de restrições. Alguns resultados computacionais são apresentados comparando o método proposto com um trabalho da literatura e com um pacote computacional. {\bf Palavras-chave}. Dimensionamento de Lotes, Máquinas Paralelas, Limitantes Inferiores. \end{abstract} %******************************************************** \newsec{Introdução} O problema de dimensionamento de lotes é um problema de otimização da produção, em que o objetivo é planejar a quantidade de itens a ser produzida em várias, ou única, máquinas em cada período ao longo de um horizonte de tempo, de modo a atender uma demanda e otimizar uma função objetivo. O problema estudado neste trabalho, envolve o planejamento da produção de múltiplos itens em um único estágio composto de máquinas paralelas distintas com capacidade limitada. Os itens podem ser produzidos em qualquer uma das máquinas e para iniciar a produção de um item decorre-se um tempo de preparação da máquina utilizada. A intenção deste trabalho é encontrar bons limites inferiores para este problema, para tanto uma reformulação é proposta e os limites inferiores são gerados com relaxação Lagrangiana, de tal maneira que, diferente da maioria dos trabalhos que utilizam a decomposição tradicional, ou seja, por itens, utiliza-se a decomposição por períodos para uma reformulação do problema seguindo as idéias de \cite{Jans2004} que fazem o mesmo para o caso com uma máquina. Cabe ressaltar a importância de se estudar e obter bons limites inferiores para estes problemas devido sua grande complexidade computacional, pondendo assim, diminuir consideravelmente os tempos e as árvores de solução dos algoritmos exatos. \newsec{Formulações do Problema} Inicialmente apresenta-se a formulação clássica, estudada em \cite{Toledo2006} e em seguida a reformulação proposta. Para a Formulação Matemática do problema considere os seguintes dados:\\ $d_{it}$: demanda do item \emph{i} no período \emph{t};\\ $sd_{itk}$: soma da demanda do item \emph{i}, do período \emph{t} até o período \emph{k};\\ $hc_{it}$: custo unitário de estoque do item \emph{i} no período \emph{t};\\ $sc_{ijt}$: custo de preparo do item \emph{i} na máquina \emph{j} no período \emph{t};\\ $vc_{ijt}$: custo de produção do item \emph{i} na máquina \emph{j} no período \emph{t};\\ $fc_i$: custo unitário de estoque inicial para o item \emph{i};\\ $st_{ijt}$: tempo de preparo do item \emph{i} na máquina \emph{j} no período \emph{t};\\ $vt_{ijt}$: tempo de produção do item \emph{i} na máquina \emph{j} no período \emph{t};\\ $Cap_{jt}$: capacidade da máquina \emph{j} no período \emph{t}.\\ Variáveis de decisão:\\ $x_{ijt}$: unidades produzidas do item \emph{i} na máquina \emph{j} no período \emph{t};\\ $y_{ijt}$: variável binária, indicando a produção ou não do item \emph{i} na máquina \emph{j} no período \emph{t};\\ $s_{it}$: estoque do item \emph{i} no final do período \emph{t};\\ $s_{i0}$: quantidade de estoque inicial para o item \emph{i}.\\ Formulação matemática: \begin{eqnarray}\label{objetivo} \displaystyle\hspace{0cm}Min\displaystyle\sum_{i=1}^nfc_is_{i0}+ \displaystyle\sum_{i=1}^n\sum_{j=1}^r\sum_{t=1}^m(sc_{ijt}y_{ijt}+vc_{ijt}x_{ijt})+\displaystyle\sum_{i=1}^n\sum_{t=1}^mhc_{it}s_{it}\hspace{0.2cm}\end{eqnarray} \hspace{0.8cm}Sujeito a :\vspace*{0.1cm} \begin{eqnarray} &s_{i,t-1}+\displaystyle\sum_{j=1}^kx_{ijt}=d_{it}+s_{it} \hspace{4.8cm} \forall{i\in I, t\in T}& \label{balanceament}\\ &x_{ijt}\leq sd_{itm}y_{ijt}\hspace{5.5cm} \forall{i\in I,j\in J, t\in T}&\label{prepara} \\ &\displaystyle\sum_{i=1}^n(st_{ijt}y_{ijt}+vt_{ijt}x_{ijt})\leq Cap_{jt}\hspace{3.7cm}\forall{j\in J, t\in T}&\label{capacidadee}\\ &y_{ijt}\in \{0,1\},\hspace{0.15cm} x_{ijt}\geq0,\hspace{0.15cm} s_{it}\geq{0},\hspace{0.15cm} s_{i0}\geq0,\hspace{0.15cm} s_{im}=0 \hspace{0.3cm} \forall{i\in I,j\in J,t\in T}\label{integralidade}& \end{eqnarray} A função objetivo (\ref{objetivo}) minimiza os custos totais de preparação, produção, estoque e estoque inicial. As restrições (\ref{balanceament}) garantem o balanceamento de estoque. Para evitar problemas infactíveis o modelo considera a possibilidade de estoque inicial, contudo o custo $fc_i$ para este estoque é muito grande, assim $s_{i0}$ terá valor diferente de zero apenas quando o problema não tiver solução factível \cite{Vanderbeck1998}. Em seguida, temos as restrições de preparação de máquina (\ref{prepara}) e as limitações de capacidade (\ref{capacidadee}). Finalmente, em (\ref{integralidade}) tem-se a definição dos domínios das variáveis. Este problema pode ser reformulado usando a abordagem de redefinição das variáveis proposta por \cite{Eppen1987}, originando numa formulação baseada no problema de caminho mínimo. A motivação para estudar esta abordagem decorre dos resultados obtidos por \cite{Jans2004} que mostram que para o problema de dimensionamento em uma máquina os limites inferiores resultantes da decomposição por períodos utilizando esta reformulação são melhores que os obtidos utilizando a decomposição por item da formulação clássica. Para a reformulação defina os seguintes parâmetros: $cv_{ijtk}$: custo de produção e estoque para produzir o item $\emph{i}$, na máquina \emph{$j$} no período $\emph{t}$ para satisfazer a demanda dos períodos $\emph{t}$ até $\emph{k}$ $$=vc_{ijt}sd_{itk}+\displaystyle\sum_{s=t+1}^k\sum_{u=t}^{s-1}hc_{iu}d_{is}$$ $ci_{it}$: custo para que o estoque inicial do item $\emph{i}$ satisfaça a demanda dos períodos $1$ até o período $\emph{t}$ $$=fc_isd_{i1t} + \displaystyle\sum_{s=2}^t\sum_{u=1}^{s-1}hc_{iu}d_{is}$$ Tem-se também as seguintes novas variáveis para o modelo: $zv_{ijtk}$: fração do plano de produção do item $\emph{i}$ na máquina \emph{$j$}, em que a produção no período $\emph{t}$ satisfaz a demanda do período $\emph{t}$ até o período $\emph{k}$ $w_{it}$: fração do plano de estoque inicial do item $\emph{i}$ em que a demanda é satisfeita para os primeiros $\emph{t}$ períodos Então, a reformulação baseada no problema do caminho mínimo é a seguinte: \begin{eqnarray}\label{obj} \displaystyle\hspace{0cm}Min\displaystyle\sum_{i=1}^n\sum_{t=1}^mci_{it}w_{it}+ \displaystyle\sum_{i=1}^n\sum_{j=1}^r\sum_{t=1}^msc_{ijt}y_{ijt}+\displaystyle\sum_{i=1}^n\sum_{j=1}^r\sum_{t=1}^m\sum_{k=t}^mcv_{ijtk}zv_{ijtk}\end{eqnarray} \hspace{0.8cm}Sujeito a :\vspace*{0.1cm} \begin{eqnarray} &1=\displaystyle\sum_{k=1}^mw_{ik}+\displaystyle\sum_{j=1}^r\sum_{k=1}^mzv_{ij1k}\hspace{5.3cm} \forall{i\in I}& \label{primeira}\\ &w_{i,t-1}+\displaystyle\sum_{j=1}^r\sum_{k=1}^{t-1}zv_{i,j,k,t-1}=\displaystyle\sum_{j=1}^r\sum_{k=t}^mzv_{ijtk}\hspace{1.6cm} \forall{i\in I,t\in T}/ \{1\}&\label{segunda} \\ &\displaystyle\sum_{k=t}^mzv_{ijtk}\leq y_{ijt}\hspace{5.5cm}\forall{i\in I,j\in J,t\in T}&\label{terceira}\\ &\displaystyle\sum_{i=1}^nst_{ijt}y_{ijt}+\displaystyle\sum_{i=1}^n\sum_{k=t}^mvt_{ijt}sd_{itk}zv_{ijtk}\leq Cap_{jt}\hspace{1 cm}\forall{i\in I,j\in J,t\in T}&\label{quarta}\\ &y_{ijt}\in \{0,1\},\quad w_{it}\geq0 \hspace{5.3cm}\forall{i\in I,j\in J}\label{quinta}&\\ &zv_{ijtk}\geq0 \hspace{4.2cm}\forall{i\in I,j\in J,t\in T}\hspace{0.2cm}\forall{k\in T},k\geq t\label{sexta }& \end{eqnarray} A função objetivo (\ref{obj}) minimiza a soma dos custos de estoque inicial, preparação, produção e custos de estocagem. As restriçãoes (\ref{primeira}) e (\ref{segunda}) definem as restrições de fluxo para a rede de caminho mínimo. Para cada produto, uma unidade de fluxo é enviada à rede, impondo que a demanda de cada produto tem que ser satisfeita sem atraso. As restrições (\ref{terceira}) forçam a preparação para cada item a ser produzido. As restrições de capacidade (\ref{quarta}) limitam a soma total dos tempos de preparação e produção pela capacidade disponível em cada período e em cada máquina. As restrições $(2.27)$ e $(2.28)$ definem o domínio das variáveis. %******************************************************** \newsec{Relaxação Lagrangiana Aplicada as Restrições de Fluxo} %\setcounter{equation}{0} Nesta seção apresenta-se uma relaxação Lagrangiana baseada em \cite{Jans2004}, em que con-\linebreak sidera-se o modelo $(2.6)-(2.12)$ e as restrições de fluxo $(2.7)$ e $(2.8)$ são dualizadas na função objetivo. O problema se decompõe em subproblemas independentes, por períodos e por máquinas e contém as restrições de capacidade, preparação e as condições de integralidade. Assim, os pontos extremos representam planos de produção a cada período e para cada máquina, ou seja, o número de subproblemas está vinculado ao número total de períodos e de máquinas. Todos esses planos de produção são factíveis em relação as restrições de capacidade. Além de \cite{Jans2004} que consideram o problema com uma única máquina, \cite{Diaby1992} testam esta decomposição por períodos, considerando a formulação clássica em que também se tem uma única máquina. De seus testes computacionais, concluíram que a decomposição por item é superior à decomposição por período para esta formulação, \cite{Pimentel2010} também fazem tal análise para a formulação clássica e chegam a mesma conclusão. Ainda para o problema com única máquina, esta decomposição é discutida, sem testes computacionais, para o problema de dimensionamento de lotes sem tempos de preparação em \cite{Chen1990}, neste trabalho prova-se que o limitante inferior obtido pela decomposição por períodos para uma reformulação da formulação clássica é melhor que o obtido pela decomposição por itens da formulação clássica. \cite{Sural2009} também testam a decomposição por períodos para o caso sem custo de preparação e assim como \cite{Jans2004} consideram uma reformulação do modelo clássico e chegam a conclusão de que a decomposição por períodos é superior à decomposição por itens. Deve-se observar que não encontramos na literatura nenhum trabalho que considera tal reformulação e a decomposição por períodos para o caso de máquinas paralelas. Na relaxação Lagrangiana as restrições (\ref{primeira}) e (\ref{segunda}) são dualizadas na função objetivo (\ref{obj}) com multiplicadores lagrangianos $p_{it}$. \begin{eqnarray}\label{rela} &\displaystyle\hspace{-0cm}Min\displaystyle\sum_{i=1}^n\sum_{t=1}^mci_{it}w_{it}+ \displaystyle\sum_{i=1}^n\sum_{j=1}^r\sum_{t=1}^msc_{ijt}y_{ijt}+\displaystyle\sum_{i=1}^n\sum_{j=1}^r\sum_{t=1}^m\sum_{k=t}^mcv_{ijtk}zv_{ijtk}-\hspace{0.5cm}&\nonumber\\ &-\displaystyle\sum_{i=1}^np_{i1}(\displaystyle\sum_{k=1}^mw_{ik}+\displaystyle\sum_{j=1}^r\sum_{k=1}^mzv_{ij1k}-1)-\nonumber&\\ &\hspace{0cm}-\displaystyle\sum_{i=1}^n\sum_{t=2}^mp_{it}(\displaystyle\sum_{j=1}^r\sum_{k=t}^mzv_{ijtk}-w_{i,t-1}-\displaystyle\sum_{j=1}^r\sum_{k=1}^{t-1}zv_{ijk,t-1})&\end{eqnarray} Após reorganizar os termos da função objetivo, o problema de Lagrange torna-se: \begin{eqnarray}\label{rel} &\displaystyle\hspace{-2.4cm}Min\displaystyle\sum_{i=1}^n\sum_{j=1}^r\sum_{t=1}^msc_{ijt}y_{ijt}+\displaystyle\sum_{i=1}^n\sum_{t=1}^{m-1}(ci_{it}- p_{i,1}+p_{i,t+1})w_{it}+&\nonumber\\ &\hspace{0.6cm}+\displaystyle\sum_{i=1}^n(ci_{im}-p_{i,1})w_{im}+\displaystyle\sum_{i=1}^n\sum_{j=1}^r\sum_{t=1}^m\sum_{k=t}^{m-1}(cv_{ijtk}-p_{it}+ p_{i,k+1})zv_{ijtk}+&\nonumber\\ &\hspace{3.4cm}+\displaystyle\sum_{i=1}^n\sum_{j=1}^r\sum_{t=1}^m(cv_{ijtm}-p_{it})zv_{ijtm}+\displaystyle\sum_{i=1}^np_{i1}\hspace{0.1cm}&\end{eqnarray} \hspace{0.8cm}Sujeito a :\vspace*{0.1cm} \begin{eqnarray} &\displaystyle\sum_{k=t}^mzv_{ijtk}\leq y_{ijt}\hspace{5.5cm}\forall{i\in I,j\in J, t\in T }&\label{te}\\ &\displaystyle\sum_{i=1}^nst_{ijt}y_{ijt}+\displaystyle\sum_{i=1}^n\sum_{k=t}^mvt_{ijt}sd_{itk}zv_{ijtk}\leq Cap_{jt}\hspace{1.9cm}\forall{j\in J, t\in T }&\label{qu}\\ &y_{ijt}\in \{0,1\},\quad w_{it}\geq0 \hspace{4.4cm}\forall{i\in I,j\in J, t\in T }\label{qui}&\\ &zv_{ijtk}\geq0 \hspace{4.1cm}\forall{i\in I,j\in J, t\in T }\hspace{0.2cm}\forall{k\in T},k\geq t\label{se}& \end{eqnarray} O problema pode ser decomposto em subproblemas independentes para cada período \emph{$t$} e cada máquina \emph{j}. Estes subproblemas podem ser resolvidos pelo método \emph{branch-and-bound} proposto por \cite{Jans2004}. O problema Lagrangiano é resolvido durante algumas iterações e os multiplicadores Lagrangianos $p_{it}$ são atualizados pelo método de otimização do subgradiente (\cite{Held1974} e \cite{Camerini1975}). Para iniciar o método, fixamos as variáveis duais em zero ($p_{it}^0=0$) e o tamanho do passo na direção do subgradiente é proporcional a um parâmetro $\alpha$, que deve decrescer com o número de iterações e a regra utilizada para gerar uma sequência decrescente para $\alpha$ é caracterizada pelos parâmetros $(\alpha_0,r_0,d)$. Os valores de $\alpha$ são obtidos fazendo $\alpha=\alpha_0$ e é diminuido progressivamente multiplicando-o por um parâmetro $d$, se a solução Lagrangiana não for melhorada nas últimas $r=r_0$ iterações. Os valores utilizados para os parâmetros são $(1,50,0.6)$ e são realizadas 2500 iterações do método. Ainda para o método do subgradiente, foi desenvolvida uma heurística para a obtenção de um limite superior (solução factível) utilizado na atualização do tamanho do passo. Para tanto, as ideias apresentadas em \cite{Thizy1985} foram estendidas e adaptadas para o problema em questão. A heurística consiste nos seguintes passos: \begin{enumerate} \item Para uma dada iteração, utilizar o plano de preparação (variáveis $y_{ijt}$) que é obtido ao resolver os subproblemas, indicando se há ou não preparação de determinado item \emph{i} na máquina \emph{j} em um período \emph{t}. Observe que este plano será factível no que diz respeito as restrições de capacidade. \item Com as variáveis $y_{ijt}$ fixadas, resolver o problema de fluxo de redes para a primeira máquina. \item Subtrair da demanda total a demanda satisfeita com a primeira máquina e resolver um novo problema de fluxo de redes para a próxima máquina. Fazer este procedimento até a última máquina. \item Para a última máquina somar ao valor total as quantidades de produção, estoque inicial (se necessário) e estoque. Este valor por sua vez gera uma solução factível (limite superior) para o problema original. \end{enumerate} \newsec{Resultados Computacionais} O procedimento descrito na seção anterior, denotado $FA$, foi testado em um total de 2880 instâncias porpostas em \cite{Toledo2006}. Foram feitas comparações com o pacote CPLEX 12.2 e com o método proposto por Toledo e Armentano \cite{Toledo2006}, denotado aqui por $TA$. Todos os testes foram realizados em um microcomputador AMD Turion 1.8 GHz com 3 GB de memória RAM e sistema operacional Windows XP. As 2880 instâncias são divididas em 8 tipos diferentes de classes que são ge-\linebreak radas com valores altos e baixos para os custos de preparação (SA ou SB) e para tempos de preparação (TA ou TB) e com capacidades normal e apertada (CN ou CA). Portanto, a classe CNSBTB, por exemplo, refere-se a instâncias com capacidade normal, custos de preparação baixos e tempos de preparação baixos. A notação para as demais classes seguem esse mesmo raciocínio. Ainda, são geradas 10 instâncias para cada classe e configuração de número de máquinas $(r = 2, 4, 6)$, itens $(n = 6, 12, 25, 50)$ e períodos $(m = 6, 12, 18)$. Os parâmetros foram gerados em intervalos $[a,b]$ com distribuição uniforme e denotado $U[a,b]$: \begin{itemize} \item custo de produção ($vc_{ij}$) U[1.5,2.5] \item custo de preparação ($sc_{ij}$) U[5.0,95.0] \item custo de estoque ($hc_i$) U[0.2,0.4] \item tempo de produção ($vt_{ij}$) U[1.0,5.0] \item tempo de preparação ($st_{ij}$) U[10.0,50.0] \item demanda ($d_{it}$) U[0,180] \end{itemize} Para gerar exemplares com custos de preparação alto multiplica-se os custos gerados por $10$, da mesma forma, para gerar exemplares com tempos de preparação alto multiplica-se estes por $1.5$. A capacidade também foi gerada de acordo com \cite{Toledo2006}, ou seja, toma-se como base a capacidade necessária para produzir os itens de acordo com a política lote-por-lote. Posteriormente aplica-se um ajuste para reduzir a capacidade afim de gerar instâncias com a utilização da capacidade em torno de $80\%$. A capacidade apertada é obtida multiplicando a capacidade gerada por $0.9$. Para avaliar a qualidade dos limites inferiores os \emph{GAPS} serão calculados da seguinte forma: $$\emph{Gap}=\frac{z_{CPLEX}-z_{LI}}{z_{LI}}*100$$ onde: $z_{CPLEX}$ é o valor da solução encontrada pelo CPLEX; $z_{LI}$ limite inferior obtido pelo próprio CPLEX ou pelos métodos $TA$ e $FA$ com a relaxação Lagrangiana; Observe que utiliza-se o limite superior obtido pelo CPLEX pois, o foco do trabalho está na qualidade dos limitantes inferiores. Poderíamos também, fazer uma comparação entre os limitantes superiores obtidos. No entanto, no atual momento da pesquisa, os limitantes obtidos pelo método proposto não são de boa qualidade. A Tabela \ref{t10} apresenta a quantidade de instâncias para cada configuração, número de períodos, máquinas e itens que o CPLEX 12.2 provou a otimalidade no tempo máximo de dois minutos para cada instância, o que permite analisar a dificuldade em se obter soluções para os problemas conforme suas características. Observa-se que para problemas com 6 períodos o CPLEX provou a otimalidade para quase todas as instâncias, por outro lado, para os problemas com 18 períodos, na maioria dos casos o \emph{solver} não provou a otimalidade em nenhum dos exemplos. Verifica-se ainda um aumento considerável na dificuldade dos problemas quando aumenta-se os custos de preparação. \begin{table}[htbp] \tiny \centering \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|} \hline m & r & n & CNSBTB & CNSATB & CNSBTA & CNSATA & CASBTB & CASATB & CASBTA & CASATA \\ \hline & & 6 & 10 & 10 & 10 & 10 & 10 & 10 & 10 & 10 \\ & 2 & 12 & 10 & 10 & 10 & 10 & 10 & 10 & 10 & 10 \\ & & 25 & 10 & 10 & 10 & 10 & 10 & 10 & 10 & 9 \\ & & 50 & 10 & 8 & 10 & 7 & 10 & 3 & 10 & 2 \\ \cline{2-11} & & 6 & 10 & 10 & 10 & 10 & 10 & 10 & 10 & 10 \\ 6 & 4 & 12 & 10 & 10 & 10 & 10 & 10 & 8 & 10 & 9 \\ & & 25 & 10 & 8 & 10 & 8 & 10 & 5 & 10 & 4 \\ & & 50 & 10 & 3 & 10 & 4 & 10 & 0 & 9 & 0 \\ \cline{2-11} & & 6 & 10 & 9 & 10 & 8 & 10 & 9 & 10 & 8 \\ & 6 & 12 & 10 & 7 & 10 & 6 & 10 & 5 & 10 & 5 \\ & & 25 & 10 & 8 & 10 & 7 & 10 & 4 & 10 & 4 \\ & & 50 & 10 & 3 & 10 & 4 & 10 & 1 & 10 & 1 \\ \hline & & 6 & 10 & 8 & 10 & 6 & 10 & 5 & 9 & 5 \\ & 2 & 12 & 10 & 6 & 9 & 5 & 9 & 5 & 8 & 5 \\ & & 25 & 9 & 3 & 9 & 0 & 8 & 0 & 7 & 0 \\ & & 50 & 10 & 0 & 10 & 0 & 7 & 0 & 7 & 0 \\ \cline{2-11} & & 6 & 8 & 0 & 8 & 0 & 7 & 1 & 5 & 0 \\ 12 & 4 & 12 & 8 & 2 & 8 & 2 & 6 & 3 & 7 & 2 \\ & & 25 & 10 & 1 & 10 & 2 & 8 & 0 & 7 & 0 \\ & & 50 & 10 & 1 & 10 & 1 & 8 & 1 & 7 & 0 \\ \cline{2-11} & & 6 & 5 & 0 & 3 & 0 & 1 & 0 & 1 & 0 \\ & 6 & 12 & 8 & 0 & 7 & 0 & 6 & 0 & 6 & 0 \\ & & 25 & 10 & 0 & 9 & 0 & 6 & 0 & 8 & 0 \\ & & 50 & 10 & 0 & 10 & 0 & 9 & 0 & 10 & 0 \\ \hline & & 6 & 8 & 1 & 7 & 1 & 6 & 1 & 7 & 1 \\ & 2 & 12 & 8 & 2 & 7 & 2 & 6 & 0 & 3 & 1 \\ & & 25 & 5 & 0 & 5 & 0 & 3 & 0 & 3 & 0 \\ & & 50 & 9 & 0 & 8 & 0 & 6 & 0 & 6 & 0 \\ \cline{2-11} & & 6 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 18 & 4 & 12 & 4 & 1 & 3 & 0 & 1 & 0 & 0 & 0 \\ & & 25 & 7 & 0 & 5 & 0 & 4 & 0 & 3 & 0 \\ & & 50 & 10 & 0 & 8 & 0 & 6 & 0 & 6 & 0 \\ \cline{2-11} & & 6 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ & 6 & 12 & 5 & 0 & 4 & 0 & 3 & 0 & 3 & 0 \\ & & 25 & 8 & 0 & 7 & 0 & 4 & 0 & 4 & 0 \\ & & 50 & 10 & 0 & 9 & 0 & 8 & 0 & 6 & 0 \\ \hline \end{tabular} \caption{Número de soluções ótima encontradas pelo CPLEX} \label{t10} \end{table} Por conta do grande número de instâncias que o CPLEX provou a otimilidade para os problemas com 6 e 12 períodos, apresentaremos nas comparações entre os limites inferiores apenas as configurações com 18 períodos, pois nestes casos o \emph{solver} apresenta grandes dificuldades e não consegue provar a otimalidade para a maioria das instâncias. Contudo, cabe observar que para todas as instâncias com 6 e 12 períodos o método proposto ($FA$) obteve \emph{gaps} em média $39\%$ melhores que o método $TA$. Na Tabela \ref{t2ff} comparam-se os limites inferiores encontrados com o CPLEX no nó raiz depois de aplicar os cortes e após as ramificações, com os gerados pelos métodos $TA$ e $FA$ para os problemas com 18 períodos e capacidade normal. Os \emph{gaps} calculados para o CPLEX utilizam como limites inferiores os encontrados no nó raiz após a aplicação dos cortes. Os resultados evidênciam que a medida que o número de itens aumentam, os \emph{gaps} diminuem de forma significativa (sempre menores que $1\%$ para 25 e 50 itens). Observe que, apesar da razoável diferença entre os tempos computacionais (T(s)), o método proposto $FA$ encontrou, em praticamente todas as instâncias \emph{gaps} me-\linebreak lhores que o método $TA$. A notável diferença dos tempos computacionais entre os dois métodos explica-se pela dificuldade dos subproblemas, enquanto para o método $TA$ os subproblemas são problemas de dimensionamento de lotes com único item em máquinas paralelas sem restrição de capacidade, que são baratos computacionalmente, para o método $FA$ os subproblemas são problemas da mochila que são caros computacionalmente. Além disso, o método $FA$ necessita de um número maior de iterações do método do subgradiente para convergir. Pode-se observar ainda que enquanto o método $TA$ obtém resultados melhores que o CPLEX em apenas $6\%$ das instâncias, o proposto $FA$ supera o \emph{solver} em $81\%$, o que comprova a qualidade dos limites inferiores deste método. A Tabela \ref{t2ff} mostra ainda, que mesmo após as ramificações do CPLEX os limites inferiores encontrados com o método $FA$ são melhores na maioria das instâncias com 25 e 50 itens principalmente para as classes com custos de preparação altos (CNSATB e CNSATA). Portanto, se utilizarmos os limitantes inferiores gerados pelo método $FA$ no nó raiz do CPLEX, além de obtermos \emph{gaps} melhores, ajudariamos o \emph{solver} a fazer várias podas nas árvores de solução e a encontrar soluções factíveis melhores. \begin{table}[htb!] \footnotesize \centering \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \multicolumn{3}{|c}{}& \multicolumn{2}{|c|}{CPLEX (LI)}&\multicolumn{2}{|c|}{TA}&\multicolumn{2}{|c|}{FA}& \multicolumn{3}{c|}{Gaps}\\ \hline & r & n & cortes & ramif. & LI &T(s)& LI & T(s) & cplex & TA &FA \\ \hline & & 6 & 21928 &22024 & 21906 & 0,19 &21972&0,84& 0,50& 0,61&0,30\\ & 2 & 12 &42494 &43051 & 42979& 0,41&43034&1,83& 1,34& 0,20&0,07\\ & & 25 & 89204&89226 & 89199& 0,74&89219&4,19& 0,04& 0,05&0,02\\ & & 50 &176489 &176493 & 176479& 1,36&176461&6,90& 0,00& 0,01&0,02\\ \cline{2-12} & & 6 & 20096&20276 & 20022& 0,56&20238&1,36& 1,49& 1,86&0,77\\ CNSBTB & 4 & 12 &39822 &39905 & 39805 & 0,87&39891&2,59& 0,32& 0,36&0,14\\ & & 25 &80842 &80859 &80837 & 1,68&80862&4,99& 0,05& 0,05&0,02\\ & & 50 &162311 &162315 &162309& 3,23& 162318&9,58&0,01& 0,01&0,00\\ \cline{2-12} & & 6 & 19593&19792 & 19409& 0,97& 19775&1,85&2,17& 3,14&1,23\\ & 6 & 12 & 38335& 38400&38314& 1,58 & 38393&3,30&0,30& 0,35&0,14\\ & & 25 &78744 &78759 & 78735& 2,74&78753 &6,57 &0,05& 0,48&0,04\\ & & 50 &154664 &154664 & 154660& 5,28 &154678 &12,47 & 0,01& 0,04&0,00\\ \hline & & 6 & 33582 & 34491 & 33111& 0,35& 33152&0,91&6,07& 7,58&6,94\\ & 2 & 12 & 65356& 65812 & 65291& 0,55& 65687 &2,14& 1,11& 1,21&0,60\\ & & 25 & 135586& 135739 & 135641& 1,14&135861&6,67& 0,42& 0,38&0,22\\ & & 50 & 266756& 266803 & 266772& 2,53& 266953&16,09&0,12& 0,11&0,05\\ \cline{2-12} & & 6 &29363& 30138& 28672& 0,66& 28842&1,52& 10,09& 12,74&10,77\\ CNSATB & 4 & 12 & 57627& 58005& 57435& 1,15& 57725&2,94& 2,76&3,10&2,59\\ & & 25 & 116675& 116808& 116669& 2,12&116948&6,47& 0,45& 0,46&0,22\\ & & 50 & 234998& 235036& 234953& 4,25&235150&14,50& 0,13& 0,15&0,06\\ \cline{2-12} & & 6 & 28923& 29893& 28145& 1,29& 28642&2,21&14,83& 18,01&13,76\\ & 6 & 12 & 54574&54837& 54343& 2,02& 54967&3,73&3,45& 3,89&2,71\\ & & 25 & 112340& 112432&112245&3,70&112641&8,27&0,76& 0,85&0,49\\ & & 50 & 218904& 218940&218897&6,78&219053&15,54&0,11& 0,12&0,05\\ \hline & & 6 &21987 &22062 & 21925 & 0,21&21989&0,91&0,42 &0,71 &0,41\\ & 2 & 12 &43028 &43090 & 42957& 0,41&43074&4,44&0,19 &0,35 &0,08\\ & & 25 & 89240& 89265& 89236& 0,80&89261&12,34&0,04 &0,05 &0,02\\ & & 50 &176525 &176531 & 176519& 1,66&176510&20,10& 0,01&0,01 &0,02\\ \cline{2-12} & & 6 &20132 &20315 & 20045& 0,56&20278&1,40&1,54 &1,98 &0,80\\ CNSBTA & 4 & 12 &39843 &39933 &39826 & 0,92&39923&2,65&0,37 &0,41 &0,17\\ & & 25 &80858 &80887 &80854& 1,65&80879&5,10&0,05 &0,06 &0,03\\ & & 50 &162323 &162332 &162320& 3,37& 162332&10,30&0,01&0,01 &0,00\\ \cline{2-12} & & 6 &19620 &19830 &19421& 0,91& 19813&1,91&2,44&3,49 &01,44\\ & 6 & 12 &38347 &38417 &38326& 1,60& 38412&3,35&0,33&0,38 &0,16\\ & & 25 &78755 &78783 &78747& 2,83&78773&6,82&0,06&0,07 &0,03\\ & & 50 &154671 &154677 &154666&5,55&154686&12,94&0,01 &0,01 &0,00\\ \hline & & 6 &33704 &34582 & 33052& 0,36& 33217&0,96& 6,64& 8,75&8,21\\ & 2 & 12 &65555 &66033 & 65211& 0,59&65934&2,33& 1,15 & 1,68&0,57\\ & & 25 &135964 &136120 & 136028& 1,20&136275&6,94&0,44 & 0,40&0,21\\ & & 50 &267498 &267544 & 267502& 2,89& 267719&17,97&0,17& 0,17&0,09\\ \cline{2-12} & & 6 &29446&30301 & 28590& 0,69&28675&1,56&10,70 & 14,01&13,70\\ CNSATA & 4 & 12 &57718 &58081 &57331& 1,21&57650&3,06&2,75 &3,45&2,87\\ & & 25 &116794 &116929 &116796&2,18&117077&6,79&0,47 & 0,47&0,23\\ & & 50 &235303 &235342 &235190&4,47&235394&15,01&0,13 & 0,17&0,09\\ \cline{2-12} & & 6 &29021 &30044 &27828& 1,21&28365&2,23&17,56& 22,60&20,30\\ & 6 & 12 &54636 &54888 &54393& 2,06&55020&3,82&3,59& 4,05&2,87\\ & & 25 &112431 &112520 &112330&3,71&112735&8,43&0,78& 0,88&0,51\\ & & 50 &219012 &219050 &219011&6,93&219170&16,27&0,12& 0,12&0,05\\ \hline \end{tabular} \caption{Comparação entre limites inferiores para 18 períodos e capacidade normal} \label{t2ff} \end{table} A Tabela \ref{ff} ilustra os dados para todas as classes considerando a capacidade apertada, em que os\emph{ gaps} apresentam um aumento se comparados com a Tabela \ref{t2ff} e as diferenças entre a qualidade dos limitantes se tornam mais evidente sendo que em praticamente $50\%$ das configurações os \emph{gaps} encontrados pelo método $FA$ é menor que a metade dos encontrados pelo método $TA$. Assim como na Tabela \ref{t2ff}, para problemas com poucos itens os \emph{gaps} são maiores, sendo que os maiores \emph{gaps} em quase todos testes com 18 períodos foram encontrados para as configurações com 6 itens. Ainda como esperado, com o aumento do número de itens e máquinas os tempos computacionais também aumentam de forma significativa. \begin{table}[htb!] \footnotesize \centering \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \multicolumn{3}{|c}{}& \multicolumn{2}{|c|}{CPLEX (LI)}&\multicolumn{2}{|c|}{TA}&\multicolumn{2}{|c|}{FA}& \multicolumn{3}{c|}{Gaps}\\ \hline & r & n & cortes & ramif. & LI &T(s)& LI & T(s) & cplex & TA &FA \\ \hline & & 6 &22017 &22157 &21929 &0,25 &22088&0,94&0,80 &1,21 &0,48\\ & 2 & 12 & 43128 &43209 & 42925 & 0,50 &43173&2,04&0,24 &0,72 &0,14\\ & & 25 &89358 &89391 & 89356 & 1,00 &89381&5,05&0,07 &0,07 &0,05\\ & & 50 &176644 &176654 &176642& 1,94 &176608&9,71&0,02 &0,02 &0,04\\ \cline{2-12} & & 6 &20211 &20402 &20100 &0,57 &20373&1,45&1,88 &2,44 &1,07\\ CASBTB & 4 & 12 &39922 &40026 &39899 &1,06 &40028&2,76&0,51 &0,57 &0,24\\ & & 25 &80917 &80950 &80912 &1,83 &80945&5,41&0,07 &0,08 &0,04\\ & & 50 &162376 &162386&162374 &3,94 &162378&11,31&0,02 &0,02 &0,02\\ \cline{2-12} & & 6 &19698 &19924 &19461 &1,04 &19906&2,09&2,83 &4,08 &1,75\\ & 6 & 12 &38394 &38474 & 38365 & 1,76 &38479&3,48&0,38 &0,46 &0,16\\ & & 25 &78802 &78837 & 78789 & 3,22 &78830&6,97&0,10 &0,11 &0,06\\ & & 50 &154699 &154711 &154695 & 5,07 &154719&13,37&0,01 &0,02 &0,00\\ \hline & & 6 &34208 &35180 &33162 &0,43 &34099&1,09&8,26 & 11,67&8,60\\ & 2 & 12 &66199 &66689 &65735 &0,80 &66695&2,70&1,86 &2,58 &1,10\\ & & 25 &137216 &137370 &137249 &1,70 &137556&8,34&0,68 &0,65 &0,43\\ & & 50 &269829 &269861 &269851 &3,86 &269993&25,08&0,23 &0,23 &0,17\\ \cline{2-12} & & 6 &29716 &30671 &28713 &0,73 &29128&1,63&12,89 &16,83 &15,20\\ CASATB & 4 & 12 &58070 &58468 &57806 &1,37 &57826&3,21&3,62 &4,09 &4,06\\ & & 25 &117241 &117342 &117203 &2,54 &117536&7,44&0,70 &0,73 &0,45\\ & & 50 &235753 &235783 &235943 &4,96 &236140&17,43&0,26 &0,18 &0,10\\ \cline{2-12} & & 6 &29300 &30456 &28199 &1,20 &28213&2,30&19,59 &24,26 &24,20\\ & 6 & 12 &54903 &55153 &54601 &2,35 &55060&3,97&4,43 &5,01 &4,13\\ & & 25 &112765 &112842 &112632&4,24 &113158&8,87&1,198 &1,31 &0,84\\ & & 50 &219399 &219434 &219412 &7,19 &219605&17,68&0,25 &0,25 &0,16\\ \hline & & 6 &22084 &23239 & 21925 & 0,27&22173&1,01&5,43 &6,03 &5,00\\ & 2 & 12 &43185 &43273 & 42957& 0,54&43233&2,29&0,28 &0,83 &0,17\\ & & 25 &89427 &89459 & 89236& 1,42&89450&5,65&0,08 &0,20 &0,06\\ & & 50 &176735 &176745 & 176519& 2,21&176709&11&0,02 &0,02 &0,03\\ \cline{2-12} & & 6 &20256 &20449 & 20064& 0,61&20419&1,49&1,98 &2,96 &1,17\\ CASBTA & 4 & 12 &39957 &40046 &39933 & 1,08&40076&2,90&0,55 &0,61 &0,26\\ & & 25 &80944 &80981 &80941& 1,89&80981&5,72&0,09 &0,09 &0,04\\ & & 50 &162405 &162411 &162403& 3,92&162413 &12,14&0,02&0,02 &0,02\\ \cline{2-12} & & 6 &19728 &19984 &19372& 1,02&19972 &1,97&3,11&5,00 &1,85\\ & 6 & 12 &38413 &38494 &38382& 1,77&38505 &3,48&0,43&0,51 &0,19\\ & & 25 &78819 &78853 &78808& 3,17&78841&7,10&0,10& 0,12 &0,07\\ & & 50 &154711 &154716 &154708&6,13&154721&13,71&0,02 &0,02 &0,01\\ \hline & & 6 &34516& 36406&33262 &0,45 &34692 &1,14&11,55 &15,75 &10,98\\ & 2 & 12 & 66568& 67073 &65591 &0,84 &67104 &2,90&2,00 &3,52 &1,18\\ & & 25 & 137907& 138040 &136834 &1,84 &138268 &9,24& 0,68&1,47 &0,42\\ & & 50 & 271176& 271203 &271191 &4,39 &271186 &27,47&0,24 &0,23 &0,23\\ \cline{2-12} & & 6 & 29851& 31388 &28630 &0,73 &29060 &1,67&13,64 &18,49 &16,75\\ CASATA & 4 & 12 & 58216& 58566 &57127 &1,41 &57976 &3,41&3,96 &5,95 &4,40\\ & & 25 & 117409& 117513 &117377&2,60 &117724 &7,70&0,68 &0,71 &0,42\\ & & 50 & 236069& 236100 &235889 &5,18 &236487 &18,83&0,28 &0,36 &0,10\\ \cline{2-12} & & 6 & 29425& 30618 &28207 &1,29 &28264 &2,36&20,71 &25,92 &25,67\\ & 6 & 12 & 54979&55243 &54668 &2,38 &54998 &4,05&5,47 &6,07 &5,43\\ & & 25 & 112879& 112941 &112751 &4,29 &113293 &9,07&1,27 &1,39 &0,90\\ & & 50 & 219561&219595 &219572 &7,34 &219781 &18,11&0,28 & 0,28&0,18\\ \hline \end{tabular} \caption{Comparação entre limites inferiores para 18 períodos e capacidade apertada} \label{ff} \end{table} \newsec{Conclusões e Propostas Futuras} Neste trabalho foi estudado um problema de dimensionamento de lotes com \linebreak restrições de capacidade em máquinas paralelas. O trabalho foi inspirado em \cite{Jans2004}, em que os autores analisam os limites inferiores do problema de dimensionamento de lotes com uma máquina utilizando a relaxação Lagrangiana. \cite{Jans2004} propõem uma reformulação para o problema utilizando a ideia de redefinição de variáveis proposta por \cite{Eppen1987} e relaxam as restrições de demanda do problema, propondo assim uma decomposição por períodos ao invés da decomposição clássica por itens e encontram limites inferiores melhores comparados com a decomposição clássica. Outros autores, tais como, \cite{Chen1990} e \cite{Sural2009} já haviam analisado procedimentos semelhantes para o caso de única máquina. A ideia foi estendida, no presente trabalho, considerando um ambiente com máquinas paralelas. Foi utilizada a mesma ideia de redefinição de variáveis proposta por \cite{Eppen1987} e foi proposta uma reformulação para o problema com máquinas paralelas. Os limites inferiores foram gerados utilizando a decomposição por períodos e comparados com os limites inferiores encontrados por \cite{Toledo2006} que utilizaram a decomposição clássica por itens. Os limitantes foram testados para diferentes tipos de problemas e os resultados foram comparados utilizando como limite superior, soluções encontradas pelo pacote de otimização CPLEX 12.2. A formulação proposta encontrou em todos os testes limites inferiores melhores do que os gerados pela decomposição clássica apesar dos tempos computacionais serem maiores, pois, enquanto na decomposição proposta tem-se que resolver problemas da mochila como subproblemas, na decomposição clássica tem-se problemas de dimensionamento de lotes com único item sem restrição de capacidade que são baratos computacionalmente. Tendo em vista estender o trabalho, bem como, melhorar os resultados computacionais tem-se como próximos passos a melhoria da heurística desenvolvida neste trabalho. Ideias clássicas da literatura que envolvem a transferência de lotes podem ser utilizadas, tais como, as heurísticas de eliminação de lotes proposta em \cite{Degreave2007}. \begin{abstract} {\bf Abstract}. This paper addresses the single stage lot-sizing problem in parallel machines. Each item can be produced on any machine, and incur a setup time before to start the production. The objective of this paper is to obtain lower bounds of good quality for this problem. A solution method is developed based on a reformulation of the problem and the Lagrangian relaxation of a set of constraints. Some computational results are presented comparing the proposed method with a method from the literature and with a computational package. \end{abstract}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{thebibliography}{8} %\bibitem{CLBG} C.S.Q. Caldas, J. Limaco, R.K. Barreto, P. Gamboa, About the %Benjamin-Bona-Mahony equation in domains with moving boundary, %{\em TEMA - Tend. Mat. Apl. Comput.}, {\bf 8}, No. 3 (2007), 329--339. \bibitem{Camerini1975} P. M. Camerini, L. Fratta, F. Maffiole, On Improving Relaxation Methods by Modified Gradient Techniques, {\em Mathematical Programming Study}, {\bf 3} (1975), 26--54. \bibitem{Chen1990} W. H. Chen, J. M. Thizy, Analysis of relaxation for the multi- item capacitated lot-sizing problem, {\em Operations Research}, {\bf 26} (1990), 29--72. \bibitem{Degreave2007} Z. Degraeve, R. Jans, A new dantzig-wolfe reformulation and branch-and-price algorithm for the capacited lot-sizing problem with setup times, {\em Operational Research}, {\bf 55} (2007), 909--920. \bibitem{Diaby1992} M. Diaby, H. Bahl, M. H. Karwan, S. Ziont, Capacitated lot-sizing and scheduling by lagrangean relaxation, {\em European Journal Of Operational Research}, {\bf 59} (1992), 444--458. \bibitem{Eppen1987} G. B. Eppen, R. K. Martin, Solving Multi-Item Capacitated Lot-Sizing Problems Using Variable Redefinition, {\em Operations Research}, {\bf 6} (1987), 832--848. \bibitem{Held1974} M. Held, P. Wolfe, H. P. Crowder, Validation of Subgradient Optimization, {\em Mathematical Programming}, {\bf 6} (1974), 62--88. \bibitem{Jans2004} R. Jans, Z. Degraeve, Improved lower bounds for capacitated lot sizing problem with setup time, {\em Operation Research Letters}, {\bf 32} (2004), 185--195. \bibitem{Pimentel2010} C. M. O. Pimentel, F. P. Alvelos, J. M. V. Carvalho, Comparing Dantzig-Wolfe decompositions and branch-and-price algorithms for the multi-item capacitated lot sizing problem, {\em Optimization Methods and Software}, {\bf 25} (2010), 229--319. \bibitem{Sural2009} H. Sural, M. Denizel, L. N. van Wassenhove, Lagrangean relaxation based heuristic for lot sizing with setup times, {\em European Journal of Operational Research}, {\bf 195} (2009), 51--63. \bibitem{Thizy1985} J. M. Thizy, L. N. V. Wassenhove, Lagrangean relaxation for the multi-item capacitated lot-sizing problem: A heuristic implementation, {\em AIIE Transactions}, {\bf 17} (1985), 64-74. \bibitem{Toledo2006} F. M. B. Toledo, V. A. Armentano, A Lagrangian-Based Heuristic for the Capacitated Lot-Sizing Problem in Parallel Machines, {\em European Journal of Operational Research}, {\bf 175} (2006), 1070--1083. \bibitem{Vanderbeck1998} F. Vanderbeck, Lot-sizing with start-up times, {\em Management Science}, {\bf 44} (1998), 1409--1425. \end{thebibliography} \end{document} \newpage $ \ \ $ \thispagestyle{myheadings} \markboth{ }{ }