Title: Some parametrized dynamic priority policies for 2-class M/G/1 queues: completeness and applications,
Abstract: Completeness of a dynamic priority scheduling scheme is of fundamental
importance for the optimal control of queues in areas as diverse as computer
communications, communication networks, supply chains and manufacturing
systems. Our first main contribution is to identify the mean waiting time
completeness as a unifying aspect for four different dynamic priority
scheduling schemes by proving their completeness and equivalence in 2-class
M/G/1 queue. These dynamic priority schemes are earliest due date based, head
of line priority jump, relative priority, and probabilistic priority.
In our second main contribution, we characterize the optimal scheduling
policies for the case studies in different domains by exploiting the
completeness of above dynamic priority schemes. The major theme of second main
contribution is resource allocation/optimal control in revenue management
problems for contemporary systems such as cloud computing, high-performance
computing, etc., where congestion is inherent. Using completeness and
theoretically tractable nature of relative priority policy, we study the impact
of approximation in a fairly generic data network utility framework. We
introduce the notion of min-max fairness in multi-class queues and show that a
simple global FCFS policy is min-max fair. Next, we re-derive the celebrated
$c/\rho$ rule for 2-class M/G/1 queues by an elegant argument and also simplify
a complex joint pricing and scheduling problem for a wider class of scheduling
policies.