Mohana Oltikar's MS Thesis Abstract

Heuristics for Robust Resource Allocation in a Weather Data Processing System

MS, Colorado State University, May 2006

Co-Major Professors: H. J. Siegel and Anthony A. Maciejewski

Heterogeneous and distributed computes involves coordinated use of machines with varied capabilities to execute diverse task mixtures. A mapping or resource allocation involves allocating the resources in a way that optimizes some system performance measure.

The first part of this study defines a heterogeneous weather data processing system that is susceptible to uncertainties in data set arrival times. The resource allocation must be robust with respect to these uncertainties. The tasks to be executed by the data processing system are classified into three broad categories: telemetry, tracking and control (high priority); data processing (medium priority); and data research (low priority). The high priority tasks must be completed before considering medium and low priority tasks. The goal of this research is to find a resource allocation that minimizes makespan of the high priority tasks, and to find a mapping that maximizes a function of the completion time and priority of the medium and low priority tasks. Different heuristic techniques to find near optimal solutions are studied and their performance is compared to a mathematical bound.

For two-phase allocation problems like the one studied in the first part of this thesis, the initial ready time for the machines for the second phase is often derived from the finishing time given by some other mapping. Therefore in such cases it is desirable that each machine should have a small finishing time. The second part of this study proposes an iterative method to minimize the completion time of a set of tasks as well as the finishing time of individual machine. A static mapping environment where a set of tasks must be executed on a heterogeneous system is studied and the behavior of several heuristics for this approach is evaluated.