initially known but are successively deduced from an incremental independent process (Garrido et al., 1999).

A prototype of proposed reasoning algorithms has been implemented in Common-Lisp and is available from the author. These reasoning algorithms are being applied to an integrated architecture of planning and scheduling processes (Garrido et al., 1999). Here, the scheduling process should guarantee the consistency of each alternative partial plan (i.e.: temporal constraints and availability of resources for operations) simultaneously as the planner is generating each partial plan (Srivastava
& Kambhampati, 1999). Thus, the following main features are needed:
 Management of disjunctive metric constraints. Particularly, in planning and scheduling problems the number disjuncts in input constraints is generally bounded by l≤2 (i.e.: nonsimultaneous use of resources). However, temporal dependencies between constraints (i.e.:
non-binary constraints) can appear. For instance, operation durations can be dependent on the order in which they are scheduled.

 Incremental reasoning. The process should interactively guarantee the consistency of each new input temporal constraint (about resources, plans, ordering, and objects) as each new step is deduced in a partial plan.

 Management of temporal contexts, where each context is associated to an alternative plan
(action or state). Reasoning algorithms simultaneously work over different and alternative partial plans.
A globally labeled-consistent (and minimal) TCN allows us to determine consistent alternative choices and to obtain optimal solutions in each plan. Additionally, the proposed model can be a useful framework to apply on problems where these features also appear (Dousson et al., 1993; Garcia & Laborie, 1996; Srivastava & Kambhampati, 1999; etc.).

The computational cost of reasoning algorithms is exponential, due to the inherent complexity of the management of disjunctive constraints. However, the management of temporal contexts does not increase the complexity of the reasoning processes on disjunctive constraints.

Some improvements to decrease the empirical cost of reasoning algorithms have been proposed in this paper. The application of algorithms to handle only an explicit TCN (without making the derived constraints explicit) and empirical evaluations on several test cases are under study. Moreover, other reasoning algorithms can be applied to the temporal algebra presented, as proposed in Section 4. On the other hand, it is interesting to identify subclasses of the labeled temporal algebra where the size of label sets can be bounded, and to identify tractable subclasses of IA on the proposed model. It could also be interesting to identify the expressive power of I-L-Sets (and labeled constraints) on the basis of method described by Jeavons, Cohen and Cooper (1999). Here, each I-LSet represents a special *derived constraint*, which expresses the inconsistency of a set of *input* elemental constraints; that is, a special type of disjunctive linear constraint (Jonsson & Bäckström, 1996; Stergiou & Koubarakis, 1996).

The proposed-labeled algebra (labeled constraints and the operations on them) can be applied to other temporal models (i.e.: to other classes of temporal constraints, operations, and reasoning algorithms). To do this, the operations of the labeled algebra (⊕lc, ⊗lc, ∪lc and ⊆lc) should be defined on the basis of the respective operations (⊕, ⊗, ∪Τ and ⊆Τ) of these models, and the reasoning algorithms should use the operations defined on labeled constraints (⊕lc, ⊗lc, ∪lc and ⊆lc). This