This paper presents a hybrid Pareto-based local search (PLS) algorithm for solving the multi-objective flexible job shop scheduling problem. Three minimization objectives-the maximum completion time (makespan), the total workload of all machines, and the workload of the critical machine are considered simultaneously. In this study, several well-designed local search approaches are proposed, which consider the problem characteristics and thus can hold fast convergence ability while keep rich population diversity. Then, an external Pareto archive is developed to memory the Pareto optimal solutions found so far. In addition, to improve the efficiency of the scheduling algorithm, a speed-up method is devised to decide the domination status of a solution with the archive set. Experimental results on two well-known benchmarks show the efficiency of the proposed hybrid algorithm. It is concluded that the PLS algorithm is superior to the very recent algorithms in term of both search quality and computational efficiency.