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