Approaches to coupled generating and sequencing optimization problems

O problema de corte de estoque consiste em cortar unidades maiores (objetos) em unidades menores (itens) de maneira a satisfazer uma demanda e otimizar algum critério, por exemplo, minimizar a perda gerada pelos padrões de corte (um padrão descreve como arranjar itens dentro de um objeto). O problema dc sequenciamento de padrões de corte consiste em determinar uma sequência, na qual os padrões serão processados a fim de otimizar algum critério, por exemplo, minimizar o número máximo de pilhas abertas (itens que ainda serão cortados de um ou mais padrões na sequência) durante o corte dos padrões. Em alguns processos industriais os problemas de geração e sequenciamento de padrões de corte não podem ser resolvidos de forma independente pois, em geral, uma boa solução para o problema de corte (isto é, com pequena perda de material) não corresponde a uma boa solução para o problema de sequenciamento (isto é, com um pequeno número de pilhas abertas) e vice-versa. Existe, na verdade, um trade-off entre os objetivos desses dois problemas. Neste trabalho três abordagens heurísticas são apresentadas para resolver de forma integrada os problemas de geração e sequenciamento de padrões. Os resultados computacionais apresentados mostram que as abordagens geram boas soluções e são eficazes para analisar o trade-off entre esses dois problemas.The cutting stock problem consists of cutting large units (objects) into smaller ones (items) in order to satisfy a demand and optimize a criterion, e.g., to minimize the trim loss. The sequencing problem consists of determining a sequence in which to cut patterns so as to optimize an objective, such as minimizing the maximum number of open stacks (items that will still be cut from one or more patterns in the sequence) during the pattern cut. In some industrial processes, the problems involved in generating and sequencing cutting patterns cannot be solved independently because a good solution for the cutting problem (i.e., with low trim loss) usually does not correspond to a good solution for the sequencing problem (i.e., with a small maximum number of open stacks) or vice-versa. There is, in fact, a tradeoff between the objectives of these two problems. In this work, three heuristic approaches are presented to solve the problems of generating and sequencing cutting patterns in an integrated manner. The computational results presented here demonstrate that these approaches offer good solution and are effective to analyze the tradeoff between these two problems