Balancing Antagonistic Time and Resource Utilization Constraints in Over-Subscribed Scheduling Problems

Abstract

In this paper, we report work aimed at applying concepts of constraint-based problem structuring and multi-perspective scheduling to over-subscribed scheduling problems. Previous research has demonstrated the utility of these concepts as a means for effectively balancing conflicting objectives in constraint-relaxable scheduling problems, and our goal here is to provide evidence of their similar potential in the context of HST observation scheduling. To this end, we define and experimentally assess the performance of two time-bounded heuristic scheduling strategies in balancing the tradeoff between resource setup time minimization and satisfaction of absolute time constraints. The first strategy considered is motivated by "dispatch-based" manufacturing scheduling research, and employs a problem decomposition that concentrates local search on minimizing resource idle time due to "setup" activities. The second is motivated by research in opportunistic scheduling and advocates a problem decomposition that focuses attention on the goal activities that have the tightest temporal constraints. Analysis of experimental results gives evidence of differential superiority on the part of each strategy in different problem solving circumstances. A composite strategy based on recognition of characteristics of the current problem solving state is then defined and tested to illustrate the potential benefits of constraint-based problem structuring and multi-perspective scheduling in over-subscribe scheduling problems.