Advanced search
Start date
Betweenand


A exact algorithm to two-dimensional level strip packing

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:
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)