Cet article propose de nouvelles heuristiques pour le problème classique de l’ordonnancement non préemptif qui consiste à assigner n tâches à m machines parallèles identiques, avec pour objectif de minimiser le temps de terminaison. En partant de la méthode du List Scheduling (LS), utilisée par exemple dans LPT [Graham, 1969] ou SLACK [Della Croce & Scatamacchia, 2020], nous dérivons une stratégie d’exploration qui considère également l’assignation d’une tâche à la deuxième meilleure machine, en plus de la première, la seule habituellement traitée dans la littérature. Tout au long de l’exploration des solutions, nous ne conservons que la meilleure solution. Cette stratégie conduit à deux heuristiques, pensées dans le but d’accélérer la recherche de solutions. La première, nommée Branch & Parallelize LS (BPLS), parallélise les deux alternatives considérées pour chaque tâche. La seconde, appelée BBLS, applique une méthode Branch & Bound pour élaguer largement l’arbre des solutions. Dans le but d’obtenir un compromis entre le temps de calcul et la qualité de la solution, ces heuristiques sont paramétrées de manière à n’assigner qu’un sous-ensemble de tâches selon la stratégie de parcours. Hors de ce sous-ensemble, l’assignation est faite par LS classique, c’est-à-dire à chaque fois sur la première machine disponible. Nous montrons sur des exemples de la littérature que notre heuristique surpasse de nombreux algorithmes bien connus sur la grande majorité des in- stances considérées. Nous étudions également le sous-espace des instances pour lesquelles notre heuristique n’est pas capable de battre tous ces algorithmes. Enfin, nous proposons une heuristique ad hoc appelée MULTI-BBLS (MBBLS) qui consiste en de multiples appels à BBLS permettant de se classer premier même sur ce sous-espace d’instances.