Academic Journals Database
Disseminating quality controlled scientific knowledge

Um método heurístico baseado em programação dinâmica para o problema de corte bidimensional guilhotinado restrito A heuristic method based on dynamic programming for the constrained two-dimensional guillotine cutting problem

ADD TO MY LIST
 
Author(s): Rejane Joas Silveira | Reinaldo Morabito

Journal: Gestão & Produção
ISSN 0104-530X

Volume: 9;
Issue: 1;
Start page: 78;
Date: 2002;
Original page

Keywords: problema de corte | padrões de corte bidimensionais guilhotinados restritos | programação dinâmica | heurísticas | cutting problem | constrained two-dimensional cutting patterns | dynamic programming | heuristics

ABSTRACT
Neste artigo estudamos um caso particular dos problemas de corte, denominado problema bidimensional guilhotinado restrito (PGR). O PGR é um problema NP-difícil que aparece em diversos processos industriais de corte de chapas retangulares, em particular, na indústria de vidro e placas de circuito impresso. Para resolvê-lo, exploramos uma variação do método exato de CHRISTOFIDES & HADJICONSTANTINOU (1995), baseada numa relaxação do espaço de estados de uma formulação de programação dinâmica do PGR, num procedimento do tipo otimização do subgradiente, e numa heurística de factibilização. O resultado é um método sem garantia de otimalidade, porém bem mais rápido e capaz de resolver problemas maiores do que o método exato de Christofides e Hadjiconstantinou. O desempenho computacional do método é avaliado resolvendo-se diversos exemplos da literatura e exemplos aleatórios, e comparando-se as soluções obtidas com as de CHRISTOFIDES & HADJICONSTANTINOU (1995) e da conhecida heurística de WANG (1983).In this paper we study a particular case of two-dimensional cutting problems named constrained guillotine cutting (CGC). The CGC is an NP-hard problem that appears in different industrial processes of cutting rectangular plates, such as in the glass and circuit board industries. To solve the problem we present a variation of the exact method of CHRISTOFIDES & HADJICONSTANTINOU (1995), based on a state space relaxation of a dynamic programming formulation of the CGC, a procedure of subgradient optimization type, and a feasibility heuristic. The result is a method without guarantee of optimality, however, faster and able to solve larger problems than the exact method of Christofides and Hadjiconstantinou. The computational performance of the approach is evaluated solving several examples of the literature as well as randomly generated examples, and comparing the solutions obtained with the ones of Christofides and Hadjiconstantinou’s method and the well-known heuristic of WANG (1983).
Save time & money - Smart Internet Solutions     

Tango Rapperswil
Tango Rapperswil