Fine and Coarse-grained Parallel Algorithms for the 2D Cutting Stock Problem

This work analyses two different approaches to parallelise an exact algorithm for the solution of the Constrained Two-Dimensional Cutting Stock Problem. A fine-grained model based on the parallel execution of the generation loops is implemented through a shared-memory model using the OpenMP tool. Also, a coarse-grained model based on the parallel execution of the search loop and in the introduction of efficient synchronisation and load balancing schemes is implemented through a distributed-memory model using MPI. As a novelty, we have incorporated into the models the checking of dominance and duplication rules, thus affecting the search space and so, the operation of the parallelisations. In the experimental evaluation it is demonstrated that, even when the domination/duplication tests are applied to the parallel algorithms, they are able to obtain an important improvement over the sequential approach.