根据 http://www-labs.iro.umontreal.ca/~dift6221/demicheli4/sch2.4.ps.pdf，当图是一棵树时，胡的算法是最优的。对于一般单位长度边 DAG，它会失败吗？在这种情况下它不是最佳的原因是什么？有这种失败的例子吗？
我花了一段时间，但我能够想出几个反例。关键是让浅层任务阻止大量任务，这在树内是不允许的。
假设您最多可以并行执行 k=10 个任务。您有 40 个任务，标记为 1 到 40。
任务 1~10 块任务 11 阻止任务 12。(这是树内。到目前为止一切顺利。 现在任务 13 阻止任务 14~40。(13.有多个父母，违规(
使用贪婪算法，第一步已经完成了任务 1~10，剩下 13 个仍然阻塞 14~40。步骤 2 只能处理 11 和 13。现在算法不能在 4 个步骤中完成，这是你能做的最好的事情。
最佳时间表是做 13 个，说 1~9 个，解锁 14~40 个，分 4 个步骤完成，没有任何工人空转。