• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Mémoire de Maîtrise
DOI
10.11606/D.55.2015.tde-25062015-111716
Document
Auteur
Nom complet
Marcos Okamura Rodrigues
Adresse Mail
Unité de l'USP
Domain de Connaissance
Date de Soutenance
Editeur
São Carlos, 2015
Directeur
Jury
Toledo, Franklina Maria Bragion de (Président)
Andretta, Marina
Telles, Guilherme Pimentel
Titre en portugais
Modelos matemáticos para o problema de empacotamento em faixas de peças irregulares
Mots-clés en portugais
Cobertura por cliques
Empacotamento em faixas
Peças irregulares
Programação inteira mista
Resumé en portugais
O problema de empacotamento em faixas de peças irregulares consiste em cortar um conjunto de peças bidimensionais a partir de um objeto de largura fixa utilizando o menor comprimento possível. Apesar de sua importância econômica para diversos setores industriais, há poucos trabalhos que abordam o problema de forma exata devido a sua dificuldade de resolução. Recentemente, Toledo et al. (2013) propuseram um modelo inteiro misto para este problema, no qual as peças são posicionadas em uma malha de pontos. Este modelo obteve bons resultados, provando a otimalidade para instâncias com até 21 peças. No entanto, o modelo possui um grande número de restrições de não-sobreposição, que cresce rapidamente de acordo com a discretização utilizada e a quantidade de peças distintas que devem ser alocadas. Neste trabalho, são propostas novas formulações matemáticas baseadas neste modelo, com o objetivo de reduzir o número de restrições. Na primeira abordagem, são propostos dois modelos reduzidos que mostraram ser eficientes para instâncias com poucas repetições de peças. Na segunda abordagem, foi proposto um modelo de cobertura por cliques para o problema. Este modelo obteve desempenho igual ou superior ao modelo da literatura para todas as instâncias avaliadas, obtendo uma solução ótima para instâncias com até 28 peças.
Titre en anglais
Mathematical models for the irregular packing problem
Mots-clés en anglais
Clique covering
Irregular
Mixed integer progrmming
Nesting
Strip packing
Resumé en anglais
The irregular strip packing problem consists of cutting a set of two-dimensional pieces from an object of fixed width using the smallest possible length. Despite its economic importance for many industrial sectors, few exact studies have been made on this problem due to its difficulty of resolution. Recently, Toledo et al. (2013) proposed a mixed-integer model to this problem in which the pieces are placed on a grid. This model has worked successfully proving the optimality for instances up to 21 pieces. However, the model has a large number of non-overlapping constraints, which grows quickly in accordance with the discretization resolution and number of distinct pieces. In this work, we propose new mathematical formulations based on this model in order to reduce the number of constraints. In the first approach, we present two reduced models that have shown to be effective for instances with few repetitions of pieces. In the second approach, it was proposed a clique covering model for the problem. This model achieved a greater or equal performance than the literature for all instances, getting an optimal solution for instances up to 28 pieces.
 
AVERTISSEMENT - Regarde ce document est soumise à votre acceptation des conditions d'utilisation suivantes:
Ce document est uniquement à des fins privées pour la recherche et l'enseignement. Reproduction à des fins commerciales est interdite. Cette droits couvrent l'ensemble des données sur ce document ainsi que son contenu. Toute utilisation ou de copie de ce document, en totalité ou en partie, doit inclure le nom de l'auteur.
MarcosOkamura_rev.pdf (1.33 Mbytes)
Date de Publication
2015-06-25
 
AVERTISSEMENT: Apprenez ce que sont des œvres dérivées cliquant ici.
Tous droits de la thèse/dissertation appartiennent aux auteurs
Centro de Informática de São Carlos
Bibliothèque Numérique de Thèses et Mémoires de l'USP. Copyright © 2001-2022. Tous droits réservés.