Algorithms for capability-based resource management - Search algorithms for capability-based resources in distributed resource management systems

Abstract

This master thesis investigates and answers the question if it can be efficient to define resources in a resource system through their capabilities. If resources are abstracted to a set of capabilities that describes the resource's use, searching for these resources will be easier given a capability requirement. This way, a resource satisfies one or more required capabilities and is thus replaceable with other resources that satisfy the same required capabilities. This concept eases the work for a user, who is not required to be a domain expert, and all he has to do is to define a capability requirement. Only specifying a resource's capabilities requires domain knowledge. This perspective on resources becomes a natural step for organizations that define their tasks and missions through capability requirements, such as a rescue service. The problem to find suitable resources given a capability requirement is fundamentally a matching problem where the problem is to decide whether a resource should be included or not depending on the context of the capability requirement. Numerous of algorithms of different types have been evaluated for this problem which turns out to be efficiently solvable. Mainly two algorithms are recommended, binary integer programming – a constrained version of linear programming as well as a greedy algorithm.