Dans ce travail nous considérons le problème de séquencement consistant à minimiser la somme pondérée des complétions en présence de deadlines. Le meilleur algorithme actuellement connu pour le résoudre utilise une méthode de Branch and Bound. Nous étudions expérimentalement comment l'accélérer en relâchant la contrainte d'unicité des travaux dans un ordonnancement, c'est-à-dire en acceptant des ordonnancements avec des travaux dupliqués ou absents. Nous comparons deux techniques adaptées aux ordonnancements relâchés: l'Inclusion-Exclusion et l'association de pénalités aux travaux.