This research investigates the application of meta-heuristic algorithms to a scheduling problem called permutation manufacturing-cell flow shop (PMFS) from two perspectives. First, we examine the effect of using different solution representations (Snew and Sold) while applying Tabu-search algorithm. Experimental results reveal that Tabu-Snew outperforms Tabu-Sold. The rationale why Tabu-Snew is superior is further examined by characterizing the intermediate outcomes of the evolutionary processes in these two algorithms. We find that the superiority of S new is due to its relatively higher degree of freedom in modeling Tabu neighborhood. Second, we propose a new algorithm GA-Tabu-Snew, which empirically outperforms the state-of-the-art meta-heuristic algorithms in solving the PMFS problem. This research highlights the importance of solution representation in the application of meta-heuristic algorithm, and establishes a significant milestone in solving the PMFS problem.