Hardware Reference
In-Depth Information
Therefore, the release time
r
b
of
J
b
can be replaced by the maximum between
r
b
and
(
r
a
+
C
a
) without changing the problem. Let
r
b
be the new release time of
J
b
. Then,
r
b
=max(
r
b
,r
a
+
C
a
)
.
The algorithm that modifies the release times can be implemented in
O
(
n
2
) and can
be described as follows:
1. For any initial node of the precedence graph, set
r
i
=
r
i
.
2. Select a task
J
i
such that its release time has not been modified but the release
times of all immediate predecessors
J
h
have been modified. If no such task exists,
exit.
3. Set
r
i
=max[
r
i
,
max(
r
h
+
C
h
:
J
h
→
J
i
)].
4. Return to step 2.
MODIFICATION OF THE DEADLINES
The rule for modifying tasks' deadlines is based on the following observation. Given
two tasks
J
a
J
b
(that is,
J
a
is an immediate predecessor of
J
b
), then in any feasible schedule that meets the precedence constraints the following
conditions must be satisfied (see Figure 3.15):
and
J
b
, such that
J
a
→
f
a
≤
d
a
(that is,
J
a
must finish the execution within its deadline);
f
a
≤
d
b
−
C
b
(that is,
J
a
must finish the execution not later than the maximum
start time of
J
b
).
C
a
J
a
<
f
d
a
a
C
b
J
b
f
<
d
b
-
C
a
b
r
r
f
d
a
d
b
a
b
a
Figure 3.15
If
J
a
→ J
b
, then the deadline of
J
a
can be replaced by
min(
d
a
,d
b
− C
b
)
.
Search WWH ::
Custom Search