最小逾期任务
单机非抢先调度中最小化逾期任务数;等价于选最大可准时子集,Moore–Hodgson 用最大堆反悔最长任务。标签 调度 / 单机调度 / 贪心 / 反悔贪心 / 堆
题目描述
有 个任务,第 个任务的加工时间为 ,截止时间为 。所有任务在时刻 到达,单机、非抢先执行。若任务 的完工时间 ,则称它逾期,记 ,否则记 。
求一种执行顺序,使逾期任务数
最小。
,。
题解
只需决定哪些任务准时。若准时任务集合为 ,按截止时间升序排列:
则 全部准时,当且仅当对每个 都有
逾期任务可以排在准时任务之后,所以原问题等价于选择最大的可行准时任务集合。
Moore–Hodgson 算法
按截止时间升序处理任务,维护已选集合 、总加工时间 和 中加工时间的最大堆。
对每个任务 :
- 把 加入 ,并令 ;
- 若 ,删除 中加工时间最长的任务 ,并令 。
结束后, 是最大准时任务数,答案为 。
若加入后仍然可行,保留它不会破坏可行性。若加入后不可行,任何可行解都必须从 中删去至少一个任务;删去加工时间最长者使剩余总加工时间最小,因此不会比删去其他任务更差。由交换论证归纳,每一步都保留了某个最优解,算法得到最大准时任务集合。
复杂度
排序为 ,堆操作共 ,空间为 。