This study applies HTS to solve RPFS scheduling problems with objective to minimize makespan. In pure TS, if the solution cannot escape from local optimum, the improvement rate can hardly be increased even a great amount of computational time is spent. The proposed HTS is used to improve the efficiency of TS. The heuristic method is hybridized into pure TS to find better solution regions. In RPFS, job-based encoding is adopted to deal with different types of problems. The results show that HTS obtains favorable solutions within reasonable time. For small problems, the percentage of HTS finding optimal solutions is near 100%. For medium problems,