Hardware Reference
In-Depth Information
that is,
d
1
1
k−
2
2
√
k
2
−
4
k
=
2
+
1
k−
2
d
2
=
2
−
2
√
k
2
−
4
k
.
Since (
x
1
>x
2
), (
x
1
>
2), and (
d
1
>
0),
C
i
will diverge, and hence, also for
k>
4,
Equation (9.5) cannot be satisfied.
In this case, since (
k
2
Case (
k<
4
)
.
4
k<
0), both the roots
x
1
,
x
2
and the
coefficients
d
1
,
d
2
are complex conjugates, so they can be represented as follows:
d
1
−
x
1
se
jθ
re
jω
=
=
re
−jω
,
d
2
se
−jθ
x
2
=
=
where
s
and
r
are real numbers,
j
=
√
−
1, and
θ
and
ω
are angles such that,
−
π/
2
<
θ<
0, 0
<ω<π/
2. Equation (9.8) may therefore be rewritten as
C
i
se
jθ
r
i
e
jiω
+
se
−jθ
r
i
e
−jiω
=
=
sr
i
[
e
j
(
θ
+
iω
)
+
e
−j
(
θ
+
iω
)
]=
=
sr
i
[cos(
θ
+
iω
)+
j
sin(
θ
+
iω
)+cos(
θ
+
iω
)
=
−
j
sin(
θ
+
iω
)] =
=2
sr
i
cos(
θ
+
iω
)
.
Being
ω
=0, cos(
θ
+
iω
) is negative for some
i
∈
N
, which implies that there exists
a finite
m
that satisfies (9.5).
Since (9.5) is satisfied for
k<
4, the largest
k
that determines the competitive factor of
an online algorithm is certainly less than 4. Therefore, we can conclude that 1
/
4 is an
upper bound on the competitive factor that can be achieved by any online scheduling
algorithm in an overloaded environment. Hence, Theorem 9.1 follows.
EXTENSIONS
Theorem 9.1 establishes an upper bound on the competitive factor of online scheduling
algorithms operating in heavy load conditions (
ρ>
2). In lighter overload conditions
(1
<ρ
≤
2), the bound is a little higher, and it is given by the following theorem
[BR91].
Theorem 9.2 (Baruah et al.)
In systems with a loading factor
ρ
,
1
<ρ
2
, and task
values equal to computation times, no online algorithm can guarantee a competitive
factor greater than
p
, where
p
satisfies
≤
1)
p
]
3
=27
p
2
.
4[1
−
(
ρ
−
(9.9)
Search WWH ::
Custom Search