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 *