Personnel scheduling aims at determining the cheapest work schedules to cover the demand for one or more tasks at each period of a given horizon. During the operations, several minor disruptions such as delays or absences of employees can occur and must be handled in real time without a significant change in the planned schedule. In this paper, we develop a fast re-scheduling heuristic that corrects minor disruptions in a context where employees can be assigned to a wide variety of shifts, starting and ending at different times. This heuristic consists of correcting a disruption by proposing a set of solutions that realize a good compromise between the cost and the number of modifications. The heuristic mainly uses a state graph whose construction and search for solutions corresponding to non-dominated paths, are based on a fundamental and "probabilistic" study. Computational experiments conducted on practical problem instances involving up to 95 employees have shown the effectiveness of the proposed heuristic. It can find all the exact solutions that realize a good compromise cost/modifications, in a search zone set by the employer, in less than one second on average for more than 96% of the scenarios generated.