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

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

Domains: Computer Science [cs]; Operations Research [cs.RO]; Computer Science [cs]; Data Structures and Algorithms [cs.DS]

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⟩