Optimal scheduling of progressive processing tasks

Progressive processing is an approximate reasoning model that allows a syst em to satisfy a set of requests under time pressure by limiting the amount of processing allocated to each task based on a predefined hierarchical tas k 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 tra de-off computational resources for quality of results, This paper addresses progressive processing of information retrieval requests that are characte rized by high duration uncertainty associated with each computational unit and dynamic operation allowing new requests to be added at run-time. We int roduce a new approach to scheduling the processing units by constructing an d 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 heur istic scheduling techniques. Moreover, the framework presented in this pape r can be applied to real-time scheduling of a wide variety of task structur es other than progressive processing. (C) 2000 Elsevier Science Inc. All ri ghts reserved.