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

被引：9

作者：

Boschetti, Marco A. ^{[1
]}

Maniezzo, Vittorio ^{[2
]}

Strappaveccia, Francesco ^{[2
]}

机构：

[1] Univ Bologna, Dept Math, I-47521 Cesena, Italy

[2] Univ Bologna, Dept Comp Sci & Engn, DISI, I-47521 Cesena, Italy

来源：

INFORMS JOURNAL ON COMPUTING | 2016年 / 28卷 / 03期

关键词：

combinatorial optimization problems; cutting problems; dynamic programming; parallel computing; GPU computing; CUDA; STOCK; ALGORITHMS;

D O I：

10.1287/ijoc.2016.0693

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

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.

引用

页码：540 / 552

页数：13

共 28 条

[1]

BEASLEY JE, 1985, J OPER RES SOC, V36, P297

[2]

Bellman R. E., 1957, Dynamic programming. Princeton landmarks in mathematics

[3] Solving knapsack problems on GPU [J].