Abstract: The two-dimensional glass cutting problem to be solved by Saint Gobain, one of the world’s largest producers of flat glass, includes some specific constraints that prevent the direct application of procedures developed for the standard cutting problem. On the one hand, the sheets to be cut have defects that made them unique and must be used in a specific order. On the other hand, the pieces are grouped in stacks and the pieces in each stack must be cut in order. There are also some additional characteristics due to the technology used, especially the requirement for a three-staged guillotine cutting process.

We have developed heuristic and exact procedures. First, we have developed a beam search algorithm, using a tree structure in which at each level the partial solution is augmented by adding some new elements until a complete solution was built. We developed a randomized constructive algorithm for building these new elements and explored several alternatives for the local and the global evaluation. An improvement procedure, specifically designed for the problem, was also added. The computational study, using the datasets provided by the company, shows the efficiency of the proposed algorithm for short and long running times.

We have also approached the problem by developing and solving integer linear models. We start with basic models, which include the essential features of the problem, as a classical 3-stage cutting problem. Then, we progressively add new conditions to consider the order in the stacks, the minimum waste produced by guillotine cuts, and the possibility of trimming for some specific items. Finally, we add the conditions of the defects in the sheets. We propose the first integer linear model capable to work with trimming and defects. The results show that in most cases the optimal solution can be obtained for small problems considering all the constraints of the real problem.