On 2-moment completeness of non pre-emptive, non anticipative work conserving scheduling policies in some single class queues

Completeness of some scheduling policies with mean waiting time performance measure is used quiet extensively in literature for dynamic control of multi-class queues due to its wide range of applications in computers, communication networks and manufacturing systems. For a single class queue, we introduce the idea of 2-moment completeness of a parametrized class of policies that also have to be non pre-emptive, non anticipative and work conserving. Significance of this idea lies in the importance of variance (or second moment) of waiting time in any queuing system. Some parametrized classes of policies are identified and shown to be 2-moment complete for M/M/1 queues. Some well known queue disciplines viz random order of service (ROS), Random Assigned Priority (RAP), etc., turn out to be 2-moment incomplete. We introduce a parametrized priority scheme that also turns out to be 2-moment incomplete. Further, few preemptive and anticipative scheduling disciplines are shown to have second moment beyond the achievable region of non pre-emptive, non anticipative and work conserving scheduling policies. Some optimal control problems are discussed to illustrate the possible applications of 2-moment complete parametrized set of policies.