About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
IEEE TACON
Paper
Optimal Allocation of a Server Between two Queues with Due Times
Abstract
Two queues share a single server. Arrivals to each queue have individual target due times for service completion (their due times are known to the controller) and a penalty is incurred when they stay in the system after the expiration of these due times. The two classes have different service requirements and incur penalty at different rates. We consider the problem of dynamic priority assignment so as to minimize the discounted and average tardiness per customer. The problem is formulated in discrete-time where we show that, under the assumptions of geometric arrivals and geometric services, there is a nonidling stationary optimal preemptive policy. Within each class, the policy chooses, if at all, the customer with the smallest due time. We introduce a partial order on the space of the set of residual times and show that the optimal choice of the customer class is monotonic with respect to this partial order; this implies a switchover-type property in the appropriate space. A combination of stochastic dominance and dynamic programming ideas is used to establish the results. © 1991 IEEE