Le problème du partitionnement d'ensemble est un problème de programmation en nombres entiers très étudié. Le problème consiste à trouver une partition de tâches de coût minimal parmi un ensemble de parties admissibles. Les algorithmes primaux spécialisés ont montré leur capacité à résoudre ces problèmes rapidement. Ces algorithmes trouvent une séquence améliorante de solutions entières jusqu'à la solution optimale. Dans cet article, nous présentons un algorithme primal pour une généralisation de ce problème, généralisation où certaines taches doivent être couverte plusieurs fois, un nombre de fois déterminé à l'avance. Le graphe des solutions entières, où les arcs sont les déplacements possibles avec des pivots du simplexe, n'est pas connexe. L'idée est d'ajouter des variables qui permettent de se déplacer d'une solution à des solutions qui ne sont pas directement voisines dans le graphe afin de restaurer la connexité. Nous montrons ensuite, qu'en pratique, notre méthode est entre 2 à 5 fois plus rapide que les méthodes traditionnelles (CPLEX) sur de larges instances de problèmes de rotations d'équipage aérien.