Dynamic matching and scheduling of a class of independent tasks onto heterogeneous computing systems

Dynamic mapping (matching and scheduling) heuristics for a class of independent tasks using heterogeneous dis-tributed computing systems are studied. Two types of map-ping heuristics are considered: on-line and batch mode heuristics. Three new heuristics, one for batch and two for on-line, are introduced as part of this research. Simula-tion studies are performed to compare these heuristics with some existing ones. In total, five on-line heuristics and three batch heuristics are examined. The on-line heuristics con-sider, to varying degrees and in different ways, task affinity for different machines and machine ready times. The batch heuristics consider these factors, as well as aging of tasks waiting to execute. The simulation results reveal that the choice of mapping heuristic depends on parameters such as: (a) the structure of the heterogeneity among tasks and machines, (b) the optimization requirements, and (c) the ar-rival rate of the tasks. 1