| Revista: | Pesquisa operacional |
| Base de datos: | PERIÓDICA |
| Número de sistema: | 000313126 |
| ISSN: | 0101-7438 |
| Autores: | Oliveira, Lilian Katia de1 Morabito, Reinaldo1 |
| Instituciones: | 1Universidade Federal de Sao Carlos, Departamento de Engenharia de Producao, Sao Carlos, Sao Paulo. Brasil |
| Año: | 2006 |
| Periodo: | May-Ago |
| Volumen: | 26 |
| Número: | 2 |
| Paginación: | 403-432 |
| País: | Brasil |
| Idioma: | Portugués |
| Tipo de documento: | Artículo |
| Enfoque: | Analítico, descriptivo |
| Resumen en inglés | In this paper we present exact methods, based on Lagrangean and surrogate relaxations, with good performance to solve the manufacturer's pallet loading problem. This problem consists of orthogonally arranging the maximum number of rectangles of sizes (l,w) or (l,w) into a larger rectangle (L,W) without overlapping. The proposed methods involve a branch and bound based tree search procedure for which the bounds, in each node of the tree, are 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 to obtain good feasible solutions in the subgradient optimization. Computational experiments were performed with instances of the literature and actual instances of a carrier. The results show that one of the proposed methods is competitive with methods found in the literature, including the software GAMS/CPLEX |
| Resumen en portugués | 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 |
| Disciplinas: | Matemáticas, Ingeniería |
| Palabras clave: | Matemáticas aplicadas, Ingeniería industrial, Productores, Plataforma de carga, Problema de plataformas de carga, Relajación lagrangiana, Ramificación y poda, Optimización de subgradiente |
| Keyword: | Mathematics, Engineering, Applied mathematics, Industrial engineering, Manufacturers, Pallet Loading, Pallet loading problem, Lagrangian relaxation, Branch and bound, Subgradient optimization |
| Texto completo: | Texto completo (Ver HTML) |
