Optimizing task schedules using an artificial immune system approach
Han Yu · 2008
Multiprocessor task scheduling is a widely studied optimization problem in the field of parallel computing. Many heuristic-based approaches have been applied to finding schedules that minimize the execution time of computing tasks on parallel processors. In this paper, we design an algorithm based on Artificial Immune Systems (AIS) to scheduling for heterogeneous computing environments. This approach distinguishes itself from many existing approaches in two aspects. First, it restricts the use of AIS to find optimal task-processor mapping, while taking advantage of heuristics used by deterministic scheduling approaches for task sequence assignment. Second, the calculation of the affinity takes into account both the solution quality and the distribution of population in the solution space. Empirical studies on benchmark task graphs show that this algorithm significantly outperforms HEFT, a deterministic algorithm. Further experiments also indicate that the algorithm is able to maintain high quality search even though a wide range of parameter settings are used.