A GRASP for a resource-constrained scheduling problem. (14th June 2010)

• Record Type: Journal Article
• Authors: Sirdey, Renaud; Carlier, Jacques; Nace, Dritan
• Is Part Of: International journal of innovative computing and applications. Volume 2:Number 3(2010)
• Page Start: 143
• Page End: 149
• Publication Date: 2010-06-14
• Subjects: combinatorial optimisation -- GRASP -- distributed systems -- operational research -- telecommunications -- resource-constrained scheduling -- metaheuristics; Evolutionary computation -- Periodicals; Neural networks (Computer science) -- Periodicals; Genetic programming (Computer science) -- Periodicals; Biologically-inspired computing -- Periodicals; Swarm intelligence -- Periodicals; Quantum computers -- Periodicals; 006.3
• Languages: English
• ISSNs: 1751-648X

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.