几个任务需要共用一台处理器时,按截止时间排序还不一定能让最多任务都按时完成。某个耗时很长的任务可能挤掉多件较短任务,适时移出它能改善按时完成数量。
先明确输入与规则
本例所有任务在零时刻可用,不可拆分,中途没有新任务加入。先按截止时间排序,同截止按编号;逐个加入计划并累计耗时。若累计时间超过当前截止时间,就移出已选任务中耗时最长的一件,同长度移出编号较大者。
本例的独立记录
八项任务编号零至七,各项耗时与截止时间为[{'duration': 8, 'deadline': 14}, {'duration': 7, 'deadline': 4}, {'duration': 8, 'deadline': 8}, {'duration': 12, 'deadline': 20}, {'duration': 7, 'deadline': 19}, {'duration': 1, 'deadline': 23}, {'duration': 10, 'deadline': 19}, {'duration': 7, 'deadline': 14}]。
考察任务 | 本步移出任务 | 保留总时长 | 暂定集合 1 | 1 | 0 | [] 2 | None | 8 | [2] 0 | 2 | 8 | [0] 7 | 0 | 7 | [7] 4 | None | 14 | [7, 4] 6 | 6 | 14 | [7, 4] 3 | 3 | 14 | [7, 4] 5 | None | 15 | [7, 4, 5] 最终任务 | 完成时刻 | 截止时刻 7 | 7 | 14 4 | 14 | 19 5 | 15 | 23 按时完成3项。
记录中的编号只用来区分本例对象,不应与大小排名或另一组记录的身份混淆。先核对单位和边界,再跟随中间值检查结果。空结果、零值与尚未确定是不同状态;分数保留精确含义,显示小数只为方便阅读。
怎样复算
保留下来的任务再按截止顺序执行,逐个完成时刻都不得超过自身截止时间。目标是最大化按时完成的件数,不是总价值,也不是全部任务的最短总用时。未保留任务可以另排在这些任务之后,但不计入本例的按时集合。
把输入规模控制得很小,就可以枚举所有任务子集,对照最多按时件数。检查时既要验证输出计划确实可行,也要确认没有更大可行子集;只找到一份能按时执行的计划,并不能证明它已经最好。
适用条件与限制
这个规则依赖所有任务从一开始都可执行、每项价值相同等前提。若有先后依赖、释放时刻或不同奖励,移出最长任务不再自动保证目标最优,应重新说明问题与算法。
练习时可以一次只改变一个条件,比较差异从哪个步骤开始。若自己的结果不同,先核对是否采用同样的规则,再定位第一个不一致的中间状态,不要只修改最终答案。输入与运算过程需要一起保存,才能判断结论究竟适用于哪一个具体场景。
