Full text
| |
| Author(s): |
Carlos Eduardo de Andrade
Total Authors: 1
|
| Document type: | Master's Dissertation |
| Press: | Campinas, SP. |
| Institution: | Universidade Estadual de Campinas (UNICAMP). Instituto de Computação |
| Defense date: | 2006-09-26 |
| Examining board members: |
Flávio Keidi Miyazawa;
Carlos Eduardo Ferreira;
Cid Carvalho de Souza
|
| Advisor: | Flávio Keidi Miyazawa |
| Abstract | |
Cutting and packing problems are common problems that occur in many industry and business process. Their optimized resolution leads to great profits in several sectors. A common problem, that occur in textil and paper industries, is to cut a strip of some material to obtain several small items, using the minimum length of material. This problem, known by Two Dimensional Strip Packing Problem (2SP), is a hard combinatorial optimization problem. In this work, we present an exact algorithm to 2SP, restricted to two staged cuts (known by Two Dimensional Level Strip Packing, 2LSP). The algorithm uses the branch-and-price technique, and heuristics based on approximation algorithms to obtain upper bounds. The algorithm obtained optimal or almost optimal for small and moderate sized instances (AU) | |