A Branch-and-Bound to solve the scheduling problem Pm/r<sub>j</sub>/&#x003A3;T<sub>j</sub> - Université de technologie de Troyes Access content directly
Conference Papers Year :

A Branch-and-Bound to solve the scheduling problem Pm/rj/ΣTj


This 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.
Not file

Dates and versions

hal-02474703 , version 1 (11-02-2020)



Farouk Yalaoui. A Branch-and-Bound to solve the scheduling problem Pm/rj/ΣTj. 2006 International Conference on Service Systems and Service Management, Oct 2006, Troyes, France. pp.1199-1204, ⟨10.1109/ICSSSM.2006.320679⟩. ⟨hal-02474703⟩


11 View
0 Download



Gmail Facebook Twitter LinkedIn More