Static heuristics for robust resource allocation of continuously executing applications

Shoukat Ali, Jong Kook Kim, Howard Jay Siegel, Anthony A. Maciejewski

Research output: Contribution to journalArticlepeer-review

17 Citations (Scopus)


We investigate two distinct issues related to resource allocation heuristics: robustness and failure rate. The target system consists of a number of sensors feeding a set of heterogeneous applications continuously executing on a set of heterogeneous machines connected together by high-speed heterogeneous links. There are two quality of service (QoS) constraints that must be satisfied: the maximum end-to-end latency and minimum throughput. A failure occurs if no allocation is found that allows the system to meet its QoS constraints. The system is expected to operate in an uncertain environment where the workload, i.e., the load presented by the set of sensors, is likely to change unpredictably, possibly resulting in a QoS violation. The focus of this paper is the design of a static heuristic that: (a) determines a robust resource allocation, i.e., a resource allocation that maximizes the allowable increase in workload until a run-time reallocation of resources is required to avoid a QoS violation, and (b) has a very low failure rate (i.e., the percentage of instances a heuristic fails). Two such heuristics proposed in this study are a genetic algorithm and a simulated annealing heuristic. Both were "seeded" by the best solution found by using a set of fast greedy heuristics.

Original languageEnglish
Pages (from-to)1070-1080
Number of pages11
JournalJournal of Parallel and Distributed Computing
Issue number8
Publication statusPublished - 2008 Aug

Bibliographical note

Funding Information:
This research was supported by the National Science Foundation under Contract No. CNS-0615170, by the DARPA/ITO Quorum Program through the Office of Naval Research under Grant No. N00014-00-1-0599, by the Colorado State University Center for Robustness in Computer Systems (funded by the Colorado Commission on Higher Education Technology Advancement Group through the Colorado Institute of Technology), and by the Colorado State University George T. Abell Endowment. Some of the equipment used was donated by Intel and Microsoft.


  • Genetic algorithm
  • Heterogeneous distributed computing
  • Resource allocation
  • Robustness
  • Shipboard computing
  • Simulated annealing
  • Static mapping
  • Task scheduling

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Artificial Intelligence


Dive into the research topics of 'Static heuristics for robust resource allocation of continuously executing applications'. Together they form a unique fingerprint.

Cite this