• 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.3.2013.tde-11072014-121631
Document
Auteur
Nom complet
Felipe Kesrouani Lemos
Adresse Mail
Unité de l'USP
Domain de Connaissance
Date de Soutenance
Editeur
São Paulo, 2013
Directeur
Jury
Santoro, Miguel Cezar (Président)
Mesquita, Marco Aurélio de
Morabito Neto, Reinaldo
Titre en portugais
Problema de programação de uma operação de empacotamento não-guilhotinado em ambiente de máquina única, minimizando custos de matéria-prima e desvio de datas: formulação e solução heurística.
Mots-clés en portugais
Bin packing
Corte e empacotamento (Cutting and packing)
Programação da produção (Scheduling)
Resumé en portugais
A presente pesquisa tem como objetivo estudar a integração entre dois temas clássicos da literatura de pesquisa operacional e gestão de operações: problemas de corte e empacotamento; e problemas de programação da produção. Ainda que sejam duas áreas intensamente exploradas e pesquisadas, e, ainda, que seja uma situação facilmente encontrada em sistemas de produção reais, abordagens de ambos problemas de forma coordenada ainda carecem de maiores pesquisas. Neste trabalho é feita uma revisão de ambos temas, com foco em problemas de bin packing e programação em ambiente de máquina única com objetivo de minimizar soma de atrasos e adiantamentos ponderados. Uma formulação matemática linear e inteira mista é proposta para o problema, contemplando as restrições que concernem a cada um e também à sua consideração simultânea. Como se trata de um problema que une dois outros, cada um NP-hard isoladamente, um método heurístico é proposto para obter uma solução interessante em tempos computacionais bastante reduzidos. Foram obtidas propriedades físicas de definição de data ideal de programação de um conjunto de itens atribuídos a um bin. Também é proposto um método para geração de um limitante inferior melhorado em relação a pacotes de otimização de mercado para o problema. Ambos métodos foram testados em uma massa de dados de 1.152 instâncias, geradas para retratar cenários de diferentes datas de entrega, setups, custos de atraso e adiantamento em relação à matéria-prima, tamanho de itens e número de itens na instância. Os resultados mostram-se largamente superiores aos obtidos por um otimizador genérico (CPLEX), embora ainda sejam gaps excessivamente grandes, o que reforça a dificuldade do problema.
Titre en anglais
Scheduling problem of a non-guillotine packing operation on single-machine envirornment, minimizing raw material, earliness and tardiness costs: formulation and heuristic solution.
Mots-clés en anglais
Bin packing
Cutting and packing
Production scheduling
Resumé en anglais
The present research aims to explore the integration between two classic themes on operations research and operations management literature: cutting and packing problems; and production scheduling problems. Although they are intensive explored and researched areas and, besides, it's an easily found situation on real production systems, coordinated approaches of both themes still need deeper research. On this paper, it was done a review of both themes, focusing on bin packing problems and single-machine environment scheduling problems aiming to minimize total weighed earliness and tardiness. A mixed integer-linear mathematical formulation is proposed to the problem, including constraints referred to each problem and, also, to their simultaneous consideration. Once it's a problem that joins the other two, each one NP-hard solely, an heuristic method is proposed to obtain an interesting solution in reasonable computational times. Physical properties were identified, defining the best date to allocate a given lot of items to be processed together. Also, a lower bound generation method is proposed, improving the one generated by optimization softwares. Both methods were tested on a 1.152 instances mass of data, generated to represent well several scenarios of different due dates, setup times, earliness and tardiness costs compared to raw material, size of items and number the items the instance. Results show largely superiority the ones obtained by an optimization pack (CPLEX), although gaps are still excessively large, fact the reinforces problem's difficulty.
 
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.
Date de Publication
2014-07-16
 
AVERTISSEMENT: Le matériau se réfère à des documents provenant de cette thèse ou mémoire. Le contenu de ces documents est la responsabilité de l'auteur de la thèse ou mémoire.
  • LEMOS, F. K., and SANTORO, M. C. Sequencing bidimensional guillotine cutting operations considering lateness and raw material utilization. In EURO XXIV - 24TH EUROPEAN CONFERENCE ON OPERATIONAL RESEARCH, Lisboa, 2010. EURO XXIV - 24TH EUROPEAN CONFERENCE ON OPERATIONAL RESEARCH., 2010. Abstract.
  • LEMOS, F. K., e SANTORO, M. C. Sequenciamento de Ordens com Operações em Lotes Bidimensionais Não Guilhotinados considerando Atendimento de Datas e Ocupação da Matéria Prima. In 42º Simpósio Brasileiro de Pesquisa Operacional, Bento Gonçalves, 2010. 42º Simpósio Brasileiro de Pesquisa Operacional - Livro de Resumos., 2010.
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-2019. Tous droits réservés.