Scheduling a directed acyclic graph (DAG) which represents theprecedence relations of the tasks of a parallel program in a distributedcomputing system (DCS) is known as an NP-complete problem except forsome special cases. Many heuristic-based methods have been proposedunder various models and assumptions. A DCS can be classified in twotypes according to the characteristics of the processors on a network: adistributed homogeneous system (DHOS) and a distributed heterogeneoussystem (DHES). The paper defines a general model for a DHOS and a DHESand presents a genetic algorithm (GA) to solve the task schedulingproblem in the defined DCS. The performance of the proposed GA iscompared with the list scheduling algorithm in a DHOS and with theone-level reach-out greedy algorithm (OLROG) in a DHES. The proposed GAhas shown better performance in various environments than otherscheduling methods
展开▼
