非线程调度场景下实现最低日均工作量的任务调度算法咨询

核心算法逻辑 #

你要的场景属于带截止日期的单资源非抢占调度优化，目标是同时满足「最低日均工作量」「工作量分布均匀」「尽量单日仅处理单个任务减少切换」三个需求，用改进的贪心算法即可实现，无需暴力枚举：

• 第一步：计算基准日工作量阈值
  把所有任务的总工作量相加，除以所有任务中最晚的截止日期，得到的就是理论最低的日均工作量，你的例子里总工作量3+2=5，最晚截止第5天，阈值就是1，这就是你要的日均最低值的基准。
• 第二步：任务预排序
  按照任务截止日期升序排序，截止日期相同的按总工作量降序排序，参考最早截止日期优先（EDF）调度逻辑，优先保障更早到期的任务不逾期。
• 第三步：逐天分配工作量
  从第1天开始逐天安排：
  1. 当天的工作量目标为第一步算出的基准阈值，尽量拉满到该值
  2. 优先分配给当前未完成、截止日期最近的任务，优先把单个任务的剩余工作量全部安排在当天，只要不超过当日目标阈值
  3. 当日目标阈值被填满，或者所有未完成任务都安排完，就进入下一天的分配

示例验证 #

用你给出的两个任务场景验证：

1. 总工作量5，最晚截止5天，阈值1
2. 任务排序：任务1（截止3天，3小时）> 任务2（截止5天，2小时）
3. 第1-3天，每天把1小时额度全部分配给任务1，3天刚好完成任务1
4. 第4-5天，每天把1小时额度全部分配给任务2，2天刚好完成任务2
   最终的调度结果和你期望的完全一致，日工作量全部为1，单日仅处理单个任务。

扩展优化 #

如果遇到多个任务截止日期交叉，无法做到单日仅处理单个任务的情况，可以加一层优化约束：优先用最少的任务凑满当日的工作量阈值，尽可能降低单日并行处理的任务数。
如果业务场景需要绝对最优解，可以用整数线性规划建模求解，约束条件如下：

1. 每个任务的总分配时长 = 任务总工作量
2. 任务的所有分配必须发生在其截止日期之前
3. 最小化每日总工作量的最大值
4. 可选约束：最小化每日处理的任务总数
   这个算法的时间复杂度为O(N log N + D*N)，N为任务总数，D为总天数，处理日常量级的任务完全无压力。

内容的提问来源于stack exchange，提问作者James