Optimization in constraint reasoning about repeating events

The effective manipulation of temporal information about periodic events is required for solving complex problems such as long range scheduling or querying temporal information. Furthermore, many problems involving repeating events require the optimization of temporal aspects of these events, e.g., minimizing makespan in job-shop scheduling. This paper contains a framework for representing and solving reasoning problems in which temporal aspects of repeating events are to be optimized. This framework rests upon three foundations: recent work on the characterization of repeating events (Morris et al., 1996), the temporal CSP framework for processing constraints, (Dechter et al., 1991), and the semiring generalization of CSPs (Bistarelli et al., 1995). The semiring allows values to be associated with consistent solutions generated from the specification; the values are computed from functions that provide interpretations of the optimizing constraints