Full text
| |
| Author(s): |
Thiago Alves de Queiroz
Total Authors: 1
|
| Document type: | Doctoral Thesis |
| Press: | Campinas, SP. |
| Institution: | Universidade Estadual de Campinas (UNICAMP). Instituto de Computação |
| Defense date: | 2010-12-21 |
| Examining board members: |
Flávio Keidi Miyazawa;
Glauber Ferreira Cintra;
Eduardo Candido Xavier;
Orlando Lee;
Horacio Hideki Yanasse
|
| Advisor: | Flávio Keidi Miyazawa |
| Abstract | |
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 (AU) | |
| FAPESP's process: | 09/01129-1 - Capacited vehicle routing with loading restrictions |
| Grantee: | Thiago Alves de Queiroz |
| Support Opportunities: | Scholarships in Brazil - Doctorate |