Irregular and quasi-polyomino strip packing problems (2020)
- Authors:
- Autor USP: RODRIGUES, MARCOS OKAMURA - ICMC
- Unidade: ICMC
- Sigla do Departamento: SME
- DOI: 10.11606/T.55.2020.tde-29072020-094550
- Subjects: HEURÍSTICA; PROGRAMAÇÃO MISTA; EMPACOTAMENTO E COBERTURA
- Keywords: Empacotamento em faixa; Irregular shapes; Itens irregulares; Nesting; Polyomino; Quasi-poliominós, Poliominós; Quasi-polyomino; Strip packing
- Agências de fomento:
- Language: Inglês
- Abstract: O problema de empacotamento em faixa de itens irregulares consiste em cortar um conjunto de itens bidimensionais a partir de um objeto com largura fixa usando o menor comprimento possível. Apesar de sua importância econômica para várias indústrias, devido a sua dificuldade de resolução poucos métodos exatos foram direcionados para o problema. Recentemente, um modelo de progamação inteira mista no qual os itens são posicionados sobre uma grelha foi proposto. Embora o modelo tenha provado a otimalidade para algumas instâncias de grande porte, ele possui um grande número de restrições de não-sobreposição, que cresce rapidamente de acordo com a resolução da discretização e o número de itens distintos. Nesta tese, é proposto um modelo de cobertura por cliques para reduzir o número de restrições e melhorar a relaxação linear. As coberturas são obtidas através de uma heurística desenvolvida pelo próprio autor. O modelo obtido superou a performance do modelo anterior para a maioria das instâncias avaliadas e obteve uma solução ótima para instância com até 25 itens (22 itens distintos) sujeito à discretização da grelha. Recentemente, outro modelo de programação inteira mista foi proposto para o problema, mas ele permite um grande número de soluções simétricas. Nesta tese, novas restrições de quebra de simetria são propostas para melhorar o modelo. Experimentos computacionais foram realizados para instâncias com itens convexos. Os resultados indicaram que a formulação proposta émelhor que a anterior para a maioria das instâncias, uma vez que melhora os limitantes inferiores e reduz o tempo de execução e o número de nós explorados para provar a otimalidade. Um caso particular de item irregular é um poliominó. Um poliominó consiste em um conjunto de quadrados de mesma dimensão conexos pela junção de uma de suas arestas. Um quasi-poliominó é uma generalização do conceito de poliominó, uma vez que representa um subconjunto de quadrados não necessariamente conexos de uma malha quadriculada equidistante. Problemas de corte e empacotamento de quasi-poliominós possuem diversas aplicações reais, por exemplo, o corte de itens de couro, a estamparia de chapas metálicas, o desenho de placas de circuito impresso e a diagramação de páginas de revistas e jornais. Nesta tese, estudamos o problema de empacotamento em faixa de quasi-poliominós. São propostos dois modelos de programação inteira para o problema e realizados testes computacionais para avaliá-los. Os modelos foram avaliados utilizando instâncias da literatura e apresentaram bons resultados, obtendo uma solução ótima para uma instância com 320 itens (20 itens distintos) em um recipiente de dimensões 44x50. Como esperado, foram encontradas mais soluções ótimas quando não há rotações e reflexões e quando as dimensões dos itens são pequenas.
- Imprenta:
- Publisher place: São Carlos
- Date published: 2020
- Data da defesa: 06.04.2020
- Este periódico é de acesso aberto
- Este artigo é de acesso aberto
- URL de acesso aberto
- Cor do Acesso Aberto: gold
- Licença: cc-by-nc-sa
-
ABNT
RODRIGUES, Marcos Okamura. Irregular and quasi-polyomino strip packing problems. 2020. Tese (Doutorado) – Universidade de São Paulo, São Carlos, 2020. Disponível em: https://www.teses.usp.br/teses/disponiveis/55/55134/tde-29072020-094550/. Acesso em: 03 out. 2024. -
APA
Rodrigues, M. O. (2020). Irregular and quasi-polyomino strip packing problems (Tese (Doutorado). Universidade de São Paulo, São Carlos. Recuperado de https://www.teses.usp.br/teses/disponiveis/55/55134/tde-29072020-094550/ -
NLM
Rodrigues MO. Irregular and quasi-polyomino strip packing problems [Internet]. 2020 ;[citado 2024 out. 03 ] Available from: https://www.teses.usp.br/teses/disponiveis/55/55134/tde-29072020-094550/ -
Vancouver
Rodrigues MO. Irregular and quasi-polyomino strip packing problems [Internet]. 2020 ;[citado 2024 out. 03 ] Available from: https://www.teses.usp.br/teses/disponiveis/55/55134/tde-29072020-094550/
Informações sobre o DOI: 10.11606/T.55.2020.tde-29072020-094550 (Fonte: oaDOI API)
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
