Métodos exatos baseados em relaxações lagrangiana e surrogate para o problema de carregamento de paletes do produtor

Pesquisa Operacional

Lilian Kátia De Oliveira¹  Reinaldo Morabito¹ 

[1] ,Universidade Federal de São Carlos Departamento de Engenharia de Produção São Carlos SP

关键词: problema de carregamento de paletes do produtor;    relaxação Lagrangiana e/ou surrogate;    método branch and bound;    otimização do subgradiente;    manufacturer's pallet loading problem;    Lagrangean and/or surrogate relaxation;    branch and bound method;    subgradient optimization;   

DOI  :  10.1590/S0101-74382006000200010

来源: SciELO

【 摘 要 】

Neste artigo apresentamos métodos exatos, baseados em relaxações Lagrangiana e surrogate, com bom desempenho para resolver o problema de carregamento de paletes do produtor. Este problema consiste em arranjar ortogonalmente e sem sobreposição o máximo número de retângulos de dimensões (l,w) ou (l,w) sobre um retângulo maior (L,W). Os métodos propostos são procedimentos de busca em árvore do tipo branch and bound que, em cada nó, utilizam limitantes derivados de relaxações Lagrangiana e/ou surrogate de uma formulação de programação linear 0-1. Algoritmos de otimização do subgradiente são usados para otimizar estes limitantes. São aplicados ainda testes de redução do problema e heurísticas Lagrangiana e surrogate para se obter boas soluções factíveis na otimização do subgradiente. Testes computacionais foram realizados utilizando exemplos da literatura e exemplos reais de uma transportadora. Os resultados mostram que um dos métodos propostos é competitivo com outros métodos da literatura, incluindo o software GAMS/CPLEX.

【 授权许可】

CC BY   
 All the contents of this journal, except where otherwise noted, is licensed under a Creative Commons Attribution License