Skip to Main content Skip to Navigation
Conference papers

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

Abstract : 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.
Document type :
Conference papers
Complete list of metadatas
Contributor : Daniel Gavrysiak <>
Submitted on : Tuesday, February 11, 2020 - 3:30:20 PM
Last modification on : Thursday, April 23, 2020 - 9:34:02 AM





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⟩



Record views