Information Technology Reference

In-Depth Information

Suppose tasks

T
=

{

T

,

T

,...,

T

}

, resources

M
=

{

M

,

M

,...,

M

}

, the allocation

1

2

1

2

m

matrix can expressed as follows.

am

am

am

1

1

2

1

m

am

am

am

2

,

2

,

2

2

,

m

AM

=

(6)

am

am

am

n

,

n

,

2

n

,

m

am
,
denotes the possibility that task
T
will be executed on resource
M
.

The allocation matrix's value is initially picked up from a uniformed distributed value

in the interval [0, 1]. The value of allocation matrix has to satisfy the following

conditions:

Here

i

j

am
j

∈

[

i

∈

{

2

,...,

n

},

j

∈

{

2

,...,

m

}

(7)

i

,

m

∑
1

am

=

1

i

∈

{

2

,...,

n

},

j

∈

2

,...,

m

}

(8)

i

,

j

j

=

Formula (7) means that the value of allocation matrix is between 0 and 1. So when

the value of allocation matrix exceeds the value boundary, we set the value to the

nearest boundary value. Formula (8) represents that the sum of all possibility value of

allocates
T
to resources is 1. When updating the allocation matrix value, formula (8)

could be violated, so we normalize the allocation matrix to satisfy the condition. The

normalize process is showed in formula (9).

am

i

,

j

am

=

i

,

j

(9)

m

∑
1

am

i

,

k

k

=

When deciding which resource the task

T
will be scheduled on, we choose the

resources with the maximum possibility.

m

=

max(

am

)

j

∈

2

,...,

m

}

(10)

j

i

,

j

3.2.2 Objective Function

In BFO algorithm, all bacterial at each iteration step are evaluated according to a

measure of solution quality. Here we use makespan as the objective function. Given a

bacteria's scheduling vector and allocation matrix, the bacteria can be evaluated

according to formula (1) and (2), while the best bacterial position is saved.

3.2.3 Update Bacteria

The position of a bacterium consists of two parts, namely scheduling vector and

allocation matrix. Allocation matrix can use formula (3) to updates itself during the

chemotaxis step. Scheduling vector can't use formula (3) to updates itself during the

chemotaxis step because the updated scheduling vector may not be a feasible