This work analyses the difficulties of parallelizing the best known sequential algorithm for the 2D Cutting Stock Problem. All the approaches to parallelize the algorithm strive against its highly irregular computation structure and its sequential nature. A distributed-memory parallel algorithm has been designed through a time-driven task intercommunication service. The service allows to introduce a load balancing scheme that tries to hide the non-homogeneous work load nature of the involved single tasks. Experimental results obtained for MVAPICH Infiniband and MPICH Gigabit Ethernet implementations prove the efficiency of the communication and balancing schemes and show the almost linear speedup achieved by the parallel algorithm.