Exportar registro bibliográfico

O problema de minimização de pilhas abertas - novas contribuições (2012)

  • Authors:
  • USP affiliated authors: FINK, CLAUDIA - ICMC
  • Unidades: ICMC
  • Sigla do Departamento: SME
  • Subjects: OTIMIZAÇÃO COMBINATÓRIA; HEURÍSTICA; TEORIA DOS GRAFOS
  • Keywords: Combinatorial optimization; Heuristic; Heurística; Otimização combinatória
  • Language: Português
  • Abstract: O Problema de Minimização do Número Máximo de Pilhas Abertas (MOSP, do inglês minimization of open stacks problem) é um problema de otimização combinatória da família NP-Difícil que vem recebendo grande atenção na literatura especializada. Este trabalho apresenta novas contribuições em termos de modelos e técnicas de resolução para o problema. A primeira parte deste trabalho lidou com modelos matemáticos, sendo analisados os modelos existentes que se baseiam em programação inteira mista. Variações de um modelo da literatura foram propostas, com o objetivo de tentar diminuir o tempo de execução necessário para se obter uma solução exata com a utilização de pacotes comerciais. Os resultados mostraram que as propostas são capazes de acelerar a solução de algumas classes de instâncias mas, que de maneira geral, métodos baseados em relaxação linear encontram dificuldade em provar a otimalidade devido à baixa qualidade dos limitantes inferiores. Uma outra contribuição deste trabalho foi o desenvolvimento de um modelo conjunto para o problema MOSP e para o problema de minimização da duração de pedidos (MORP, do inglês minimization of order spread problem). Este modelo propõe um framework unificado em que os dois problemas podem ser resolvidos ao mesmo tempo, tendo suas funções objetivo individuais ponderadas através de pesos definidos pelo usuário. A segunda parte do trabalho voltou-se para o desenvolvimento de métodos heurísticos para o MOSP. Duas estratégias de solução foramdesenvolvidas. O primeiro método propõe uma transformação heurística entre o problema MOSP e o clássico problema do caixeiro viajente (TSP, do inglês traveling salesman problem). A partir de uma representação em grafo do MOSP, o TSP é definido por meio de uma regra de atribuição de distâncias baseadas nos graus dos nós. Nos testes computacionais, a estratégia proposta mostrou-se eficiente em relação às heurísticas específicas para o MOSP, obtendo a solução ótima do MOSP em 80,42% das instâncias testadas e sendo competitiva em termos de tempo computacional com algumas das melhores heurísticas da literatura. O segundo método heurístico proposto utilizou a ideia de decomposição. De fato, neste método, um corte no grafo associado ao problema original divide-o em problemas menores, que são resolvidos. A solução global é obtida através da junção das soluções dos subproblemas e, em alguns casos, é possível demonstrar a otimalidade da solução obtida. Testes computacionais indicam a validade da proposta e apontam caminhos para pesquisas futuras
  • Imprenta:
  • Data da defesa: 19.10.2012
  • Online source access
    How to cite
    A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas

    • ABNT

      FINK, Claudia; COSTA, Alysson Machado; YANASSE, Horacio Hideki. O problema de minimização de pilhas abertas - novas contribuições. 2012.Universidade de São Paulo, São Carlos, 2012. Disponível em: < http://www.teses.usp.br/teses/disponiveis/55/55134/tde-19022013-084858/ >.
    • APA

      Fink, C., Costa, A. M., & Yanasse, H. H. (2012). O problema de minimização de pilhas abertas - novas contribuições. Universidade de São Paulo, São Carlos. Recuperado de http://www.teses.usp.br/teses/disponiveis/55/55134/tde-19022013-084858/
    • NLM

      Fink C, Costa AM, Yanasse HH. O problema de minimização de pilhas abertas - novas contribuições [Internet]. 2012 ;Available from: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-19022013-084858/
    • Vancouver

      Fink C, Costa AM, Yanasse HH. O problema de minimização de pilhas abertas - novas contribuições [Internet]. 2012 ;Available from: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-19022013-084858/

    Últimas obras dos mesmos autores vinculados com a USP cadastradas na BDPI:

Digital Library of Intellectual Production of Universidade de São Paulo     2012 - 2020