Algoritmos para problemas de corte e empacotamento / Algorithms for cutting and packing problems

AUTOR(ES)

Thiago Alves de Queiroz

DATA DE PUBLICAÇÃO

2010

RESUMO

Several versions of Cutting and Packing problems are considered NP-hard and, if we consider that P ¿ NP, we do not have any exact polynomial algorithm for solve them. Practical applications arises for such problems and include: resources allocation for computers; cut of steel, wood, glass, aluminum, etc.; packing of objects; and, loading objects into containers and trucks. In this thesis we investigate Cutting and Packing problems that are NP-hard considering theirs two- and three-dimensional versions, and subject to several practical constraints, that are: that allows the items to be orthogonally rotated; whose cuts are guillotine type; whose cuts are guillotine type and performed in at most k stages; whose cuts are non-guillotine type; whose items have varying and unit demand; whose bins are of variable sizes; whose items are represented by convex and non-convex polygons (irregular shapes); whose packing must satisfy the conditions for static equilibrium of rigid bodies; whose packing must satisfy an order to unloading; and, whose intermediaries and resultant packing have theirs center of gravity inside a safety region; Such cutting and packing problems were solved by dynamic programming algorithms; integer linear programming models; branch-and-cut algorithms; several heuristics, including those ones based on column generation approaches, and metaheuristics like GRASP. Theoretical results were also provided, so a recent open question arised by literature about non-guillotine patterns restricted to a set of points was demonstrated. We performed an extensive series of computational experiments for algorithms developed considering several instances presented in literature and others generated at random. These results, some of them compared with the literature, validate the approaches proposed and suggest their applicability to deal with practical situations involving the problems here investigated

ASSUNTO(S)

algorithms problema de corte problema de empacotamento otimização combinatória algoritmos cutting problem packing problem combinatorial optimization

Documentos Relacionados

• Algoritmos para problemas de empacotamento
• Three-dimensional cutting and packing problems and integration with vehicle routing
• Algoritmos de aproximação para problemas de empacotamento em faixa com restrições de descarregamento
• Algoritmos para problemas de grafos com incertezas
• Algoritmos para problemas de escalonamento em grades