Accession Number:

ADA210668

Title:

Preference Propagation in Temporal/Capacity Constraint Graphs

Descriptive Note:

Technical rept.

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA ROBOTICS INST

Personal Author(s):

• Sadeh, Norman
• Fox, Mark S.

Report Date:

1989-01-01

Pagination or Media Count:

59.0

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 temporalcapacity constraint graph TCCG. 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 TCCGs in order to focus attention in an incremental scheduler.

Descriptors:

• *GRAPHS
• CAPACITY(QUANTITY)
• UTILIZATION
• TIME
• MACHINES
• RESOURCES
• PROPAGATION
• ACCURACY

Subject Categories:

• Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE