Experimental Comparison of Heuristic and Optimal Resource Allocation Algorithms for Maximizing Allowable Workload in Dynamic, Distributed Real-Time Systems


This paper introduces a maximal allowable workload task allocation problem (MAW) to address a class of distributed real-time systems that have unpredictable execution times due to varying workload. It is known that worst case execution time analysis is not well suited for these systems. This problem seeks to maximize the upper bound of permissible workload in an allocation so that it can sustain major workload fluctuations without the need for reallocation. An answer to the problem is significant in that it increases robustness of the system by reducing expensive reallocation costs such as process migration, which degrades system performance. Previously in [12], we presented and compared several heuristic algorithms experimentally, including simulated annealing, hill-climbing and random search. This paper expands the set of algorithms to include tabu search, genetic algorithm, dynamic programming, and optimal branch-and-bound. The main contribution of this paper is the performance comparisons among these various well known heuristic and optimal algorithms applied to the MAW problem. Through simulation experiments, relative solution quality and time complexity of the algorithms were evaluated and tradeoffs were revealed.

Caso o link acima esteja inválido, faça uma busca pelo texto completo na Web: Buscar na Web

Biblioteca Digital Brasileira de Computação - Contato:
     Mantida por: