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

AUTOR(ES)

Lilian Kátia de Oliveira

DATA DE PUBLICAÇÃO

2004

RESUMO

The purpose of this work is to develop exact methods, based on Lagrangean and Surrogate relaxation, with good performance to solve the manufacturers pallet loading problem. This problem consists of orthogonally arranging the maximum number of rectangles of sizes (l,w) and (w,l) into a larger rectangle (L,W) without overlapping. Such methods involve a tree search procedure of branch and bound type and they use, in each node of the branch and bound tree, bounds derived from Lagrangean and/or Surrogate relaxations of a 0-1 linear programming formulation. Subgradient optimization algorithms are used to optimize such bounds. Problem reduction tests and Lagrangean and Surrogate heuristics are also applied in the subgradient optimization to obtain good feasible solution. Computational experiments were performed with instances from the literature and also real instances obtained from a carrier. The results show that the methods are able to solve these instances, on average, more quickly than other exact methods, including the software GAMS/CPLEX.

ASSUNTO(S)

método branch and bound lagrangean relaxation relaxação surrogate surrogate relaxation relaxação lagrangiana branch and bound method paletes engenharia de producao manufacturers pallet loading problem

Documentos Relacionados

• Métodos exatos baseados em relaxações lagrangiana e surrogate para o problema de carregamento de paletes do produtor
• Um método heurístico baseado em relaxação Lagrangiana para o problema de carregamento de paletes do produtor
• Uma heurística de busca tabu simples para o problema de carregamento de paletes do produtor
• Um refinamento do algoritmo tabu de Dowsland para o problema de carregamento de paletes do produtor
• Aplicação do método de decomposição de Benders para o problema de carregamento de paletes