Title: MILP methods for the S-stage flexible flow shop scheduling problem

Authors: Nadia Chaabane; Racem Mellouli; Faouzi Masmoudi; Chengbin Chu

Addresses: Université de Sfax, Unité de Mécanique, Modélisation et Productique, Ecole Nationale d'Ingénieurs de Sfax, B.P. 1173, 3038 Sfax, Tunisie. ' Université de Sfax, Unité de Recherche Gestion Industrielle et Aide à la Décision, Ecole Supérieure de Commerce de Sfax, B.P. 1081, 3018 Sfax, Tunisie. ' Université de Sfax, Unité de Mécanique, Modélisation et Productique, Ecole Nationale d'Ingénieurs de Sfax, B.P. 1173, 3038 Sfax, Tunisie. ' Laboratoire Génie Industriel, Ecole Centrale Paris, 92295 Châtenay-Malabry Cedex, France

Abstract: This paper studies the flexible flow shop (FFS) NP-hard scheduling problem with the availability constraints to minimise the makespan. We used implicitly Branch and Bound through developing three different new mixed integer linear programming (MILP) to model the problem based on different definitions of the decision variables. We studied the efficiency of the model proposed in terms of a computational resolution and of the quality of the linear lower bound by using ILOG-Cplex solver. The experimentations which are carried out show that we can optimally solve the problems up to ten jobs and within four stages using three parallel machines per stage within several minutes of process time (CPU). We find that two proposed MILP show good results in terms of the quality of the linear lower bound obtained by the relaxation of the integrity constraints of this model.

Keywords: MILP; flexible flow shops; flow shop scheduling; modelling; operations management; availability constraints; total completion times; mixed integer linear programming.

DOI: 10.1504/IJMOM.2012.046337

International Journal of Modelling in Operations Management, 2012 Vol.2 No.2, pp.138 - 152

Published online: 21 Aug 2014 *

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