Using GPU Computing for Solving the Two-Dimensional Guillotine Cutting Problem

摘要

In recent years, GPU computing has become an increasingly important tool to develop efficient applications in several areas, including optimization. One of the optimization approaches that seems to take most advantage from GPU computing is dynamic programming. In this paper, we investigate the application of GPU computing to the two-dimensional guillotine cutting problem, solved by dynamic programming. We show a possible implementation and we discuss a number of technical issues. Computational results on test instances available in the literature and on new larger instances show the effectiveness of the dynamic programming approach based on GPU computing for this problem.