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