In this study, we address a rescheduling problem in parallel machine environments under machines failures. To make a balance between efficiency and stability of the reschedules, we consider the total number of tardy jobs as efficiency measure and the number of jobs processed on different machines in the initial and revised schedules as a stability measure. Then a heuristic algorithm which synthesizes beam search (BS) and repair-based constraint satisfaction algorithm is developed. Numerical experiments are processed to evaluate the performance and efficiency of the proposed algorithm. The experimental results show that the proposed algorithm improves the results significantly.