A Branch-and-Bound to solve the scheduling problem Pm/r_j/ΣT_j

International audienceThis paper presents the first study for the total tardiness minimization on parallel machine scheduling problem with different release dates of jobs. In this problem, a set of jobs has to be scheduled, without any preemption or splitting, on identical parallel machine. Each job has a due date and a release date. A polynomial lower bound is proposed using a relaxation procedure. A set of dominance properties are also established. A branch and bound algorithm is developed by taking into account the theoretical properties, lower and also upper bounds. This exact method has been tested on a large number of randomly generated problems. The obtained results are promising