Title: A branch and bound algorithm to minimise the total tardiness in the two-machine permutation flowshop scheduling problem with minimal time lags

Authors: Imen Hamdi; Ammar Oulamara; Taïcir Loukil

Addresses: Research Unit LOGIQ, High Institute of Industrial Management, University of Sfax, Sfax 3018, Tunisia ' Université Lorraine, LORIA-UMR7503, Parc de Saurupt, 54042 Nancy Cedex, France ' Research Unit LOGIQ, High Institute of Industrial Management, University of Sfax, Sfax 3018, Tunisia

Abstract: In this paper, we consider the two-machine permutation flowshop scheduling problem with minimal time lags and the objective of minimising total tardiness. Dominance criteria are developed to establish precedence constraints between jobs in an optimal schedule and a lower bound on the total tardiness of the problem is derived. A branch and bound algorithm for this problem is developed to reach an optimal solution using lower bound and dominance criteria. Also, computationally efficient heuristics are proposed. Results of computational experiments on randomly generated problems are reported.

Keywords: two-machine scheduling; permutation flowshops; flowshop scheduling; time lags; total tardiness; branch and bound.

DOI: 10.1504/IJOR.2015.070142

International Journal of Operational Research, 2015 Vol.23 No.4, pp.387 - 405

Received: 25 Jun 2013
Accepted: 05 Aug 2013
Published online: 28 Jun 2015 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article