NASA Logo

NTRS

NTRS - NASA Technical Reports Server

Back to Results
producing satisfactory solutions to scheduling problems: an iterative constraint relaxation approachOne drawback to using constraint-propagation in planning and scheduling systems is that when a problem has an unsatisfiable set of constraints such algorithms typically only show that no solution exists. While, technically correct, in practical situations, it is desirable in these cases to produce a satisficing solution that satisfies the most important constraints (typically defined in terms of maximizing a utility function). This paper describes an iterative constraint relaxation approach in which the scheduler uses heuristics to progressively relax problem constraints until the problem becomes satisfiable. We present empirical results of applying these techniques to the problem of scheduling spacecraft communications for JPL/NASA antenna resources.
Document ID
20060038309
Document Type
Preprint (Draft being sent to journal)
External Source(s)
Authors
Chien, S.
Gratch, J.
Date Acquired
August 23, 2013
Publication Date
June 13, 1994
Distribution Limits
Public
Copyright
Other
Keywords
Constraint Satisfaction Problems CSP constraint propagation iterative relaxation