借助分类模型的鲁棒非预知调度

arXiv:2610.01343v1 公告类型：新 摘要：我们研究经典的单机调度问题：在非预知环境下最小化作业完工时间之和，其中每个作业的处理时间在其完成之前始终未知。这是一个困难问题，不存在具有常数竞争比的算法。受鲁棒优化和学习增强算法的启发，我们引入了一种新颖的鲁棒性框架，利用分类模型提供的结构信息来克服这一限制。具体而言，我们假设作业被划分为若干类别，并且可以获得分类器的混淆矩阵，其中条目 $(k,\ell)$ 表示被预测为属于类别~$k$、但实际属于类别~$\ell$ 的作业数量。通过这种方式，我们能够将不确定性刻画为每个预测类别内的一组排列，而不是一组离散的数值场景，从而避免 Min-Max 和 Min-Max Regret 等经典鲁棒度量所带来的计算困难。除这些最坏情况度量外，我们还考虑所有场景下的期望目标值。我们首先提出一种最优的非自适应策略，该策略对于三种鲁棒准则均不依赖于具体信息。随后，我们研究自适应算法和随机化算法，并证明当矩阵具有特定结构性质时，它们能够优于最优非自适应策略。