Optimal Scheduling of Progressive Processing Tasks

Shlomo Zilberstein and Abdel-Illah Mouaddib. Optimal Scheduling of Progressive Processing Tasks. International Journal of Approximate Reasoning, 25(3):169-186, 2000.

Abstract

Progressive processing is an approximate reasoning model that allows a system to satisfy a set of requests under time pressure by limiting the amount of processing allocated to each task based on a predefined hierarchical task structure. It is a useful model for a variety of real-time tasks such as information retrieval, automated diagnosis, or real-time image tracking and speech recognition. In performing these tasks it is often necessary to trade-off computational resources for quality of results. This paper addresses progressive processing of information retrieval requests that are characterized by high duration uncertainty associated with each computational unit and dynamic operation allowing new requests to be added at run-time. We introduce a new approach to scheduling the processing units by constructing and solving a particular Markov decision problem. The resulting policy is an optimal schedule for the progressive processing problem. Evaluation of the technique shows that it offers a significant improvement over existing heuristic scheduling techniques. Moreover, the framework presented in this paper can be applied to real-time scheduling of a wide variety of task structures other than progressive processing.

Bibtex entry:

@article{ZMijar00,
  author	= {Shlomo Zilberstein and Abdel-Illah Mouaddib},
  title		= {Optimal Scheduling of Progressive Processing Tasks},
  journal	= {International Journal of Approximate Reasoning},
  volume	= {25},
  number	= {3},
  year		= {2000},
  pages		= {169-186},
  url		= {http://rbr.cs.umass.edu/shlomo/papers/ZMijar00.html}
}

shlomo@cs.umass.edu