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

Description

Made available in DSpace on 2016-06-02T19:50:17Z (GMT). No. of bitstreams: 1
TeseLKO.pdf: 834201 bytes, checksum: 994d7b70c6b1001f9dec962fafc8b72e (MD5)
Previous issue date: 2004-12-13 / Universidade Federal de Sao Carlos / The purpose of this work is to develop exact methods, based on
Lagrangean and Surrogate relaxation, 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) 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. / O objetivo deste trabalho é desenvolver métodos exatos, baseados em
relaxação Lagrangiana e Surrogate, com bom desempenho para resolver o problema de
carregamento de paletes do produtor. Tal problema consiste em arranjar ortogonalmente
e sem sobreposição o máximo número de retângulos de dimensões ( , ) l w ou ( , ) w l
sobre um retângulo maior ( , ) L W . Tais métodos exatos 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 na otimização do subgradiente para obter boas soluções factíveis. Testes
computacionais foram realizados utilizando exemplos da literatura e exemplos reais,
obtidos de uma transportadora. Os resultados mostram que os métodos são capazes de
resolvê-los, em média, mais rapidamente do que outros métodos exatos, incluindo o
software GAMS/CPLEX.

Links & Downloads

1. OLIVEIRA, Lilian Kátia de. Métodos exatos baseados em relaxação lagrangiana e surrogate para o problema de carregamento de paletes do produtor.. 2004. 199 f. Tese (Doutorado em Ciências Exatas e da Terra) - Universidade Federal de São Carlos, São Carlos, 2004.
2. https://repositorio.ufscar.br/handle/ufscar/3407

Tags

Paletes

Relaxação lagrangiana

Relaxação surrogate

Método Branch and Bound

Manufacturer s pallet loading problem

Lagrangean relaxation

Surrogate relaxation

Branch and Bound Method

ENGENHARIAS::ENGENHARIA DE PRODUCAO

Additional Fields

Identifer	oai:union.ndltd.org:IBICT/oai:repositorio.ufscar.br:ufscar/3407
Date	13 December 2004
Creators	Oliveira, Lilian Kátia de
Contributors	Morabito Neto, Reinaldo
Publisher	Universidade Federal de São Carlos, Programa de Pós-graduação em Engenharia de Produção, UFSCar, BR
Source Sets	IBICT Brazilian ETDs
Language	Portuguese
Detected Language	Portuguese
Type	info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis
Format	application/pdf
Source	reponame:Repositório Institucional da UFSCAR, instname:Universidade Federal de São Carlos, instacron:UFSCAR
Rights	info:eu-repo/semantics/openAccess