流水作业调度问题 难点解释

流水作业调度之作业拆分

T是对集合最优调度后完成作业所需要的时间，也就是完成作业所需要的最短时间。

T(N, 0)是指对全集N按最优调度完成作业所需要的时间。其中第二个参数为0，是因为开始完成全集N时，M2机器上没有滞留作业，不需要等待。

T(S, t)是一边情况下的最优调度所需要的最短时间，其中第一个参数S是剩下所需要完成的作业集合，而t是指在开始完成S中的作业时，M2机器上还遗留着一些作业需要处理，t是完成这些作业所需要的时间。

从直观上可以看出t的大小会影响整体作业完成的时间，如果M2上遗留任务所需的时间t很大，则M2会一直处在完成上个作业的进程中，即便M1已经处理完S中的第一个作业，该作业也无法进入M2中进行第二步处理，因此整个系统就会拥塞，必须等遗留任务全部完成M2才能加工下个任务。而如果M2上遗留任务所需的时间t很大时，则会出现这样一种情况：M1处理完集合S中的第一个任务时，M2早已经处理好遗留任务在等待完成的任务进入M2执行了，这时，这个遗留任务对于整个系统来说时没有影响的。