Algorithms that have shown to be feasible, even efficient, in practice are based on the so-called zone graph abstraction30: a zone is a set of clock valuations defined by a clock constraint and can hence be represented by such; the zone graph has as vertices pairs of locations and zones that satisfy the location’s invariant, and its edges are derived from the transitions of the given timed automaton. The number of zones is unbounded, so unlike the region graph, the zone graph is infinite. Finiteness can be enforced using a technique known as normaliza-tion12; however, the number of zones is still much larger than the number of regions, and moreover the same zone can be represented using many different clock constraints.

The reason for zone-based algo-
rithms to be efficient in practice is
twofold: First, the algorithms used
have no need to explore all of the
zone graph (they work on-the-fly),
and zones are commonly bigger
than regions, hence the part of the
zone graph to be explored is smaller.
Second, operations on zones can
be implemented very efficiently (in
time cubic in the number of clocks):
zones are usually represented using
difference-bound matrices, or DBMs.
The DBM representation of a zone
on a set of k clocks has (k + 1) × (k +
1) entries, where an entry ci,j repre-
sents a clock constraint xi − xj ≤ ci,j
and an extra clock x0 is added to rep-
resent absolute clock constraints
xi ≤ ci0. DBMs in turn can be repre-
sented as directed weighted graphs;
see below for an example of a zone
and its DBM (graph) representation.
Canonical representations of zones
can be obtained using shortest-path
closure or shortest-path reduction
of their DBM graphs, and delay and
reset operations on zones can be
efficiently implemented on the DBM
representations.

− 4

1≤ 3 1− 2≤ 10 1− 2≥ 4 1− 3≤ 2 3− 2≤ 2

3≥− 5

1

2

=

3

2

10

2

0

3

5

task graph scheduling: time optimality. A task graph problem involves a number of tasks T1, …, Tm, a number of machines or processors P1, …, Pn, and a (partial) mapping d giving, for each task Ti and processor Pj, the time d(i,j) for computing Ti on Pj. In addition there is a partial order on the tasks used for describing dependencies. Figure 3 is an example of a task graph problem.

We want to determine a schedule of when to start the execution of tasks, and on which processors, that minimizes the total execution time while being feasible in respecting the following conditions: (a) a task can be executed only if all its predecessors have completed; (b) each machine can process at most one task at a time; (c) tasks cannot be preempted.

Task graph scheduling problems may be easily modeled as networks of timed automata so that every run corresponds to a feasible schedule and the fastest run gives the time-optimal schedule: for each processor we construct a small timed automaton able—when idle—to handle within the appropriate amount of time the

figure 3. Task graph problem with six tasks, where each task corresponds to the computation of a given sub-expression of the term (D × (C × (A + B) ) + ( (A + B) + (C × D) ). Given the execution platform with two processors, P1 and P2, and corresponding computation times for addition and multiplication, as well as their energy consumption, sch1–sch3 provide three feasible schedules, where sch2 is in fact time-optimal, and sch3 is energy-optimal.