Preference Propagation in Temporal/Capacity Constraint Graphs
Abstract
Scheduling can be formalized as a constraint satisfaction problem. Within this framework activities in a plan are interconnected via temporal relation constraints a la Allen, thereby defining a temporal constraint graph (TCG). Additionally there are capacity constraints restricting the use of each resource to only one activity at a time. Together these constraints form a temporal/capacity constraint graph (T/CCG). Preferences such as meeting due dates, reducing order flowtime, or selecting accurate machines are modeled as utility functions over the domain of possible start times and durations of activities and over the sets of possible resources activities can use. These preferences interact via the TCG and via the resource capacity constraints. Hence, in general, they cannot be simultaneously optimized. The objective of preference propagation techniques is to transform such local a priori preferences so as to account for their interactions. This paper describes a probabilistic framework in which start time, duration and resource preferences are propagated across T/CCGs in order to focus attention in an incremental scheduler.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1989
- Accession Number
- ADA210668
Entities
People
- Mark S. Fox
- Norman Sadeh
Organizations
- Carnegie Mellon University