Benny Van Houdt

Nils Charlet, Benny Van Houdt

Recently it was shown that the response time of First-Come-First-Served (FCFS) scheduling can be stochastically and asymptotically improved upon by the {\it 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 asymptotic tail improvement ratio (ATIR) of Nudge*$(M)$ over FCFS are derived as well as explicit results for the optimal parameter $M$. An expression for the ATIR 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. The paper further presents a numerical method to compute the response time distribution and mean response time of Nudge*$(M)$ scheduling provided that the job size distribution of both job types follows a phase-type distribution (by making use of the framework of Markov modulated fluid queues with jumps).

Nils Charlet, Benny Van Houdt

In a recent paper the $γ$-Boost scheduling policy was shown to minimize the tail of the response time distribution in a light-tailed M/G/1-queue. This policy schedules jobs using a boosted arrival time, defined as the arrival time of a job minus its boost, where the boost of a job depends on its exact job size. The $γ$-Boost policy can also be used when only partial job size information is available, such as the type of an incoming job. In such case the boost $b_i$ of a job depends solely on its type $i$ and $γ$-Boost was shown to optimize the tail among all boost policies, where a boost policy is fully determined by the $b_i$ values. In the partial information setting $γ$-Boost relies on two types of information: job types and arrival times. 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 {\it 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 \geq 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.