arXiv: arXiv:1303.0038 APPROXIMATELY OPTIMAL SCHEDULING OF AN M/G/1 QUEUE WITH HEAVY TAILS ∗

Distributions with a heavy tail are difficult to estimate. If the design of an optimal scheduling policy is sensitive to the details of heavy tail distributions of the service times, an approximately opti-mal solution is difficult to obtain. This paper shows that the optimal scheduling of an M/G/1 queue with heavy tailed service times does not present this difficulty and that an approximately optimal strategy can be derived by truncating the distributions. 1. Introduction. Th