The task sequence planning problem (TSPP) is one of the most significant combinatorial optimization problems. In this paper, we formulate the TSPP and prove that the optimal task sequence planning problem (OTSPP) is NP-complete based on the graph theory. We incorporate the idea of topological sorting into the solution and propose the exact method, named all topology sort minimum distance (ATS-MD). Given the shortcomings of the ATS-MD, the time complexity is very high. We use the idea of dynamic programming to reduce the search range of the algorithm and propose the dynamic programming based on topological relationship algorithm (DP-TR). However, both ATS-MD and DP-TR are unable to cope with largescale OTSPP. We present a hybrid genetic algorithm, genetic algorithm based on topological relationship (GA-TR), which can give an approximate solution to the large-scale OTSPP in a feasible time. The results of numerical experiments prove the validity of the three algorithms.