Title: Climbing depth-bounded discrepancy search for solving hybrid flow shop problems

Authors: Abir Ben Hmida, Marie-Jose Huguet, Pierre Lopez, Mohamed Haouari

Addresses: Universite de Toulouse, LAAS-CNRS, 7 avenue du Colonel Roche, Toulouse, France; Ecole Polytechnique de Tunisie, Unite ROI, La Marsa, Tunisia. ' Universite de Toulouse, LAAS-CNRS, 7 avenue du Colonel Roche, Toulouse, France. ' Universite de Toulouse, LAAS-CNRS, 7 avenue du Colonel Roche, Toulouse, France. ' Ecole Polytechnique de Tunisie, Unite ROI, La Marsa, Tunisia; Faculty of Business Administration, Bilkent University, Ankara, Turkey

Abstract: This paper investigates how to adapt some discrepancy-based search methods to solve Hybrid Flow Shop (HFS) problems in which each stage consists of several identical machines operating in parallel. The objective is to determine a schedule that minimises the makespan. We present here an adaptation of the Depth-bounded Discrepancy Search (DDS) method to obtain near-optimal solutions with makespan of high quality. This adaptation for the HFS contains no redundancy for the search tree expansion. To improve the solutions of our HFS problem, we propose a local search method, called Climbing Depth-bounded Discrepancy Search (CDDS), which is a hybridisation of two existing discrepancy-based methods: DDS and Climbing Discrepancy Search (CDS). CDDS introduces an intensification process around promising solutions. These methods are tested on benchmark problems. Results show that discrepancy methods give promising results and CDDS method gives the best solutions. [Received 27 October 2006; Revised 27 February 2007; Accepted 8 March 2007].

Keywords: flow shop scheduling; hybrid flow shops; HFS; discrepancy search methods; climbing depth-bounded discrepancy search; CDDS; lower bounds; LBs; heuristics; parallel machines; local search.

DOI: 10.1504/EJIE.2007.014110

European Journal of Industrial Engineering, 2007 Vol.1 No.2, pp.223 - 243

Published online: 20 Jun 2007 *

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