Title: Modelling and solving a multimode and multisite industrial problem: Lagrangean relaxation and heuristic approaches

Authors: Michel Gourgand, Sylverin Kemmoe Tchomte, Alain Quilliot

Addresses: Laboratoire d'Informatique de Modelisation et d'Optimisation, des Systemes (LIMOS), Campus Scientifique des Cezeaux, Universite Blaise Pascal, 63177 Aubiere, Cedex, France. ' Laboratoire d'Informatique de Modelisation et d'Optimisation, des Systemes (LIMOS), Campus Scientifique des Cezeaux, Universite Blaise Pascal, 63177 Aubiere, Cedex, France. ' Laboratoire d'Informatique de Modelisation et d'Optimisation, des Systemes (LIMOS), Campus Scientifique des Cezeaux, Universite Blaise Pascal, 63177 Aubiere, Cedex, France

Abstract: In this paper, we tackle the problem of scheduling multisite and multimode activities in order to minimise the project duration that meets the constraints imposed by limited resources. The industrial system is composed of many production sites, and each site has its own resources called local resources, and every site can receive resources called global resources. The objective is to support the repartition of all the lots of pieces on different sites in a cooperative way, and to assign resources. The system reduced to only one site highlights the well-known problem of the Multimode Resource-Constrained Project Scheduling Problem (MRCPSP). We propose a mathematical programming approach based on competitive feasible solutions and strong lower bounds, within quite reasonable computation times. The basic ingredients of this approach are the Lagrangean relaxation. We also propose a method based on stochastic descent with restart to compute large-sized industrial instances. The experiments show that this technique gives solutions close to the optimum. This seems to indicate that these resolution methods are good candidates for real industrial problems. [Received: 1 February 2007; Revised: 31 July 2007; Accepted: 31 October 2007]

Keywords: resource-constrained project scheduling problem; RCPSP; multisite; multimode scheduling; Lagrangean relaxation; stochastic descent; heuristics; project duration.

DOI: 10.1504/EJIE.2008.017351

European Journal of Industrial Engineering, 2008 Vol.2 No.2, pp.190 - 206

Published online: 01 Mar 2008 *

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