Automated Planning is a method used in artificial intelligence systems such as autonomous robots or automatic satellite control. While there already are some planning algorithms that make use of multi-core processors, this thesis proposes a parallelized version of the Graphplan algorithm. The proposed algorithm works by transforming plan extraction problems for different horizon lengths into the Boolean Satisfiability Problem (SAT) and solving multiple SAT formulas in parallel. Experiments based on the problem instances provided by the 2014 International Planning Competition show that this method results in a significant parallel speedup and is able to outperform the state-of-the-art SAT-based sequential planner Madagascar in some problem domains. A disadvantage of the proposed algorithm is high memory consumption for some problems with certain configurations.