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