Java Reference
In-Depth Information
approach, where the algorithm has visibility of the entire model of the
scheduling problem.
On the other hand, the decentralized approach assigns to each resource
the responsibility to schedule its activities. The resource applies a three-step
procedure that does not require evaluating all the possible permutations of
activities.
First, the resource orders the activities by their activation time.
■
Second, the resource enforces resource and temporal constraints. This
requires shifting the activities' activation time and termination time
forward in order to avoid temporal overlapping between consecutive
activities.
■
Third, each activity evaluates its performance and proposes a new acti-
vation time that tries to minimize earliness and tardiness. The new
activation time is evaluated according to Equation 3.2. Parameter
g
(gain)
represents the strength of the activity's preferences. The greater this
value, the stronger is the ability of the activity to enforce its preferences.
The resource repeats the above procedure for all the tasks until the global
performance or the number of iterations (indicated by
k
) reaches a
desired threshold.
■
a
[
k
+
1]
=
a
[
k
]
+
g
*
(
d
−
t
)
Equation 3.2
Earliness, tardiness and task overall performance
This approach is actually one of dynamic scheduling and implements a
strict separation of concerns between resource and activity. The former
knows its availability and is simply the bookkeeper that orders the list of
activities temporally in order to avoid overlapping; the latter takes the
initiative proposing its preferred activation time based on its constraints
(release time and due date) and the estimated termination time received as
a response from the resource.
This algorithm resembles a discrete time control feedback loop that
minimizes earliness and tardiness (see Figure 3.3). It has been shown that
the emerging behaviour, which results from the unconscious interaction
between activities on a resource, as previously described, has good stability
and performance properties (Prabhu and Duffie 1999).
3.2.2
Main features
We are now able to summarize all the main features emerging from the
problem analysis.
d
a
[
k
!
1]
t
Activity
a
[
k
!
1]
#
a
[
k
]
!
g
'
(
d
0
t
)
0
Resources
t
Figure 3.3
Discrete time control feedback loop
