Optimal Allocation of a Server Between two Queues with Due Times

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