Title: A GRASP for a resource-constrained scheduling problem

Authors: Renaud Sirdey, Jacques Carlier, Dritan Nace

Addresses: CEA LIST, Embedded Real Time Systems Lab, Point Courrier 94, 91191 Gif-sur-Yvette Cedex, France. ' UMR CNRS Heudiasyc, Universite de Technologie de Compiegne, Centre de Recherches de Royallieu, BP 20529, 60205 Compiegne Cedex, France. ' UMR CNRS Heudiasyc, Universite de Technologie de Compiegne, Centre de Recherches de Royallieu, BP 20529, 60205 Compiegne Cedex, France

Abstract: This paper is devoted to the approximate resolution of a strongly NP-hard real world resource-constrained scheduling problem, which arises in relation to the operability of certain high availability real time distributed systems. We present a fast and pragmatic algorithm based on the GRASP metaheuristic and, building on previous research on exact resolution methods, extensive computational results demonstrating its practical ability to find solutions within a few percents to optimality on a wide spectrum of hard instances.

Keywords: combinatorial optimisation; GRASP; distributed systems; operational research; telecommunications; resource-constrained scheduling; metaheuristics.

DOI: 10.1504/IJICA.2010.033646

International Journal of Innovative Computing and Applications, 2010 Vol.2 No.3, pp.143 - 149

Received: 02 Mar 2009
Accepted: 05 Mar 2010

Published online: 13 Jun 2010 *

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