The blockage of the high-speed railway segment may seriously affect the original timetable of the train. If it happens, the dispatcher needs to adjust the timetable. This study focuses on how to reschedule the timetable without changing the sequence of trains that are affected by the segment blockage. A train rescheduling model is formulated with aiming at minimizing the sum of the delay time of all trains in each station, and all constraints of the model is used to ensure the safety of trains. And a multi-stage variable neighborhood descent algorithm is proposed to solve the problem that it takes a long time to get the optimal or suboptimal solution. In the first and second stages of the algorithm, variable neighborhood descent combined with tabu table is used to quickly ascertain the trains which can maintain the original timetable after several adjustments, and then adjust other trains in the third stage. Finally, taking Xi’an-Chengdu Passenger Dedicated Line and the timetable of a single day as an example, the validity and real-time performance of the algorithm is verified by getting the timetable adjusted under various interval failure scenarios.