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