Tail Optimality of the Nudge-M Scheduling Algorithm

Recently it was shown that the response time of First-Come- First-Served (FCFS) scheduling can be stochastically and asymptotically improved upon by the Nudge scheduling algorithm in case of light-tailed job size distributions. Such improvements are feasible even when the jobs are partitioned into two types and the scheduler only has information about the type of incoming jobs (but not their size). In this paper we introduce Nudge-M scheduling, where basically any incoming type-1 job is allowed to pass any type-2 job that is still waiting in the queue given that it arrived as one of the last M jobs. We prove that Nudge- M has an asymptotically optimal response time within a large family of Nudge scheduling algorithms when job sizes are light-tailed. Simple explicit results for the the prefactor of Nudge-M are derived as well as explicit results for the optimal parameter M. An expression for the prefactor that only depends on the type-1 and type-2 mean job sizes and the fraction of type-1 jobs is presented in the heavy traffic setting.