Branch‐and‐bound algorithm for total weighted tardiness minimization on parallel machines under release dates assumptions

This paper deals with the parallel‐machine scheduling problem with the aim of minimizing the total (weighted) tardiness under the assumption of different release dates. This problem has been proven to be NP‐hard. We introduce some new lower and upper bounds based on different approaches. We propose a branch‐and‐bound algorithm to solve the weighted and unweighted total tardiness. Computational experiments were performed on a large set of instances and the obtained results showed that our algorithms are efficient.