如何计算指定并发数下并行任务的总耗时估算值？

具体案例计算（最优调度场景） #

给定任务耗时列表 [30, 10, 15, 20, 25]，并发数3，要算出最短总耗时，按以下步骤操作：

1. 将任务按耗时从大到小排序：[30, 25, 20, 15, 10]
2. 初始化3个并发队列，先放入前3个最大的任务，此时队列累计耗时为：[30, 25, 20]
3. 把剩余任务依次加到当前累计耗时最小的队列：
   • 剩余第一个任务15，加到耗时20的队列，队列变为：[30, 25, 35]
   • 剩余第二个任务10，加到耗时25的队列，队列变为：[30, 35, 35]
4. 最终总耗时取队列中的最大值，即35秒

通用精确计算逻辑 #

要得到最优调度下的最短总耗时，核心是让各并发队列的负载尽可能均衡，步骤通用：

• 把所有任务按耗时从大到小排序
• 维护一个长度等于并发数的列表，记录每个队列的累计耗时
• 依次将剩余任务添加到当前累计耗时最小的队列中
• 最终总耗时为该列表的最大值

粗略估算公式（快速评估） #

如果不需要精确值，可通过两个边界值取较大者作为估算结果：

• 边界1（下限）：单个任务的最长耗时（无论怎么并发，最长任务必须完成，总耗时不可能短于它）
• 边界2（理论最优）：所有任务总耗时 ÷ 并发数（理想完全均衡的情况，实际因任务不可拆分，总耗时≥该值）

用案例验证：

• 所有任务总耗时：30+10+15+20+25=100秒，100÷3≈33.33秒
• 最长任务耗时25秒
• 取较大值33.33秒，与实际最优耗时35秒接近

当任务数量远多于并发数、单任务耗时差异较小时，该估算精度更高；若存在超长任务，下限值会成为总耗时的主导。

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