在算法功课调遣范围，计较资源经常被视为静态的：管事用具有固定数目的CPU，或集群具有恒定数目的可用机器。关系词，当代大范围云计较的本质要动态得多。由于硬件故障、顾惜周期或功率截至，资源会不断波动。

更伏击的是，在分层调遣系统中，高优先级任务经常按需占用资源，为低优先级批处理功课留住时变的"剩余"容量。念念象一家餐厅，VIP客户在不同手艺预订餐桌；在剩余餐桌上安排日常客户可能成为一个复杂的难题。

当这些低优先级功课是不可中断的时——意味着它们不可暂停并稍后复原——风险很高。要是由于容量下跌而中断功课，扫数程度都将丢失。调遣器必须决定：咱们当今运转这个长功课，冒着改日容量下跌的风险吗？如故恭候更安全的手艺窗口，可能错过截止日历？

在SPAA 2025上发表的"时变容量下的非霸占式隐晦量最大化"接洽中，咱们运转接洽在可用容量顺手艺波动的环境中最大化隐晦量（告捷功课的总权重或数目）。咱们的接洽为这个问题的几个变体提供了首个常数因子类似算法，为在不巩固云环境中构建更宏大的调遣器提供了表面基础。

调遣模子瞎想

咱们的职责要点是瞎想一个拿获多个要津照应的调遣模子。咱们辩论一个容量设置顺手艺变化的单机器（或集群）。该设置决定了在职何给定时刻不错并走运行的最大功课数目。咱们给定一系列潜在功课，每个功课由四个要津属性特征化：

隐晦量最大化问题的实例包括一组功课，每个功课都有其发布手艺、截止日历、抓续手艺和价值，以及机器的容量设置。容量设置详情在职何给定手艺不错同期处理的最大功课数目。

盘算推算是取舍功课子集并调遣它们，使每个采选的功课在其有用窗口内连络运行。要津照应是任何时候，运行功课的总和不得跳跃现时容量。咱们的盘算推算是最大化隐晦量，即扫数完奏效课的总权重。

咱们在两个不同的环境中惩办这个问题：

离线栽植：运筹帷幄改日的政策

{jz:field.toptypename/}

在不错提前运筹帷幄的离线栽植中，咱们发现简便政策领略独特地好。由于在此栽植中找到最优调遣被觉得是"NP贫窭"（即莫得已知的找到完整谜底的捷径），咱们专注于具有严格类似保证的算法。咱们分析了一种称为狡计的短视政策，它迭代地调遣最早完成的功课，开云体育官网并讲授当功课具有单元利润时，这种简便启发式收尾了1/2类似。这意味着即使在挣扎性取舍功课和容量设置的最坏情况下，咱们的简便算法也能保证调遣至少一半的最优功课数目。当不同功课不错有不同的关系利润时，咱们使用原对偶框架收尾1/4类似。

在线栽植：及时有筹画的挑战

竟然的复杂性在于在线栽植，其中功课动态到达，调遣器必须作念出立即的、不可取销的有筹画，而不知谈接下来会到达什么功课。咱们通过竞争比量化在线算法的性能，竞争比是咱们在线算法隐晦量与提前表露扫数功课的最优算法隐晦量之间的最坏情况比拟。

圭臬的非霸占式算法在这里都备失败，因为它们的竞争比接近零。这是因为调遣长功课的单一虚假决定可能破损调遣好多改日较小功课的可能性。

为了使在线问题可解并反馈本质寰球的天真性，咱们接洽了两个模子，九游体育允许在出现更好契机时中断行动功课（尽管只好再行启动并稍后非霸占式完成的功课才算告捷）。

功课重启模子

在此模子中，在线算法被允许中断现时推行的功课。诚然中断功课上已推行的部单干作丢失，但功课自身仍留在系统中并不错重试。

咱们发现允许功课重启提供的天真性特殊有利。迭代调遣最早完奏效课的狡计变体持续收尾1/2竞争比，与离线栽植中的效果相匹配。

功课丢弃模子

在这个更严格的模子中，中断功课上推行的扫数职责都丢失，功课自身被始终丢弃。厄运的是，咱们发当今这个严格模子中，任安在线算法都可能际遇一系列功课，迫使它作念出断绝它在改日鼎沸更多职责的有筹画。扫数在线算法的竞争比再次接近零。

分析上述贫窭实例使咱们专注于扫数功课分享共同截止日历的本色场景。关于这种共同截止日历实例，咱们瞎想了新颖的常数竞争算法。咱们的算法特殊直不雅，咱们在此形色单元容量设置的简便栽植算法，即咱们不错在职何手艺调遣单个功课。

在此栽植中，咱们的算法通过将已到达的功课分拨给不相交的手艺间隔来顾惜试探性调遣。当新功课到达时，算法通过选拔以下四个手脚中的第一个适用手脚来修改试探性调遣：

1. 通过将功课搁置在空间隔中将功课添加到试探性调遣

2. 要是新功课权贵更小，则从试探性调遣中替换另一个改日功课

3. 要是新功课小于推行功课的剩余手艺，则中断现时推行的功课

4. 丢弃新到达的功课

咱们的主要效果标明，该算法对随便容量设置的泛化为此问题提供了首个常数竞争比。表情上，咱们赢得1/11的竞争比。诚然保证仅调遣约9%的最优功课数目听起来像是一个弱保证，但这是一个即使在最挣扎情况下也成立的最坏情况保证。

改日瞻望

跟着云基础形状变得愈加动态，调遣算法中静态容量的假定不再成立。本文运转了时变容量下隐晦量最大化的负责接洽，弥合了表面调遣模子与数据中心波动本质之间的差距。

诚然咱们拓荒了宏大的常数因子类似，但仍有增漫空间。咱们在线栽植的1/11竞争比与表面上限1/2之间的差距标明可能存在更高效的算法。探索马上算法或对改日容量不都备了解的场景可能为本质寰球诈欺产生更好的效果。

Q&A

Q1：什么是时变容量下的非霸占式功课调遣问题？

A：这是指在云计较环境中，由于硬件故障、顾惜或高优先级任务占用，可用计较资源不断波动的情况下，若何调遣那些一朝运转就不可暂停的功课。盘算推算是最大化告捷完奏效课的总权重或数目。

Q2：为什么传统的静态调遣算法在当代云环境中不适用？

A：因为当代大范围云计较的本质是动态的，资源会因为硬件故障、顾惜周期或功率截至不断波动。在分层调遣系统中，高优先级任务会按需占用资源，为低优先级功课留住时变的剩余容量，传统静态算法无法有用处理这种动态性。

Q3：接洽中建议的狡计算法在离线和在线栽植中领略若何？

A：在离线栽植中，狡计算法收尾了1/2类似比，即使在最坏情况下也能保证调遣至少一半的最优功课数目。在允许功课重启的在线栽植中雷同收尾1/2竞争比，但在严格的功课丢弃模子中，扫数在线算法的竞争比都接近零。