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

Stephen Smith and Dhiraj K. Pathak
tech. report CMU-RI-TR-91-05, Robotics Institute, Carnegie Mellon University, March, 1991


Download
  • Adobe portable document format (pdf) (624KB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

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.

Notes
Sponsor: NASA
Grant ID: NCC 2-531
Number of pages: 11

Text Reference
Stephen Smith and Dhiraj K. Pathak, "Balancing Antagonistic Time and Resource Utilization Constraints in Over-Subscribed Scheduling Problems," tech. report CMU-RI-TR-91-05, Robotics Institute, Carnegie Mellon University, March, 1991

BibTeX Reference
@techreport{Smith_1991_250,
   author = "Stephen Smith and Dhiraj K. Pathak",
   title = "Balancing Antagonistic Time and Resource Utilization Constraints in Over-Subscribed Scheduling Problems",
   booktitle = "",
   institution = "Robotics Institute",
   month = "March",
   year = "1991",
   number= "CMU-RI-TR-91-05",
   address= "Pittsburgh, PA",
}