An online algorithm for the glass cutting problem with defects of multiple grades and products with quality classes

In this thesis, we focus on the problem of placing cutting patterns on a sheet of flat glass that contains various types of defects. In flat glass production, a continuous glass sheet is cut into glass products of different sizes and different quality classes. Each quality class indicates the maximum number of defects of each type that can be tolerated on a glass product. Products that do not meet the quality requirements defined by their quality classes are considered scrap and sent back to the furnace to be recycled. In a continuous glass production line, patterns to be cut from the glass sheet have to be determined in real time, which limits the time available for decision making. The main goal of the glass cutting problem is to determine the cutting patterns in a limited time so as to minimize the total area of scrap glass. In selecting the products to be cut, daily production targets of each product type are also considered to ensure timely delivery of orders. To solve this real time glass cutting problem, we propose an online algorithm that solves a series of static cutting problems over a rolling horizon using various approaches and implements the first few cuts from each static solution to avoid a myopic decision. In this study, we develop genetic algorithm (GA), dynamic programming (DP) and Mixed Integer Programming (MIP) based methods for solving the static cutting problem on a glass sheet of fixed size that contains defects. These methods are integrated into the online algorithm and tested using realistic instances with different defect densities. In the initial versions of the algorithm, production targets are used as constraints. Later, production targets are integrated into the objective function in order to the improve solution quality by balancing the production of different products during the production run. Moreover, an adaptive version of the algorithm, which is capable of adjusting itself based on the current status of the production run, is also provided in this study. This thesis is one of the first studies in the literature that solves a real time cutting problem with defects of multiple grades and products with quality classes.