The single-server scheduling problem with convex costs

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 nonpreemptive problems, it results in a priority ordering of the different 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μ-rule. 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μ-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.