论文标题
在首次进行的首次安排和轻推调程的随机和渐近改进方面
On the stochastic and asymptotic improvement of First-Come First-Served and Nudge scheduling
论文作者
论文摘要
最近表明，与期望相反，可以通过调度算法（称为{\ it nudge}用于轻尾的作业大小分布）来随机改进。根据它们的大小，将作业分为4种类型，例如中小型，大型，庞大的工作。 Nudge的操作与FCF相同，只是每当{\ it small}作业到达时，发现{\ it that and}工作在队列的后面等待时，除非大型工作已经参与了较早的交换。 在本文中，我们表明，在较弱的条件下，FCF可以随机改善。我们考虑一个具有$ 2 $的工作类型的系统，在类型为$ 1 $和$ 2 $的工作之间有限地交换，但是如果类型为-1 $ 1 $的工作不一定小于类型-2美元的工作。更具体地说，我们介绍并研究了Nudge-$ k $调度算法，该算法允许类型-1 $ $ 1 $的作业与最多$ k $ type-2 $ 2 $ $ 2 $的工作在排队后面等待，而Type-2 $ 2 $ absip可以涉及最多交换。当两种作业类型都遵循相类型的分布时，我们提出了针对响应时间分布的明确表达式。关于渐近尾的改善比（ATIR），我们为ATIR提供了一个简单的表达，以及最大化ATIR的$ K $。我们表明，只要类型为2 $ 2 $的工作，ATIR是正面的，最佳的$ K $倾向于无限交通繁忙。
Recently it was shown that, contrary to expectations, the First-Come-First-Served (FCFS) scheduling algorithm can be stochastically improved upon by a scheduling algorithm called {\it Nudge} for light-tailed job size distributions. Nudge partitions jobs into 4 types based on their size, say small, medium, large and huge jobs. Nudge operates identical to FCFS, except that whenever a {\it small} job arrives that finds a {\it large} job waiting at the back of the queue, Nudge swaps the small job with the large one unless the large job was already involved in an earlier swap. In this paper, we show that FCFS can be stochastically improved upon under far weaker conditions. We consider a system with $2$ job types and limited swapping between type-$1$ and type-$2$ jobs, but where a type-$1$ job is not necessarily smaller than a type-$2$ job. More specifically, we introduce and study the Nudge-$K$ scheduling algorithm which allows type-$1$ jobs to be swapped with up to $K$ type-$2$ jobs waiting at the back of the queue, while type-$2$ jobs can be involved in at most one swap. We present an explicit expression for the response time distribution under Nudge-$K$ when both job types follow a phase-type distribution. Regarding the asymptotic tail improvement ratio (ATIR) , we derive a simple expression for the ATIR, as well as for the $K$ that maximizes the ATIR. We show that the ATIR is positive and the optimal $K$ tends to infinity in heavy traffic as long as the type-$2$ jobs are on average longer than the type-$1$ jobs.
