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

References

• Beasley JE (1985) Algorithms for unconstrained two-dimensional guillotine cutting. J. Oper. Res. Soc. 36:297–306.Crossref, Google Scholar
• Bellman R (1957) Dynamic Programming (Princeton University Press, Princeton, NJ).Google Scholar
• Boyer V, El Baz D, Elkihel M (2012) Solving knapsack problems on GPU. Comput. Oper. Res. 39:42–47.Crossref, Google Scholar
• Bożejko W, Uchroński M, Wodecki M (2012) Solving the flexible job shop problem on GPU. Rutkowski L, Korytkowski M, Scherer R, Tadeusiewicz R, Zadeh LA, Zurada JM, eds. Artificial Intelligence and Soft Computing, Lecture Notes in Computer Science, Vol. 7268 (Springer, Berlin), 387–394.Crossref, Google Scholar
• Buluc A, Gilbert JR, Budak C (2010) Solving path problems on the GPU. Parallel Comput. 36:241–253.Crossref, Google Scholar
• Chakroun I, Mezmaz M, Melab N, Bendjoudi A (2013) Reducing thread divergence in a GPU-accelerated branch-and-bound algorithm. Concurrency Comput.: Practice Experience 25:1121–1136.Crossref, Google Scholar
• Christofides N, Whitlock C (1977) An algorithm for two-dimensional cutting problems. Oper. Res. 25:30–44.Link, Google Scholar
• Cintra GF, Miyazawa FK, Wakabayashi Y, Xavier EC (2008) Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation. Eur. J. Oper. Res. 191:61–85.Crossref, Google Scholar
• Dagum L, Enon R (1998) Openmp: An industry standard API for shared-memory programming. Comput. Sci. Engrg., IEEE 5:46–55.Crossref, Google Scholar
• Gilmore PC, Gomory RE (1965) Multistage cutting stock problems of two and more dimensions. Oper. Res. 13:94–120.Link, Google Scholar
• Gilmore PC, Gomory R (1966) The theory and computation of knapsack functions. Oper. Res. 14:1045–1074.Link, Google Scholar
• Harris M (2009) Optimizing parallel reduction in CUDA. NVIDIA Developer Zone. Accessed April 24, 2016, http://developer.download.nvidia.com/assets/cuda/files/reduction.pdf.Google Scholar
• Herz JC (1972) Recursive computational procedure for two-dimensional stock cutting. IBM J. Res. Development 16:462–469.Crossref, Google Scholar
• Jaros J, Pospichal P (2012) A fair comparison of modern CPUs and GPUs running the genetic algorithm under the knapsack benchmark. Di Chio C, Agapitos A, Cagnoni S, Cotta C, de Vega FF, Di Caro GA, Drechsler Ret al., eds. Applications of Evolutionary Computation, Lecture Notes in Computer Science, Vol. 7248 (Springer, Berlin), 426–435.Crossref, Google Scholar
• Katz GJ, Kider JT Jr (2008) All-pairs shortest-paths for large graphs on the GPU. Proc. 23rd ACM SIGGRAPH/EUROGRAPHICS Sympos. Graphics Hardware GH ’08 (Eurographics Association, Aire-la-Ville, Switzerland), 47–55.Google Scholar
• Koufaty D, Marr DT (2003) Hyperthreading technology in the Netburst microarchitecture. IEEE Micro Archive 23:56–65.Crossref, Google Scholar
• Lane TJ, Shukla D, Beauchamp KA, Pande VS (2013) To milliseconds and beyond: Challenges in the simulation of protein folding. Current Opinion Structural Biol. 23:58–65.Crossref, Google Scholar
• Liu Y, Wirawan A, Schmidt B (2013) CUDAsw++ 3.0: Accelerating Smith-Waterman protein database search by coupling CPU and GPU SIMD instructions. BMC Bioinformatics 14:Article no. 117.Crossref, Google Scholar
• Lund B, Smith JW (2010) A multi-stage CUDA kernel for Floyd-Warshall. CoRR abs/1001.4108. Accessed April 24, 2016, http://arxiv.org/abs/1001.4108.Google Scholar
• Mrozek D, Brożek M, Małysiak-Mrozek B (2014) Parallel implementation of 3D protein structure similarity searches using a GPU and the CUDA. J. Molecular Modeling 20:1–17.Crossref, Google Scholar
• NVIDIA (2007) NVIDIA developer zone. Accessed December 3, 2013, https://developer.nvidia.com/.Google Scholar
• Russo M, Sforza A, Sterle C (2013) An improvement of the knapsack function based algorithm of Gilmore and Gomory for the unconstrained two-dimensional guillotine cutting problem. Internat. J. Production Econom. 145:451–462.Crossref, Google Scholar
• Schulz C, Hasle G, Brodtkorb AR, Hagen TR (2013) GPU computing in discrete optimization. Part ii: Survey focused on routing problems. EURO J. Transportation Logist. 2:159–186.Crossref, Google Scholar
• Smith TF, Waterman MS (1981) Identification of common molecular subsequences. J. Molecular Biol. 147:195–197.Crossref, Google Scholar
• Steffen P, Giegerich R, Giraud M (2010) GPU parallelization of algebraic dynamic programming. Wyrzykowski R, Dongarra J, Karczewski K, Wasniewski J, eds. Parallel Processing and Applied Mathematics, Lecture Notes in Computer Science, Vol. 6068 (Springer, Berlin), 290–299.Crossref, Google Scholar
• Stone JE, Hardy DJ, Ufimtsev IS, Schulten K (2010) GPU-accelerated molecular modeling coming of age. J. Molecular Graphics Model. 29:116–125.Crossref, Google Scholar
• Wäscher G, Haussner H, Schumann H (2007) An improved typology of cutting and packing problems. Eur. J. Oper. Res. 183:1109–1130.Crossref, Google Scholar
• Wu C-C, Wei K-C, Lin T-H (2012) Optimizing dynamic programming on graphics processing units via data reuse and data prefetch with inter-block barrier synchronization. Parallel Distributed Systems (ICPADS), 2012 IEEE 18th Internat. Conf., Singapore, 45–52.Crossref, Google Scholar