Information Technology Reference
In-Depth Information
scheduling plan can be measured using several optimization criteria, such as
minimizing the makespan (the completion time of the last task), meeting the deadline,
or within the budget. In this research, we consider the DAG application scheduling
problem with the most commonly used criteria, i.e. minimizing the makespan.
The goal of mapping tasks on grid resources has been proven to be NP-complete
[1]. In recent years, people have proposed a lot of heuristic algorithms and meta-
heuristic algorithm to solve this problem. Heuristic algorithms contain Min-min,
Max-min, Sufferage [3], XSufferage [4], Segemented Min-min [5], Qos Guided Min-
min [6], HEFT [7], etc. Meta-heuristic algorithm can also be applied to solve the
problem, such as Greedy Randomized Adaptive Search Process (GRASP) [8],
Genetic Algorithm (GA) [9], Simulated Annealing (SA) [10], Ant Colony
Optimization [14], Particle Swarm Optimization [15]. Jia Yu [11] provided a more
detailed overview of workflow scheduling problem solution.
The Bacterial Foraging Optimization (BFO) algorithm [12] was proposed by
Passino et al. It is a population-based numerical optimization algorithm based on
foraging behavior of Escherichia coli bacteria. In paper [13], they use Bacterial
Foraging Optimization to resource scheduling in grid computing. However, they are
dealing with meta-task scheduling problem.
In this paper, we proposed a workflow scheduling algorithm based on Bacterial
Foraging Optimization. This algorithm aims at minimizing the makespan of a
workflow application. The experiment shows that the approach proposed is effective
to solve task scheduling problem in grid workflow application.
The rest of this paper is organized as follows. Section 2 formalizes the task
scheduling problem in grid workflow application. Section 3 introduces the task
scheduling optimization process based on Bacterial Foraging Optimization. Section 4
uses the experiment to evaluate the approach proposed in this paper with other
algorithms. Section 5 draws a conclusion.
2
Problem Statement
Workflow application is composed by many interrelate tasks. Viewing each task as a
node, communication and precedence constraints between tasks as a directed edge,
the grid application can be expressed as a Directed Acyclic Graph (DAG).
Definition 1.
(Workflow Application) workflow application can be represented as a
quad,
WF
=
(
T
,
E
,
D
,
C
)
,
T
is set of tasks,
E
is the set of edges between tasks,
i
E
T
.
means the edges from task
T
to task
D
=
{
d
,
d
,
d
,...,
d
}
is the workload of
1
2
3
n
each task.
C
is the communication data between tasks.
ij
C
means the
communication data from task
T
to task
T
.
Without loss of generality, we assume one entry and exit task. The set of parent
tasks is denoted as
pred
(
T
)
, the set of children tasks is denoted as
succ
(
T
)
. A task
T
is called entry task if
|
pred
(
T
)
|
=
0
, and an exit task if
|
succ
(
T
)
|
=
0
.
