TASK MATCHING AND SCHEDULING IN HETEROGENEOUS COMPUTING ENVIRONMENTS USING A GENETIC-ALGORITHM-BASED APPROACH

To exploit a heterogeneous computing (HC) environment, an application task may be decomposed into subtasks that have data dependencies. Subt ask matching and scheduling consists of assigning subtasks to machines , ordering subtask execution for each machine, and ordering intermachi ne data transfers. The goal is to achieve the minimal completion time for the task. A heuristic approach based on a genetic algorithm is dev eloped to do matching and scheduling in HC environments. It is assumed that the matcher/scheduler is in control of a dedicated HC suite of m achines. The characteristics of this genetic-algorithm-based approach include: separation of the matching and the scheduling representations , independence of the chromosome structure from the details of the com munication subsystem, and consideration of overlap among all computati ons and communications that obey subtask precedence constraints. It is applicable to the static scheduling of production jobs and can be rea dily used to collectively schedule a set of tasks that are decomposed into subtasks. Some parameters and the selection scheme of the genetic algorithm were chosen experimentally to achieve the best performance. Extensive simulation tests were conducted. For small-sized problems ( e.g., a small number of subtasks and a small number of machines), exha ustive searches were used to verify that this genetic-algorithm-based approach found the optimal solutions. Simulation results for larger-si zed problems showed that this genetic-algorithm-based approach outperf ormed two nonevolutionary heuristics and a random search. (C) 1997 Aca demic Press.