? -CounterBoost: Optimizing Response Time Tails using Job Type Information Only

This paper focuses on the problem of minimizing the tail in a light-tailed M/G/1-queue in the partial job size information setting when the scheduler only makes use of the job types and does not exploit arrival times. Prior work showed that in case of 2 job types the so-called Nudge-M policy minimizes the tail in a large class of scheduling policies. In this paper we introduce the ?-CounterBoost policy in the partial information setting with d ≥ 2 job types and prove that it minimizes the tail in an even broader class of scheduling policies called Contextual CounterBoost policies. The γ-CounterBoost policy reduces to the Nudge-M policy in case of d = 2 job types.