Skip to Main content Skip to Navigation
Conference papers

A Branch and bound for 1|ri| wiCi, Scheduling Problem

Rabia Nessah 1 Chengbin Chu 1 Farouk Yalaoui 1 Imed Kacem 1
1 LOSI - Laboratoire d'Optimisation des Systèmes Industriels
ICD - Institut Charles Delaunay
Abstract : In this paper, we consider a single machine scheduling problem with release dates. The objective is to minimize the total completion time. This problem is know to be strongly NP-hard. We propose two new lower bounds that can be computed in O(n 2 ) and in O(n log n) time respectively. We also propose some dominance properties. A branch-and-bound algorithm in which the lower bounds and the dominance properties are incorporated is proposed and tested on a large set of instances
Keywords : Processor scheduling Single machine scheduling Systems engineering and theory Scheduling algorithm Open systems Testing Linear programming Lagrangian functions Polynomials
Document type :
Conference papers
Complete list of metadata
https://hal-utt.archives-ouvertes.fr/hal-02473395
Contributor : Daniel Gavrysiak Connect in order to contact the contributor
Submitted on : Monday, February 10, 2020 - 4:52:20 PM
Last modification on : Friday, August 27, 2021 - 3:14:07 PM

Identifiers

Collections

UTT | CNRS

`

Citation

Rabia Nessah, Chengbin Chu, Farouk Yalaoui, Imed Kacem. A Branch and bound for 1|ri| wiCi, Scheduling Problem. Multiconference on "Computational Engineering in Systems Applications, Oct 2006, Beijing, China. pp.1047-1053, ⟨10.1109/CESA.2006.4281801⟩. ⟨hal-02473395⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

51