An integrated technique for task matching and scheduling onto distributed heterogeneous computing systems

This paper presents a problem-space genetic algorithm (PSGA)-based technique for efficient matching and scheduling of an application program that can be represented by a directed acyclic graph, onto a mixed-machine distributed heterogeneous computing (DHC) system. PSGA is an evolutionary technique that combines the search capability of genetic algorithms with a known fast problem-specific heuristic to provide the best-possible solution to a problem in an efficient manner as compared to other probabilistic techniques. The goal of the algorithm is to reduce the overall completion time through proper task matching, task scheduling, and inter-machine data transfer scheduling in an integrated fashion. The algorithm is based on a new evolutionary technique that embeds a known problem-specific fast heuristic into genetic algorithms (GAs). The algorithm is robust in the sense that it explores a large and complex solution space in smaller CPU time and uses less memory space as compared to traditional GAs. Consequently, the proposed technique schedules an application program with a comparable schedule length in a very short CPU time, as compared to GA-based heuristics. The paper includes a performance comparison showing the viability and effectiveness of the proposed technique through comparison with existing GA-based techniques. (C) 2002 Elsevier, Science (USA)