例如:
Task C depends on Task B1's completion
Task C also depends on Task B2' completion
Task B1 depends on A's completion
Task B2 depends on A's completion, B2 also has a value of 1600(4pm), which means it can only start at or after 1600
Task A depends on nothing, A also has a value of 1500 (3pm), which means it can only start at or after 1500.
这将是一个具有4个顶点(任务)的图:a、B1、B2、C。作业B1或B2只能在a完成时运行,作业C只能在B1和B2都完成时运行。
A->B1->B2->C
A->B2->B1->C
但序列1的时间优化程度更高,因为在序列2中,我们必须等到1600点才能运行B2,其他的都要等待。在序列1中,我们可以先运行B1,然后等到1600。虽然总的完成时间可能不会有所不同,但优化意味着“尽可能早地运行每个作业”。同样为了简单起见,让我们不要考虑作业持续时间:假设每个作业在运行后立即完成。
所以问题是,什么是一个明智的算法来输出这样一个时间优化序列?我知道,如果不考虑时间优化,这只是一个拓扑排序,但如何增强该算法以实现时间优化?
