Workflow Scheduling in Grid Based on Bacterial Foraging Optimization - Process-Aware Systems - page 21

Workflow Scheduling in Grid
Based on Bacterial Foraging Optimization

Feng Yao 1,2,3 , Jidong Ge 1,2,3,* , Chuanyi Li 1,2,3 , Yuhang Ge 1,2,3 , Haiyang Hu 1,2,4 ,
Yu Zhou 1,5 , Hao Hu 1 , and Bin Luo 1,2

1 State Key Laboratory for Novel Software Technology, Software Institute,
Nanjing University, Nanjing, China, 210093
[e-mail]
2 State Key Laboratory of Networking and Switching Technology
(Beijing University of Posts and Telecommunications), Beijing, China, 100876
3 Key Laboratory of Intelligent Perception and Systems for High-Dimensional Information,
Ministry of Education, Nanjing University of Science and Technology, Nanjing, China, 210094
4 School of Computer, Hangzhou Dianzi University, Hangzhou, China, 310018
5 College of Computer Science, Nanjing University of Aeronautics and Astronautics,
Nanjing, China, 210016

Abstract. Optimal assignment of a workflow application in heterogeneous
computing system is NP-complete in general case. We proposed the algorithm
based on bacterial foraging optimization technique for Grid resource
scheduling. This algorithm aims at minimizing the makespan of workflow
application. To show the advantage of this algorithm, we made comparison with
ant colony optimization and particle swarm optimization. The experiment
shows that this bacterial foraging optimization algorithm is better than the other
two algorithms in minimizing the makespan.

Keywords: Workflow scheduling, Grid computing, Bacterial foraging

optimization.

1 Introduction

Grid computing is the collection of computer resource from multiple locations to
reach a common goal. The main characteristics of grid computing are loosely
coupled, heterogeneous, and geographically dispersed. Task scheduling subsystem is
the core part of grid computing. Task scheduling subsystem assigns all tasks with the
corresponding resources based on the application requirement.
Grid applications are basically categorized into two types [2]; meta-task
application and DAG application. The former one describes independent tasks which
have no priority relations and data dependences among them. The latter one is known
as workflow application which is represented as Directed Acyclic Graph (DAG), in
which the nodes of the graph have dependences between them. The quality of a
* Corresponding author.