A heuristic-genetic algorithm for client web service scheduling constrained by one I/O port

摘要

Enhancing heterogeneous distributed computing systems requires effective scheduling approach to achieve high performance and satisfy the clients request. Many scheduling algorithms have been proposed to map and order clients requests running on a suitable processor at the minimum makespan and maximum resource utilization. However, they do not take into account the task scheduling under bounded number of I/O port constraint which is a realistic communications model between client and server. Based on the I/O port constraint, this paper proposes a one I/O port task scheduling using a hybrid heuristicgenetic algorithm to achieve minimum completion time. For practical scenario, web service workflow represented by the Directed Acyclic Graph (DAG) of tasks is implemented as an input task set. The proposed algorithm focuses on sending the clients request of web services and receiving results having minimum makespan and delay. Unlike Genetic Algorithm (GA) providing near optimal results but high time complexity, the proposed approach named Critical Path with Genetic Algorithm (CPGA) incorporates GA to produce the good quality schedule with lower processing time. Preliminary result of fair comparisons with existing scheduling methods shows that the proposed approach outperforms them in terms of minimum makespan and delay.