This SGER proposal seeks to develop and simulate heuristic scheduling algorithms to efficiently map tasks to heterogeneous cluster systems in grid environments. Two approaches will be taken to the algorithm development and investigation: list scheduling and clustering. The list scheduling approach involves intelligent matching of tasks to cluster components, prioritizing critical tasks in the list, and duplicating task duplication where appropriate. Task duplication will be the subject of specific study, in analyzing tradeoffs in the cost of duplication against overall performance gains. Performance bounds will be calculated for developed schedules, and the schedules will be evaluated using random Directed Acyclic Graphs (DAGs).
