A Branch and bound for 1|ri| wiCi, Scheduling Problem - Archive ouverte HAL Access content directly
Conference Papers Year :

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

(1) , (1) , (1) , (1)
1

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

Dates and versions

hal-02473395 , version 1 (10-02-2020)

Identifiers

Cite

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⟩

Collections

CNRS UTT LOSI
16 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More