Optimality of the Stochastic Earliest Deadline Policy for the G/M/c Queue Serving Customers with Deadlines

Abstract

We consider the problem of scheduling customers with deadlines in the G/M/c queue. We assume that customer deadlines are not known but that the scheduling policy has available to it partial information regarding stochastic relationships between the deadlines of eligible customers. We prove three main results, 1) in the case that deadlines are until the beginning of service, the nonpreemptive, non-idling policy that stochastically minimizes the number of customers lost during an interval of time belongs to the class of non-idling stochastic earliest deadline (SED) policies, 2) in the case that deadlines are until the end of service, the optimum policy belongs to the class of SED policies, and 3) in the case of deadlines until the end of service, the optimum non-preemptive policy belongs to the class of non-preemptive, non-idling SED policies. The last result assumes that a customer in service that misses its deadline is always removed and thrown away. Here a policy belongs to ...

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 41 citations exist upstream.