Approximate solution of a resource-constrained scheduling problem

This paper is devoted to the approximate solution of a strongly NP -hard resource-constrained scheduling problem which arises in relation to the operability of certain high availability real time distributed systems. We present an algorithm based on the simulated annealing metaheuristic and, buildin...

Full description

Saved in:
Bibliographic Details
Published in:Journal of heuristics 2009-02, Vol.15 (1), p.1-17
Main Authors: Sirdey, Renaud, Carlier, Jacques, Nace, Dritan
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Artificial Intelligence
Calculus of Variations and Optimal Control
Optimization
Heuristic
Management Science
Mathematics
Mathematics and Statistics
Operations Research
Operations Research/Decision Theory
Optimization algorithms
Scheduling
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper is devoted to the approximate solution of a strongly NP -hard resource-constrained scheduling problem which arises in relation to the operability of certain high availability real time distributed systems. We present an algorithm based on the simulated annealing metaheuristic and, building on previous research on exact solution methods, extensive computational results demonstrating its practical ability to produce acceptable solutions, in a precisely defined sense. Additionally, our experiments are in remarkable agreement with certain theoretical properties of our simulated annealing scheme. The paper concludes with a short discussion on further research.
ISSN:1381-1231
1572-9397
DOI:10.1007/s10732-007-9052-0