Title: Scheduling hybrid flow shop problem with non-fixed availability constraints

Authors: Walid Besbes, Jacques Teghem, Taicir Loukil

Addresses: Unite de Recherche LOGIQ, Faculte des Sciences Economiques et de Gestion de Sfax, Route de l'aerodrome km4, BP 1088, 3018 Sfax, Tunisie. ' Laboratory of Mathematics and Operational Research, Faculte Polytechnique de Mons, Rue de Houdain 9, B-7000 Mons, Belgium. ' Unite de recherche LOGIQ, Faculte des Sciences Economiques et de Gestion de Sfax, Route de l'aerodrome km 4, BP1088, 3018 Sfax, Tunisie

Abstract: In this study, we deal with a k-stage hybrid flow shop scheduling problem under availability constraints (HFSPAC). In such a problem, machines are not continuously available due to preventive maintenance tasks. Our study aims to provide a good approximate solution to this specific problem with the makespan minimisation as the performance measure. Few studies exist in the literature dealing with the HFSPAC. We consider in this paper two variants to tackle this problem. In the first, the starting times of maintenance tasks are fixed, whereas in the second variant, maintenance must be performed on given time windows. In this last case, a theoretical analysis is elaborated based on the machine idle time to decide which action to perform between left-shifting or right-shifting the maintenance task in the window. Due to the NP-hardness of the HFSPAC, an approximate approach, based on a genetic algorithm (GA), is proposed to minimise the makespan. Computational experiments are performed on randomly generated instances to show the efficiency of the proposed variant (flexibility of the starting times of the maintenance tasks) in terms of makespan minimisation. Moreover, a correlation function computation is proposed to statistically analyse these experiments. [Received 7 November 2008; Revised 30 May 2009; Accepted 6 December 2009]

Keywords: flow shop scheduling; hybrid flow shops; availability constraints; genetic algorithms; schedules; k-stage; preventive maintenance; makespan minimisation; performance measures; starting times; time windows; idle time; flexibility.

DOI: 10.1504/EJIE.2010.035652

European Journal of Industrial Engineering, 2010 Vol.4 No.4, pp.413 - 433

Published online: 01 Oct 2010 *

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