A Dynamic Programming Algorithm for the Online Cutting Problem with Defects and Quality Grades

摘要

In this article, we propose a dynamic programming based algorithm for an online glass cutting problem that arises in the glass industry. In flat glass production, a continuous ribbon of flat glass is cut into glass products of various sizes as it flows on a conveyor belt. The glass ribbon contains defects of different types based on their severity and each glass product belongs to a quality class that indicates the maximum number of defects of each type that can be tolerated. Since the location and type of defects are detected in real time using a camera, the cutting problem has to be solved online and each cutting decision is made within a few seconds. The primary goal of this cutting problem is to minimize the amount of leftover (scrap) glass resulting from the cut products. The proposed algorithm uses a look-ahead strategy to solve a static cutting problem at each iteration to determine the products to be cut within a fixed horizon length, but implements only the first one or few of these cuts per iteration. We evaluated the algorithm on a set of realistic problems reflecting the parameters of current flat glass production lines. Computational results indicate that the proposed algorithm can reduce the amount of scrap glass by an average of 26.1%.