Single Server Scheduling Problem. Optimal policy for convex costs depends on arrival rates

August 2011

Being probably one of the oldest decision problems in queuing theory, the single server scheduling problem continues to be a challenging one. The original formulations considered linear costs and the resulting policy is puzzling in many ways. The main one is that, either for preemptive or non preemptive problems, it results in a priority ordering of the dierent classes of customers being served that is insensitive to the individual load each class imposes on the server and insensitive to the overall load the server experiences. This policy is known as the c$mu$-rule. Recently and to address the fairness issue, some authors proposed that convex costs are a better way to model the problem. Customers in the non priority queues have a highly variable cycle time as well as they may have a long average waiting time, under linear costs. This may result in customer dissatisfaction and/or high abandonment rates. The policy derived for convex costs is shown to be asymptotically optimal for heavy trac and consists on a generalization of the optimal policy for linear costs, taking the derivative of the single stage cost function. One of the characteristics preserved in the generalization is the insensitivity to the individual loads of the classes being served. We claim and show that for convex costs the optimal policy depends on the individual loads. Therefore, there is a need for an alternative generalization of the c$mu$-rule. The main feature of our generalization consists on first order differences of the single stage cost function, rather than on its derivatives. The resulting policy is able to reach near optimal performances and is a function of the individual loads.

Authors in the community:

• 

  C

  Carlos Filipe Gomes Bispo

  ist12409

  Affiliations and sources

  IST > LARSYS

  Laboratório de Robótica e Sistemas em Engenharia e Ciência

  IST > LARSYS > ISR

  Instituto de Sistemas e Robótica

  IST > DEEC

  Departamento de Engenharia Electrotécnica e de Computadores

This information is not available. Please contact the author for more information.

Phoenix, AZ, USA

electrical-engineering-electronic-engineering-information-engineering - Electrical engineering, electronic engineering, information engineering

eng - English