Seja um conjunto de formas retangulares em D- dimensional. Para d ∈ { 1 , . . . , D } e v ∈ V , w d ( v ) ∈ Q + descreve o comprimento de v na dimensão d . A mesma notação é usada para o recipiente C . A D problema -dimensional ortogonal embalagem (OPP- D ) é decidir se V se encaixa no recipiente Csem sobreposição. Formalmente, o problema é descobrir se existe uma função f d : V → Q + , tal que ∀ v ∈ V , f d ( v ) + w d ( v ) ≤ w d ( C ) e ∀ v 1 , v 2 ∈ V, , [ f d ( v 1 ) , f d ( v 1 ) + w d ( v 1 ) ) ∩ [ f d ( v 2 ) , f d ( v 2 ) + w d ( v 2 ) ) = ∅ .
O problema é NP-completo (veja Fekete SP, Schepers J. "Sobre embalagens com dimensões superiores I: Modelagem". Relatório Técnico 97–288, Universidade de zu Köln, 1997). O problema é NP-completo mesmo para . Gostaria de saber se o problema de empacotamento ortogonal para um número limitado de tipos (ou seja, tamanhos em cada dimensão) de itens ainda está completo ou não. Até agora, encontrei um resultado em algum artigo sobre a completude de NP de empacotar quadrados em um quadrado (consulte JOSEPH YT. LEUNG, TOMMY W. TAM e CS WONG, "Empacotar quadrados em um quadrado", Journal of Parallel and Distributed Distributed, Volume 10 Edição 3, novembro de 1990), que já é uma restrição, mas ainda não sei o que acontece quando o número de tipos de itens é limitado.
Obrigado pela sua resposta,
Respostas:
Penso que o artigo de Klaus Jansen e Roberto Solis-Oba " Um algoritmo OPT + 1 para o problema do material de corte com número constante de comprimentos de objeto " tem uma resposta parcial à sua pergunta. Eles consideram um caso especial do seu problema conhecido como problema de estoque de corte quando o número de diferentes tipos de objetos é constante e definido da seguinte forma:
Os autores afirmam que
E eles propõem o algoritmo de tempo polinomial de aproximação quando d é fixo.OPT+1 d
Uma vez que não está provado que este caso especial está em , esta é a evidência de que seu problema é N P -Hard.P NP
fonte