Java Reference
In-Depth Information
Activity
i
00
1
Activity
i
Activity
i
!!
1
r
a
t
d
ra
td
ra
td
r
#
Release time
a
#
Start time
t
#
Completion time
d
#
Due time
r
i
≤
a
i
d
i
≥
t
i
r
i
#
t
i
00
1
a
i
#
d
i
00
1
Figure 3.2
The relationship between task and activity
A resource represents a physical entity (e.g. a piece of manufacturing
equipment) that receives requests for an activity of proper types to be
delivered over a certain time interval.
Two types of constraint characterize a job-shop scheduling problem:
temporal consistency constraints and resource consistency constraints.
A temporal consistency constraint states that within a given task each
activity can only start when the previous one is finished.
■
A resource consistency constraint states that a given resource can process
only one activity at a time. In fact, it is assumed that each activity
requires the exclusive use of a resource.
■
The solution of a job-shop problem consists of the set values for the acti-
vation time and termination time variables of each activity. Such values
must respect all the temporal and resource consistency constraints and
guarantee that all the activities are processed after their release time and
within their due times.
A variety of scheduling algorithms are documented in the literature. From
an architectural point of view, they can be divided in two categories:
centralized and decentralized.
Centralized algorithms require the model of the system to be expressed in
terms of global state variables (the temporal parameters of each activity) and
global constraints (the temporal and resource dependencies between
activities). Usually, they are customized for the specific problem at hand in
order to compute the optimal solution that maximizes or minimizes the
target parameters (e.g. the total mail delivery time, or the total delay
between two exercises). These algorithms compute all the possible permu-
tations between activities and evaluate the target parameter for each of
them. The main drawback is that both the system model identification and
the consequent ad hoc algorithm design are complex tasks even for trivial
problems. In addition, centralized algorithms have to be designed with “ad
hoc” techniques. Every new problem must be solved from scratch.
Decentralized algorithms exploit the natural decomposition of the
problem into sub-problems according to the physical system organization in
subsystems and allow the system designer to tackle each sub-problem
