The scheduling problem with learning effects on two parallel machines is considered in the paper. The objective is to minimize the makespan. First, we discuss the NP-hardness of this problem. Next, we establish the integer programming model to find the optimal solution. Then, based on the simulated annealing algorithm, we propose an approximation algorithm SA and prove that the algorithm SA converges to global optimal solution with probability 1. Finally, we analyze the performance of the algorithm SA by numerical simulation. The results of numerical simulation show that the algorithm SA can reach 99% of the optimal value, it is an effective algorithm for the problem.