最小逾期任务

单机非抢先调度中最小化逾期任务数;等价于选最大可准时子集,Moore–Hodgson 用最大堆反悔最长任务。

标签 调度 / 单机调度 / 贪心 / 反悔贪心 / 堆

题目描述

有 𝑛 个任务,第 𝑖 个任务的加工时间为 𝑝𝑖,截止时间为 𝑑𝑖。所有任务在时刻 0 到达,单机、非抢先执行。若任务 𝑖 的完工时间 𝐶𝑖>𝑑𝑖,则称它逾期,记 𝑈𝑖=1,否则记 𝑈𝑖=0。

求一种执行顺序,使逾期任务数

∑𝑖=1𝑛𝑈𝑖

最小。

1≤𝑛≤105,1≤𝑝𝑖,𝑑𝑖≤109。

题解

只需决定哪些任务准时。若准时任务集合为 𝑆={𝑖1,…,𝑖𝑘},按截止时间升序排列:

𝑑𝑖1≤…≤𝑑𝑖𝑘,

则 𝑆 全部准时,当且仅当对每个 𝑚=1,…,𝑘 都有

∑𝑗=1𝑚𝑝𝑖𝑗≤𝑑𝑖𝑚.

逾期任务可以排在准时任务之后,所以原问题等价于选择最大的可行准时任务集合。

Moore–Hodgson 算法

按截止时间升序处理任务,维护已选集合 𝑆、总加工时间 𝑃 和 𝑆 中加工时间的最大堆。

对每个任务 𝑖:

  • 把 𝑖 加入 𝑆,并令 𝑃←𝑃+𝑝𝑖;
  • 若 𝑃>𝑑𝑖,删除 𝑆 中加工时间最长的任务 𝑗,并令 𝑃←𝑃−𝑝𝑗。

结束后,|𝑆| 是最大准时任务数,答案为 𝑛−|𝑆|。

若加入后仍然可行,保留它不会破坏可行性。若加入后不可行,任何可行解都必须从 𝑆∪{𝑖} 中删去至少一个任务;删去加工时间最长者使剩余总加工时间最小,因此不会比删去其他任务更差。由交换论证归纳,每一步都保留了某个最优解,算法得到最大准时任务集合。

复杂度

排序为 𝑂(𝑛log𝑛),堆操作共 𝑂(𝑛log𝑛),空间为 𝑂(𝑛)。

参考

源码位置