Real-Time Stochastic Processing Networks with Concurrent Resource Requirements

I Hou, R Singh - arXiv preprint arXiv:1204.4467, 2012 - arxiv.org
arXiv preprint arXiv:1204.4467, 2012arxiv.org
Stochastic Processing Networks (SPNs) can be used to model communication networks,
manufacturing systems, service systems, etc. We consider a real-time SPN where tasks
generate jobs with strict deadlines according to their traffic patterns. Each job requires the
concurrent usage of some resources to be processed. The processing time of a job may be
stochastic, and may not be known until the job completes. Finally, each task may require that
some portion of its tasks to be completed on time. In this paper, we study the problem of …
Stochastic Processing Networks (SPNs) can be used to model communication networks, manufacturing systems, service systems, etc. We consider a real-time SPN where tasks generate jobs with strict deadlines according to their traffic patterns. Each job requires the concurrent usage of some resources to be processed. The processing time of a job may be stochastic, and may not be known until the job completes. Finally, each task may require that some portion of its tasks to be completed on time. In this paper, we study the problem of verifying whether it is feasible to fulfill the requirements of tasks, and of designing scheduling policies that actually fulfill the requirements. We first address these problems for systems where there is only one resource. Such systems are analog to ones studied in a previous work, and, similar to the previous work, we can develop sharp conditions for feasibility and scheduling policy that is feasibility-optimal. We then study systems with two resources where there are jobs that require both resources to be processed. We show that there is a reduction method that turns systems with two resources into equivalent single-resource systems. Based on this method, we can also derive sharp feasibility conditions and feasibility-optimal scheduling policies for systems with two resources.
arxiv.org