We study an expressive quantitative temporal model: Disjunctive Temporal Problem (DTP), which was first proposed only in 1998 [5]. As extension of Temporal Constraint Satisfaction Problem (TCSP) [1], DTP differs from TCSP in that two disjuncts in a same disjunctive constraint do not necessarily refer to same temporal variables. Traditionally, most of the DTP algorithms in the literature solve DTPs by treating them as Constraint Satisfaction Problems (CSPs), and searching for solutions using standard CSP techniques, e.g. backtracking, back-jumping, forward checking, semantic branching, removal of subsumed variables, nogood recording [3, 5, 6], etc.