Date: Wednesday, 15-Jan-97 02:08:39 GMT Server: NCSA/1.3 MIME-version: 1.0 Content-type: text/html Last-modified: Wednesday, 22-Mar-95 16:48:03 GMT Content-length: 4784 Design-to-time Real-time Scheduling

Design-to-time Real-time Scheduling

Design-to-time is an approach to real-time problem solving in situations where multiple methods exist for many tasks that a system needs to solve. Design-to-time involves designing a solution to a problem that uses all available resources to maximize the solution quality within the available time. One important area of research has focused on interdependencies that may exist between methods, such as the execution of one method enabling the execution of another, or the use of a rough approximation by one method negatively affecting the performance of a method that uses its result.

The methodology is known as design-to-time because it advocates the use of all available time to generate the best solutions possible. It is a problem-solving method of the type described by D'Ambrosio as those which "given a time bound, dynamically construct and execute a problem solving procedure which will (probably) produce a reasonable answer within (approximately) the time available."

If design-to-time is to be generally useful, it must be possible to embed design-to-time schedulers in larger application systems. There are many reasons why a distinct separation should exist between a design-to-time scheduler and its invoker, including at least modularity and efficiency. Modularity suggests that separate functionality should be kept in separate modules with clearly defined interfaces. In general it is difficult for all current problem solving criteria to be encapsulated into an evaluation function and transmitted to the scheduler, because deciding what to do is a evolving computational process. Another reason why a separation might exist between a decision maker and a design-to-time scheduler is that they work at different levels of abstraction. One of the roles of the decision maker is to constrain the search done by the design-to-time scheduler, for example, by using commitments to tell the scheduler what parts of the task structure to focus on. While it is possible for the scheduler to use all available information to make such decisions itself, for efficiency reasons it is useful to have the decision maker constrain the search space for the scheduler. More details on this aspect of design-to-time scheduling can be found in our page on integrating scheduling and decision-making.

To date we have examined design-to-time scheduling in the Distributed Vehicle Monitoring Testbed (DVMT), looked at simplified DVMT-like tasks with limited subtask interactions, explored the interaction between a design-to-time scheduler and a decision-maker, briefly described extensions to design-to-time for uncertainty, and experimented with an optimal design-to-time scheduling algorithm.


Back to the DIS Lab Home Page

If you have questions, problems or suggestions send mail to www@dis.cs.umass.edu
Last Update: 3/22/95