arXiv:2505.21331cs.DScs.GT2025-05

针对内容审核中成本不确定且动态变化的问题,提出新调度算法OaRC。

Scheduling in Queueing Systems with Uncertain and Evolving Holding Costs

  • 将每个任务视为马尔可夫滑雪租赁问题,动态调整服务优先级。
  • 理论证明其性能与最优解差距为√N量级,系统规模大时渐近最优。
  • 适用于内容审核等需处理不确定成本的实时场景,优于传统方法。

在社交媒体内容审核中,延迟审查的成本与内容的浏览轨迹相关,该轨迹波动且事前未知。针对此类不确定且动态演变的持有成本,本文研究一个作业状态基于马尔可夫链演化、状态相关瞬时持有成本的排队模型。研究表明,在此类环境下,经典的即时成本(cμ规则)和期望剩余成本(cμ/θ规则)均次优。通过将每个任务视为马尔可夫滑雪租赁问题,提出一种新的基于索引的调度算法——机会调整剩余成本(OaRC),能根据未来不确定性部分消除的机会调整优先级。理论分析表明,OaRC的次优性差距为 ilde{O}( )(N为系统规模),该界独立于状态空间大小,说明当系统规模趋于无穷时,其在过载系统中达到渐近最优。仿真验证基于在线广告和用户生成内容两类真实成本模式,涵盖合成与真实数据集,结果一致显示OaRC持续优于基于经典规则的现有实践。

原文摘要 · Abstract (English)

In content moderation for social media platforms, the cost of delaying the review of a content is proportional to its view trajectory, which fluctuates and is apriori unknown. Motivated by such uncertain and evolving holding costs, we consider a queueing model where job states evolve based on a Markov chain with state-dependent instantaneous holding costs. We demonstrate that in the presence of such uncertain and evolving holding costs, the two canonical algorithmic principles, instantaneous-cost ($cμ$-rule) and expected-remaining-cost ($cμ/θ$-rule), are suboptimal. By viewing each job as a Markovian ski-rental problem, we develop a new index-based algorithm, Opportunity-adjusted Remaining Cost (OaRC), that adjusts to the opportunity of serving jobs in the future when uncertainty partly resolves. We show that the suboptimality gap of OaRC scales as $\tilde{O}(\sqrt{N})$, where $N$ is the system size. This bound shows that OaRC achieves asymptotic optimality for overloaded systems when the system size $N$ scales to infinity. Moreover, the bound is independent of the state-space size, which is a desirable property when job states contain contextual information. We corroborate our results with an extensive simulation study based on two holding cost patterns (online ads and user-generated content) that arise in content moderation for social media platforms. Our simulations based on synthetic and real datasets demonstrate that OaRC consistently outperforms existing practice, which is based on the two canonical algorithmic principles.

排队调度不确定性内容审核优化算法

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。