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

Author

Nessah, Rabia ; Chu, Chengbin ; Yalaoui, Farouk ; Kacem, Imed

Author_Institution

Inst. Charles Delaunay - OSI (CNRS FRE 2848), Univ. de Technologie de Troyes

Volume

1

fYear

2006

fDate

4-6 Oct. 2006

Firstpage

1047

Lastpage

1053

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²) 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

computational complexity; single machine scheduling; tree searching; branch-and-bound algorithm; lower bound; release dates; single machine scheduling problem; strongly NP-hard problem; total completion time minimization; Lagrangian functions; Linear programming; Open systems; Polynomials; Processor scheduling; Scheduling algorithm; Single machine scheduling; Systems engineering and theory; Testing; Release dates; Scheduling; Splitting; Total weighted completion times; lower bounds; single machine;

fLanguage

English

Publisher

ieee

Conference_Titel

Computational Engineering in Systems Applications, IMACS Multiconference on

Conference_Location

Beijing

Print_ISBN

7-302-13922-9

Electronic_ISBN

7-900718-14-1

Type

conf

DOI

10.1109/CESA.2006.4281801

Filename

4281801