A Scheduling Tool for Conditionally Independent Temporal Preferences

It is well known that the problem of finding a feasible schedule for a partially ordered set of tasks can be formulated as a Disjunctive Temporal Problem (DTP). In case we want to find a schedule by taking preferences into account, there exist extensions to DTPs that augment them by associating numeric costs to the violation of individual temporal constraints, however, such extensions make the restrictive assumption that the costs associated with constraints are independent of one another. In this paper we propose a further extension, which enables the designer to specify (directional) dependencies between the preferences associated with the constraints. Such preferences are represented by exploiting Utility Difference Networks (UDNs), that define objective functions whose structure reflects conditional independencies among the nodes of the network. The paper describes the branch-and-bound algorithm at the core of the scheduling tool we have implemented for solving this new class of problems. We also present and discuss encouraging experimental results collected in two different test domains.