Uma revisão sobre o uso da programação dinâmica na solução do problema de corte

Abstract

Os problemas de corte e empacotamento d-dimensional, d ≥ 1 e inteiro, consistem em cortar (alocar) de (em) um objeto grande de medida O ∈ Rd , n objetos menores (itens) de medida Oi ∈ Rd e valor vi , i = 1, · · · , n com o critério de maximizar o valor total obtido com os itens cortados (ou alocados). Se d = 1, tem-se o Problema de Corte Unidimensional (PC-1D) e o Problema da Mochila (PM), e para d = 2, o Problema de Corte Bidimensional (PC-2D) e o Problema da Mochila Bidimensional (PM-2D). Nesses problemas, pode-se considerar ainda: o caso em que se restringe a quantidade de itens (R) ou não, caso irrestrito (I); ou ainda restrições associadas à maneira como os itens são cortados (alocados). O caso bidimensional tratado nessa pesquisa considera que o objeto e os itens são retangulares, e o corte é do tipo guilhotinado ortogonal (PCG- 2D), classificado de acordo com a tipologia de Wäscher et. al (apud [7]) como two- dimensional rectangular single large object placement problem. O objetivo é apresentar uma breve revisão bibliográfica sobre o uso da programação dinâmica (PD) para resolver esses problemas considerando os casos irrestrito e restrito. [...]