Balancing Antagonistic Time and Resource Utilization Constraints in Oversubscribed Scheduling Problems

Abstract

Previous research has demonstrated the utility of constraint-based problem structuring and multiperspective scheduling for effective balancing conflicting objects in constraint-relaxable scheduling problems. Work aimed at applying these concepts to over-subscribed scheduling problems is discussed. The focus is on the problem of constructing short-term schedules for the Hubble Space Telescope, where complex state-dependent constraints on resource utilization interact antagonistically with the ability to satisfy absolute time constraints on execution of goal activities. Two time-bounded heuristic scheduling strategies were defined. The performance of each in balancing this tradeoff was studied experimentally. On the basis of results indicating the differential superiority of each strategy, a composite multiperspective strategy based on recognition of characteristics of the current problem-solving state is defined. Its experimental performance indicates the benefits of constraint-based problem structuring in over-subscribed domains.