A branch and bound algorithm for the two-machine flowshop problem with unit-time operations and time delays. Issue 2 (7th March 2014)

• Record Type: Journal Article
• Authors: Moukrim, Aziz; Rebaine, Djamal; Serairi, Mehdi
• Is Part Of: RAIRO. Volume 48:Issue 2(2014)
• Page Start: 235
• Page End: 254
• Publication Date: 2014-03-07
• Subjects: Branch and bound, -- dominance rule, -- flowshop, -- lower and upper bounds, -- time delays; Operations research -- Periodicals; 658.4034
• DOI: 10.1051/ro/2014004
• Languages: English
• ISSNs: 0399-0559

Abstract

Abstract : In this paper we consider the problem of scheduling, on a two-machine flowshop, a set of unit-time operations subject to time delays with respect to the makespan. This problem is known to be\hbox{${\cal NP}$} 𝒩𝒫 -hard in the strong sense. We propose an algorithm based on a branch and bound enumeration scheme. This algorithm includes the implementation of new lower and upper bound procedures, and dominance rules. A computer simulation to measure the performance of the algorithm is provided for a wide range of test problems.