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.

在平板玻璃制造过程中，各类尺寸的玻璃制品均从传送带持续输送的玻璃带（glass ribbon）上切割得到。玻璃制品在玻璃带上的排布位置，受玻璃带表面不同严重程度的缺陷以及待切割制品的质量等级双重限制。除切割成品外，行业常规操作还会将玻璃带上的缺陷区域作为废玻璃去除。由于玻璃带持续运行，切割决策必须在数秒内完成，这使得该在线问题极具挑战性。一种简化假设是将废玻璃切割限定在缺陷紧邻的后方位置，即缺陷后切割（cut-behind-fault, CBF）。针对该玻璃切割问题，我们提出一种在线算法，其通过滚动时域策略求解一系列静态切割子问题。我们采用两种方法求解静态切割问题：一种是利用CBF假设的动态规划算法（DP），另一种是无CBF限制的混合整数规划（MIP）模型。尽管两种方法均能显著提升工艺收率，但结果表明MIP的性能显著优于DP，这意味着CBF假设所带来的计算优势，是以牺牲更优解质量为代价的。