Cutting Stock Problems arise in many industries where large stock sheets of a given material must be cut into smaller pieces. Many algorithms have been proposed for solving each of the problem formulations. We present different implementations based on Viswanathan and Bagchi?s algorithm to solve the Two-Dimensional Cutting Stock Problem (2DCSP). One approximation parallelizes the generation of new builds from different subproblems. Also a highly efficient data structures to store subproblems are introduced, allowing to provide a parallel implementation where the generation of new subproblems from a particular one can be distributed. The OpenMP tool has been used for the parallel implementations and some computational results are presented.