Personnel scheduling consists of determining least-cost work schedules to cover the demand of multiple jobs expressed in number of employees per job and period of a given horizon. During the operations, minor disruptions to the planned schedule, such as employee lateness, often occur and must be addressed in real time without changing too much the schedule. In this paper, we develop a fast re-scheduling heuristic that can be used to correct such minor disruptions in a retail industry context where employees can be assigned to a wide variety of shifts, starting and ending at numerous times. This heuristic can compute a set of approximate Pareto-optimal solutions that achieve a good compromise between cost and number of shift changes. It can be seen as a labeling algorithm that partially explores a network defined by the edges of the convex hull of the solutions of an integer program. Theoretical insights are provided to support certain speedup rules. Computational experiments conducted on instances derived from real-life datasets involving up to $95$ employees show the heuristic efficiency. In less than one second on average, it can compute Pareto-optimal solutions for more than 98% of the tested scenarios.