Java Reference
In-Depth Information
individually. For example, scheduling the time plan for a single mail carrier
represents a sub-problem of the scheduling problem for the entire post
office. The decentralized approach prevents the algorithm from finding the
optimal solution of a given scheduling problem (the algorithm does not have
global visibility of the state variables) but simplifies the system model
identification and solution evaluation. The solution emerges as the result of
the interactions between the subsystems: each subsystem optimizes its own
objective but coordinates with the other subsystems when conflicts arise.
For a wide class of problem, scheduling algorithms try to minimize earli-
ness and tardiness. This means that an activity should not start before its
release time and should not complete after its due time. The earliness and
tardiness constraints might be strong or weak. In the former case the con-
straints cannot be violated, while in the latter case they can be violated to
the prejudice of the scheduling performance. For the sake of simplicity, we
consider only weak constraints. This guarantees that the scheduling
problem always has a solution, no matter how bad. The performance of the
scheduling algorithm measures the quality of the solution, i.e. how much the
solution enforces the temporal constraints.
The performance of an activity is computed as illustrated in Equation 3.1
as a function the parameters
r
,
a
,
t
and
d
, which have the meaning defined
in Figure 3.2. The lower is the value of performance the better is the solu-
tion. The
pe
is the earliness performance, the
pt
is the tardiness perfor-
mance,
we
and
wt
are the weights on
pe
and
pt
, and
P
is the activity
performance. We define the performance of the entire system as the sum of
the performances of all the activities.
we
*
(
r
−
a
)
r
p
a
wt
*
(
t
−
d
)
t
p
d
pe
=
pt
=
0
r
≤
a
0
t
≤
d
P
=
pe
+
pt
Equation 3.1
Earliness, tardiness and task overall performance
The values of
we
and
wt
depend on the problem at hand. For example, we
can give more importance to the tardiness constraint if we want the activities
to complete as soon as possible.
The scheduling algorithm has the goal of minimizing the value of
P
while
looking for a solution to the scheduling problem (assignment of new values
to the activity parameters) that satisfies the temporal and resource con-
straints. The algorithm enforces these constraints by sequencing the
activities executed by a resource. This implies shifting values of the tem-
poral parameters of each activity forwards or backwards. It is clear that the
performance of the result depends on the specific order imposed on the
activities processed by all the resources.
In order to find the optimal solution (the one that corresponds to the
minimum value of
P
), the algorithm would have to permute all the possible
sequences of activities for each resource. This is the typical centralized
