Title: Efficient upper and lower bounding methods for flowshop sequence-dependent group scheduling problems

Authors: Taha Keshavarz; Nasser Salmasi

Addresses: Department of Industrial Engineering, Sharif University of Technology, P.O. Box 11365-8639, Tehran, Iran ' Department of Industrial Engineering, Sharif University of Technology, P.O. Box 11365-8639, Tehran, Iran

Abstract: In this research, a permutation flowshop sequence-dependent group scheduling problem with minimisation of total completion time is considered. Since the problem is shown to be strongly NP-hard, a hybrid genetic (HG) algorithm is proposed. The only available lower bounding (LB) method for the proposed research problem in the literature based on branch and price (B&P) algorithm is also enhanced by proposing efficient method to solve sub-problems and proposing a better branching rule. A statistical comparison shows that both the proposed HG algorithm and the proposed LB have better performance than the other methods from the literature with an average 5.96% percentage gap. [Received 13 December 2011; Revised 24 May 2012; Revised 15 November 2012; Accepted 16 November 2012]

Keywords: flowshop scheduling; group scheduling; sequence-dependent setup times; branch and price; lower bound; metaheuristics; upper bound; hybrid genetic algorithms.

DOI: 10.1504/EJIE.2014.060997

European Journal of Industrial Engineering, 2014 Vol.8 No.3, pp.366 - 387

Published online: 28 Jun 2014 *

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