论文标题
大型服务系统中的近乎最佳的随机箱包装，具有随时间变化的物品大小
Near-Optimal Stochastic Bin-Packing in Large Service Systems with Time-Varying Item Sizes
论文作者
论文摘要
在现代计算系统中，工作资源需求通常会随着时间而变化。在工作计划期间考虑这种时间变异性对于达到绩效目标至关重要。但是，关于如何与时变资源需求安排工作的理论理解是有限的。在此差距的促进的情况下，我们提出了服务系统中随机箱包装问题的一个\ emph {new设置}，该问题允许\ emph {time-nimphing}工作资源需求，也称为传统bin包装术语中的“项目尺寸”。在这种情况下，必须在到达时将作业或“项目”派发到服务器或“ bin”。按照马尔可夫的假设，其资源需求可能会随着时间的推移而变化。一旦工作的服务完成，它就会偏离系统。我们的目标是最大程度地减少处于稳定状态的预期活动服务器或“非空垃圾箱”的数量。 在我们的问题提出的情况下，我们制定了一个名为Join-Reqesting-Server（JRS）的职位调度策略。从广义上讲，JR可以独立评估其当前的作业配置，并决定是否接受其他工作，平衡最大化吞吐量的竞争目标，并最大程度地减少资源能力超支的风险。然后，JRS调度员利用这些单独的评估来决定要派遣哪个服务器到达的服务。 JRS的理论性能保证在于渐近制度，在该制度中，与缩放系数$ r $相对于缩放系数，工作率在线性上缩放。我们表明，JRS在目标值中实现了$ O（\ sqrt {r}）$的加性最优差距，其中最佳目标值为$θ（r）$。当专门针对恒定的工作资源需求时，我们的结果会改善最先进的$ O（R）$最佳差距。我们的技术方法突出了一个新颖的政策转换框架，该框架将策略设计问题减少到单服务器问题中。
In modern computing systems, jobs' resource requirements often vary over time. Accounting for this temporal variability during job scheduling is essential for meeting performance goals. However, theoretical understanding on how to schedule jobs with time-varying resource requirements is limited. Motivated by this gap, we propose a \emph{new setting} of the stochastic bin-packing problem in service systems that allows for \emph{time-varying} job resource requirements, also referred to as `item sizes' in traditional bin-packing terms. In this setting, a job or `item' must be dispatched to a server or `bin' upon arrival. Its resource requirement may vary over time while in service, following a Markovian assumption. Once the job's service is complete, it departs from the system. Our goal is to minimize the expected number of active servers, or `non-empty bins', in steady state. Under our problem formulation, we develop a job dispatch policy, named Join-Reqesting-Server (JRS). Broadly, JRS lets each server independently evaluate its current job configuration and decide whether to accept additional jobs, balancing the competing objectives of maximizing throughput and minimizing the risk of resource capacity overruns. The JRS dispatcher then utilizes these individual evaluations to decide which server to dispatch each arriving job to. The theoretical performance guarantee of JRS is in the asymptotic regime where the job arrival rate scales large linearly with respect to a scaling factor $r$. We show that JRS achieves an additive optimality gap of $O(\sqrt{r})$ in the objective value, where the optimal objective value is $Θ(r)$. When specialized to constant job resource requirements, our result improves upon the state-of-the-art $o(r)$ optimality gap. Our technical approach highlights a novel policy conversion framework that reduces the policy design problem into a single-server problem.
