Real Time Scheduling Problems with Applications to Communication Networks

Abstract

Queuing systems with time-critical customers can be encountered in packetized voice-communication systems, automated command and control systems and manufacturing systems with time-critical jobs among others. We consider the following model for these systems. Customers arriving at the system have individual deadlines and they must reach their destination by their extinction time or due time (arrival time plus deadline). A penalty is incurred otherwise and this implies either the complete loss of customer or another form of tardiness cost. We are interested in characterizing the strategy (of scheduling the customers bearing the label of their deadlines) which minimizes a cost function that reflects the nature of the penalty incurred. We first consider single queues. Under fairly general statistical assumptions on the arrivals, services and deadlines, we show, via simple probabilisitc arguments, that the policy of serving the customer with closest deadline minimizes either the number of lost customers or a generalized tardiness cost in a strong pathwise sense. The optimality results extend to the more general tree network of nodes under some additional assumptions. We then consdier the problem of priority assignment between two queues of heterogeneous time-critical customers. The customers of the two classes have different service requirements and incur tardiness penalty at different rates. A single server has to be allocated to a customer within a class so as to minimize the average tardiness per customer. We formulate the problem in the framework of Markovian Decision Theory and drive certain structural properties of the optimal policy through a novel use of the value iteration technique. These properties readily lead to some implementable (but possible sub-optimal) policies. The presence of time-constraints makes the analysis of these systems intractable in most cases and this motivates the search for qualitative properties which can provide useful design guidelines. Towards this end, we consider multi-server queues with lost customers which are being operated under the optimal scheduling policies and show that the lost and successful customer processes are stochastically monotone in the system parameters: arrivals, services, deadlines and the number of servers.