Um refinamento do algoritmo tabu de Dowsland para o problema de carregamento de paletes do produtor A refinement of Dowsland's tabu search algorithm for the manufacturer's pallet loading problem
O Problema de Carregamento de Paletes do Produtor consiste em arranjar, ortogonalmente e sem sobreposição, o máximo número de caixas retangulares idênticas de dimensões (l,w) sobre um palete (L,W). Este problema vem sendo tratado com sucesso por heurísticas de blocos, as quais constroem padrões de c...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Associação Brasileira de Engenharia de Produção (ABEPRO)
2003-01-01
|
| Series: | Production |
| Subjects: | |
| Online Access: | http://www.scielo.br/scielo.php?script=sci_arttext&pid=S0103-65132003000300002 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849467403778392064 |
|---|---|
| author | Cintia A. Yamassaki Vitória Pureza |
| author_facet | Cintia A. Yamassaki Vitória Pureza |
| author_sort | Cintia A. Yamassaki |
| collection | DOAJ |
| description | O Problema de Carregamento de Paletes do Produtor consiste em arranjar, ortogonalmente e sem sobreposição, o máximo número de caixas retangulares idênticas de dimensões (l,w) sobre um palete (L,W). Este problema vem sendo tratado com sucesso por heurísticas de blocos, as quais constroem padrões de carregamento com um ou mais blocos, cujas caixas possuem a mesma orientação. Os arranjos gerados por estes métodos estão limitados aos chamados padrões não-guilhotinados de primeira ordem. Neste trabalho, foi elaborada uma implementação baseada no algoritmo de busca tabu de Dowsland, que, ao contrário das heurísticas de blocos, provê arranjos não limitados a padrões particulares de empacotamento. Experimentos computacionais com um conjunto de 34 exemplos extraídos da literatura e de contextos reais indicam que a abordagem é capaz de resolver otimamente a maioria dos exemplos; para os exemplos não resolvidos, é proposto um procedimento adicional simples, cuja aplicação resultou na obtenção de padrões ótimos.<br>The Manufacturer's Pallet Loading Problem (MPLP) consists in arranging, orthogonally and without overlapping, the maximum number of rectangular and identical pieces of sizes (l, w) onto a pallet (L, W). The MPLP has been successfully handled by block heuristics, which generate loading patterns with one or more blocks where the pieces have the same orientation. The resulting patterns produced by these methods are limited to the so-called 1st order non-guillotine patterns. In this work we present a tabu search implementation based on the algorithm proposed by Dowsland to solve the MPLP; differently than block heuristics, the solutions are not limited to particular loading patterns. Computational experiments with a set of 34 instances extracted from the literature as well as from practical contexts indicate that this approach is capable to solve most of the examples. For the unsolved instances, we propose a simple additional procedure, which resulted in optimal patterns. |
| format | Article |
| id | doaj-art-deeaa0e8a8074e18a208da3a0e6e357c |
| institution | Kabale University |
| issn | 0103-6513 |
| language | English |
| publishDate | 2003-01-01 |
| publisher | Associação Brasileira de Engenharia de Produção (ABEPRO) |
| record_format | Article |
| series | Production |
| spelling | doaj-art-deeaa0e8a8074e18a208da3a0e6e357c2025-08-20T03:26:15ZengAssociação Brasileira de Engenharia de Produção (ABEPRO)Production0103-65132003-01-0113361710.1590/S0103-65132003000300002Um refinamento do algoritmo tabu de Dowsland para o problema de carregamento de paletes do produtor A refinement of Dowsland's tabu search algorithm for the manufacturer's pallet loading problemCintia A. YamassakiVitória PurezaO Problema de Carregamento de Paletes do Produtor consiste em arranjar, ortogonalmente e sem sobreposição, o máximo número de caixas retangulares idênticas de dimensões (l,w) sobre um palete (L,W). Este problema vem sendo tratado com sucesso por heurísticas de blocos, as quais constroem padrões de carregamento com um ou mais blocos, cujas caixas possuem a mesma orientação. Os arranjos gerados por estes métodos estão limitados aos chamados padrões não-guilhotinados de primeira ordem. Neste trabalho, foi elaborada uma implementação baseada no algoritmo de busca tabu de Dowsland, que, ao contrário das heurísticas de blocos, provê arranjos não limitados a padrões particulares de empacotamento. Experimentos computacionais com um conjunto de 34 exemplos extraídos da literatura e de contextos reais indicam que a abordagem é capaz de resolver otimamente a maioria dos exemplos; para os exemplos não resolvidos, é proposto um procedimento adicional simples, cuja aplicação resultou na obtenção de padrões ótimos.<br>The Manufacturer's Pallet Loading Problem (MPLP) consists in arranging, orthogonally and without overlapping, the maximum number of rectangular and identical pieces of sizes (l, w) onto a pallet (L, W). The MPLP has been successfully handled by block heuristics, which generate loading patterns with one or more blocks where the pieces have the same orientation. The resulting patterns produced by these methods are limited to the so-called 1st order non-guillotine patterns. In this work we present a tabu search implementation based on the algorithm proposed by Dowsland to solve the MPLP; differently than block heuristics, the solutions are not limited to particular loading patterns. Computational experiments with a set of 34 instances extracted from the literature as well as from practical contexts indicate that this approach is capable to solve most of the examples. For the unsolved instances, we propose a simple additional procedure, which resulted in optimal patterns.http://www.scielo.br/scielo.php?script=sci_arttext&pid=S0103-65132003000300002Problema de carregamento de paletesbusca tabuotimização combinatóriaPallet loading problemtabu searchcombinatorial optimization |
| spellingShingle | Cintia A. Yamassaki Vitória Pureza Um refinamento do algoritmo tabu de Dowsland para o problema de carregamento de paletes do produtor A refinement of Dowsland's tabu search algorithm for the manufacturer's pallet loading problem Production Problema de carregamento de paletes busca tabu otimização combinatória Pallet loading problem tabu search combinatorial optimization |
| title | Um refinamento do algoritmo tabu de Dowsland para o problema de carregamento de paletes do produtor A refinement of Dowsland's tabu search algorithm for the manufacturer's pallet loading problem |
| title_full | Um refinamento do algoritmo tabu de Dowsland para o problema de carregamento de paletes do produtor A refinement of Dowsland's tabu search algorithm for the manufacturer's pallet loading problem |
| title_fullStr | Um refinamento do algoritmo tabu de Dowsland para o problema de carregamento de paletes do produtor A refinement of Dowsland's tabu search algorithm for the manufacturer's pallet loading problem |
| title_full_unstemmed | Um refinamento do algoritmo tabu de Dowsland para o problema de carregamento de paletes do produtor A refinement of Dowsland's tabu search algorithm for the manufacturer's pallet loading problem |
| title_short | Um refinamento do algoritmo tabu de Dowsland para o problema de carregamento de paletes do produtor A refinement of Dowsland's tabu search algorithm for the manufacturer's pallet loading problem |
| title_sort | um refinamento do algoritmo tabu de dowsland para o problema de carregamento de paletes do produtor a refinement of dowsland s tabu search algorithm for the manufacturer s pallet loading problem |
| topic | Problema de carregamento de paletes busca tabu otimização combinatória Pallet loading problem tabu search combinatorial optimization |
| url | http://www.scielo.br/scielo.php?script=sci_arttext&pid=S0103-65132003000300002 |
| work_keys_str_mv | AT cintiaayamassaki umrefinamentodoalgoritmotabudedowslandparaoproblemadecarregamentodepaletesdoprodutorarefinementofdowslandstabusearchalgorithmforthemanufacturerspalletloadingproblem AT vitoriapureza umrefinamentodoalgoritmotabudedowslandparaoproblemadecarregamentodepaletesdoprodutorarefinementofdowslandstabusearchalgorithmforthemanufacturerspalletloadingproblem |