Although computer systems can assist rescheduling experts and have recently been utilized to restore disrupted train operations, they are not so helpful in decreasing dispatcher workloads. This is because they lack the intelligence that would enable them to create rescheduling plans automatically. In this paper, we propose an algorithm for automatic train rescheduling. Firstly, we proposed using the causes of passenger dissatisfaction as rescheduling plan criteria and to regard the problem of train rescheduling as a constraint optimization problem in which the degree of passenger dissatisfaction should be minimized. Then we introduced an algorithm for train rescheduling designed as a combination of Program Evaluation and Review Technique (PERT) and metaheuristics. We have shown some experimental results derived from applying the algorithm to data from existing train schedules.