在算法作业调度领域计算资源通常被视为静态的服务器具有固定数量的CPU或集群具有恒定数量的可用机器。然而现代大规模云计算的现实要动态得多。由于硬件故障、维护周期或功率限制资源会不断波动。更重要的是在分层调度系统中高优先级任务通常按需占用资源为低优先级批处理作业留下时变的剩余容量。想象一家餐厅VIP客户在不同时间预订餐桌在剩余餐桌上安排普通客户可能成为一个复杂的难题。当这些低优先级作业是不可中断的时——意味着它们不能暂停并稍后恢复——风险很高。如果由于容量下降而中断作业所有进度都将丢失。调度器必须决定我们现在开始这个长作业冒着未来容量下降的风险吗还是等待更安全的时间窗口可能错过截止日期在SPAA 2025上发表的时变容量下的非抢占式吞吐量最大化研究中我们开始研究在可用容量随时间波动的环境中最大化吞吐量成功作业的总权重或数量。我们的研究为这个问题的几个变体提供了首个常数因子近似算法为在不稳定云环境中构建更强大的调度器提供了理论基础。调度模型设计我们的工作重点是设计一个捕获多个关键约束的调度模型。我们考虑一个容量配置随时间变化的单机器或集群。该配置决定了在任何给定时刻可以并行运行的最大作业数量。我们给定一系列潜在作业每个作业由四个关键属性特征化吞吐量最大化问题的实例包括一组作业每个作业都有其发布时间、截止日期、持续时间和价值以及机器的容量配置。容量配置确定在任何给定时间可以同时处理的最大作业数量。目标是选择作业子集并调度它们使每个选定的作业在其有效窗口内连续运行。关键约束是任何时候运行作业的总数不得超过当前容量。我们的目标是最大化吞吐量即所有完成作业的总权重。我们在两个不同的环境中解决这个问题离线设置规划未来的策略在可以提前规划的离线设置中我们发现简单策略表现出奇地好。由于在此设置中找到最优调度被认为是NP困难即没有已知的找到完美答案的捷径我们专注于具有严格近似保证的算法。我们分析了一种称为贪婪的短视策略它迭代地调度最早完成的作业并证明当作业具有单位利润时这种简单启发式实现了1/2近似。这意味着即使在对抗性选择作业和容量配置的最坏情况下我们的简单算法也能保证调度至少一半的最优作业数量。当不同作业可以有不同的关联利润时我们使用原对偶框架实现1/4近似。在线设置实时决策的挑战真正的复杂性在于在线设置其中作业动态到达调度器必须做出立即的、不可撤销的决策而不知道接下来会到达什么作业。我们通过竞争比量化在线算法的性能竞争比是我们在线算法吞吐量与提前知晓所有作业的最优算法吞吐量之间的最坏情况比较。标准的非抢占式算法在这里完全失败因为它们的竞争比接近零。这是因为调度长作业的单一错误决定可能破坏调度许多未来较小作业的可能性。为了使在线问题可解并反映现实世界的灵活性我们研究了两个模型允许在出现更好机会时中断活动作业尽管只有重新启动并稍后非抢占式完成的作业才算成功。作业重启模型在此模型中在线算法被允许中断当前执行的作业。虽然中断作业上已执行的部分工作丢失但作业本身仍留在系统中并可以重试。我们发现允许作业重启提供的灵活性非常有益。迭代调度最早完成作业的贪婪变体继续实现1/2竞争比与离线设置中的结果相匹配。作业丢弃模型在这个更严格的模型中中断作业上执行的所有工作都丢失作业本身被永远丢弃。不幸的是我们发现在这个严格模型中任何在线算法都可能遇到一系列作业迫使它做出阻止它在未来满足更多工作的决策。所有在线算法的竞争比再次接近零。分析上述困难实例使我们专注于所有作业共享共同截止日期的实际场景。对于这种共同截止日期实例我们设计了新颖的常数竞争算法。我们的算法非常直观我们在此描述单位容量配置的简单设置算法即我们可以在任何时间调度单个作业。在此设置中我们的算法通过将已到达的作业分配给不相交的时间间隔来维护试探性调度。当新作业到达时算法通过采取以下四个动作中的第一个适用动作来修改试探性调度1. 通过将作业放置在空间隔中将作业添加到试探性调度2. 如果新作业显著更小则从试探性调度中替换另一个未来作业3. 如果新作业小于执行作业的剩余时间则中断当前执行的作业4. 丢弃新到达的作业我们的主要结果表明该算法对任意容量配置的泛化为此问题提供了首个常数竞争比。形式上我们获得1/11的竞争比。虽然保证仅调度约9%的最优作业数量听起来像是一个弱保证但这是一个即使在最对抗情况下也成立的最坏情况保证。未来展望随着云基础设施变得更加动态调度算法中静态容量的假设不再成立。本文开始了时变容量下吞吐量最大化的正式研究弥合了理论调度模型与数据中心波动现实之间的差距。虽然我们建立了强大的常数因子近似但仍有增长空间。我们在线设置的1/11竞争比与理论上限1/2之间的差距表明可能存在更高效的算法。探索随机算法或对未来容量不完全了解的场景可能为现实世界应用产生更好的结果。QAQ1什么是时变容量下的非抢占式作业调度问题A这是指在云计算环境中由于硬件故障、维护或高优先级任务占用可用计算资源不断波动的情况下如何调度那些一旦开始就不能暂停的作业。目标是最大化成功完成作业的总权重或数量。Q2为什么传统的静态调度算法在现代云环境中不适用A因为现代大规模云计算的现实是动态的资源会因为硬件故障、维护周期或功率限制不断波动。在分层调度系统中高优先级任务会按需占用资源为低优先级作业留下时变的剩余容量传统静态算法无法有效处理这种动态性。Q3研究中提出的贪婪算法在离线和在线设置中表现如何A在离线设置中贪婪算法实现了1/2近似比即使在最坏情况下也能保证调度至少一半的最优作业数量。在允许作业重启的在线设置中同样实现1/2竞争比但在严格的作业丢弃模型中所有在线算法的竞争比都接近零。