Approaches to coupled generating and sequencing optimization problems

Author(s)

Gisele Castro Fontanella Pileggi

• Document type: Doctoral Thesis
• Press: São Carlos.
• Institution: Universidade de São Paulo (USP). Instituto de Ciências Matemáticas e de Computação (ICMC/SB)
• Defense date: 2002-12-02

Examining board members

Reinaldo Morabito Neto; Marcos Nereu Arenales; Paulo Morelato França; Clovis Perin Filho; Horacio Hideki Yanasse

• Advisor: Reinaldo Morabito Neto; Marcos Nereu Arenales

Abstract

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. (AU)