Dynamic programming and mixed integer programming based algorithms for the online glass cutting problem with defects and production targets

摘要

In flat glass manufacturing, glass products of various dimensions are cut from a glass ribbon that runs continuously on a conveyor belt. Placement of glass products on the glass ribbon is restricted by the defects of varying severity located on the ribbon as well as the quality grades of the products to be cut. In addition to cutting products, a common practice is to remove defective parts of the glass ribbon as scrap glass. As the glass ribbon moves continuously, cutting decisions need to be made within seconds, which makes this online problem very challenging. A simplifying assumption is to limit scrap cuts to those made immediately behind a defect (a cut-behind-fault or CBF). We propose an online algorithm for the glass cutting problem that solves a series of static cutting problems over a rolling horizon. We solve the static problem using two methods: a dynamic programming algorithm (DP) that utilises the CBF assumption and a mixed integer programming (MIP) formulation with no CBF restriction. While both methods improve the process yield substantially, the results indicate that MIP significantly outperforms DP, which suggests that the computational benefit of the CBF assumption comes at a cost of inferior solution quality.