In some factory, job has been processed in batches which consist of the processing procedures basical identical jobs, so all jobs have the same normal processing time. The actual processing time is affected by th “learning effect”. The batch scheduling problem with learning effect on a single-machine to minimize the total tardiness is discussed, which is a NP-hard problem. For this problem, we model and propose a dynamic programming(DP) algorithm and a simulated annealing(SA) algorithm. The solution time variation trend of the both algorithms and the errors variation trend of SA with different problem sizes are analyzed by experimental tests. We have compared the performance of the SA to other classical rules which are usually applied in real-life. The results show that the DP can get exact solution and more suit the small size problems whose batch number is less than 13. Comparing to other classical rules, the SA is effective because of 20% decline in object value by using the SA. The large size problems can be solved better by using the SA, and the variation trend of the solution time and the errors with controlling parameters changed is analyzed.