Information Technology Reference
In-Depth Information
When scheduling a workflow to grid resources, it has to satisfy following
conditions:
1.
Every task can be scheduled to any grid resource. The execution time of a
task is determined by workload of the task and calculating speed of grid
resource.
2.
Every task is processed on one resource at a time.
3.
Every resource processes only one task at a time.
4.
Grid resource is connected in a strongly connected topology in which all
communication between resources are assumed to perform without contention
5.
Grid resource can do computation and communication simultaneously.
6.
When two tasks are scheduled to the same resources and they have
communications data between them, we neglect the communication time.
7.
A task can't be started until the communication data of all parent tasks have
been transferred to the scheduled resources and the resources must be in the
idle state.
We use
ST
(
T
)
and
FT
(
T
)
to denote the start time of task
T
and end time of
task
T
respectively. For the entry task
,
. Given a scheduling
T
ST
(
T
)
=
0
entry
entry
scheme,
ST
(
T
)
is calculated by formula (1)
ST
(
T
)
=
max{
avail
(
M
),
max
(
FT
(
T
)
+
C
/
s
)}
(1)
i
k
j
i
,
j
T
∈
pred
(
T
)
j
i
avail
(
M
)
denotes the available time of resource
M
,
pred
(
T
)
is the set of
k
immediate predecessor of task
C
,
is communication data size,
s
is bandwidth
between resources. The equation means the start time of task
T
is the maximum of
resource available time and the time when all precede data have been transferred to
the resource.
T
,
j
FT
(
T
)
is calculated by formula (2).
FT
(
T
)
=
d
/
r
+
ST
(
T
)
(2)
i
i
i
d
is the workload of task
T
,
r
is the calculating speed of grid resource. After
all tasks have been scheduled, the finish time of exit task
exi
T
is recorded as the
makespan of workflow application. This paper aims at minimizing the makespan.
3
Bacterial Foraging Optimization Based Algorithm
3.1
Bacterial Foraging Optimization
Bacterial Foraging Optimization algorithm is a population-based numerical
optimization algorithm proposed by Passino [12]. It simulated the foraging behavior
of Escherichia coli bacteria. Foraging is a process in which a group of bacteria move
in search of food in a region. Bacteria search for nutrient in a manner to maximize
energy obtained per unit time. There are four basic steps of bacteria foraging
