Skip to Main content Skip to Navigation
Conference papers

A branch and bound algorithm to minimize total weighted completion time on identical parallel machines with job release dates

Abstract : In this paper, we consider an identical parallel machine scheduling problem with release dates. The objective is to minimize the total weighted completion time. This problem is know to be strongly NP-hard. We propose two lower bounds. We present an efficient heuristic, we also propose some dominance properties. A branch and bound algorithm in which the heuristic, the lower bounds and the dominance properties are incorporated is proposed and tested on a large set of randomly generated instances
Complete list of metadata

https://hal-utt.archives-ouvertes.fr/hal-02473383
Contributor : Daniel Gavrysiak Connect in order to contact the contributor
Submitted on : Monday, February 10, 2020 - 4:48:39 PM
Last modification on : Friday, August 27, 2021 - 3:14:07 PM

Identifiers

Collections

UTT | CNRS

Citation

Rabia Nessah, Farouk Yalaoui. A branch and bound algorithm to minimize total weighted completion time on identical parallel machines with job release dates. 2006 International Conference on Service Systems and Service Management, Oct 2006, Troyes, France. pp.1192-1198, ⟨10.1109/ICSSSM.2006.320678⟩. ⟨hal-02473383⟩

Share

Metrics

Record views

52