Les problèmes de gestion de personnel visent à déterminer les horaires de travail les moins coûteux pour couvrir la demande d'une ou plusieurs tâches à chaque période d'un horizon donné. Durant l'opération, plusieurs petites perturbations, comme les retards ou les absences d'employés, surviennent et doivent être traitées en temps réel sans trop modifier l'horaire planifié. Dans cet article, nous développons une heuristique de ré-optimisation rapide qui corrige les petites perturbations dans un contexte où les employés peuvent être assignés à une grande variété de quarts, débutant et s'achevant à divers moments. Cette heuristique consiste à corriger la perturbation en proposant un ensemble de solutions qui réalisent un compromis entre le coût et le nombre de modifications. L'heuristique utilise principalement un graphe d'états dont la construction et la recherche des solutions correspondantes aux chemins non-dominés, sont basées sur une étude fondamentale et "probabiliste". Les tests numériques menés sur des instances de problèmes réels allant jusqu'à 95 employés ont montré l’efficacité de l'heuristique proposée. Celle-ci arrive à trouver toutes les solutions exactes qui réalisent un bon compromis coût/modifications, dans une zone de recherche fixée par l'employeur, en moins d'une seconde en moyenne pour plus de 96% des scénarios générés.