Citation
Single server scheduling problem: Optimal policy for convex costs depends on arrival rates. In proceedings of the 5th Multidisciplinary International Conference on Scheduling : Theory and Applications (MISTA 2011), 9-11 August 2011, Phoenix, Arizona, USA, pages 275-296, 2011.
Paper
Abstract
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 di erent 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 traffic 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 dfferences 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.
You can download the pdf of this publication from here
doi
This publication does not have a doi, so we cannot provide a link to the original source
What is a doi?: A doi (Document Object Identifier) is a unique identifier for sicientific papers (and occasionally other material). This provides direct access to the location where the original article is published using the URL http://dx.doi/org/xxxx (replacing xxx with the doi). See http://dx.doi.org/ for more information
URL
This pubication does not have a URL associated with it.
The URL is only provided if there is additional information that might be useful. For example, where the entry is a book chapter, the URL might link to the book itself.
Bibtex
@INPROCEEDINGS{2011-275-296-P, author = {C. F. Bispo},
title = {Single server scheduling problem: Optimal policy for convex costs depends on arrival rates},
booktitle = {In proceedings of the 5th Multidisciplinary International Conference on Scheduling : Theory and Applications (MISTA 2011), 9-11 August 2011, Phoenix, Arizona, USA},
year = {2011},
editor = {J. Fowler and G. Kendall and B. McCollum},
pages = {275--296},
note = {Paper},
abstract = {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 di erent 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 traffic 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 dfferences 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.},
owner = {gxk},
timestamp = {2011.08.15},
webpdf = {2011-275-296-P.pdf} }