算法分析第五讲.ppt

5.4 最优二分检索树 5.5 0/1背包问题 5.6 可靠性设计 5.7 货郎担问题(售货员问题) 5.8 流水线调度问题 图8.1 例8.1的两种可能的调度 时间 1 2 3 4 5 6 7 8 9 10 11 12 ? 1 2 3 4 5 6 7 8 9 10 11 p1 ? ? ? ? ? ? ? ? ? ? T11 ? ? ? ? ? ? ? ? ? P2 T22 T21 T22 ? ? ? ? ? ? T22 T21 ? ? ? ? ? P3 ? ? ? ? ? T31 T32 ? ? ? T32 ? T31 流水线上的作业调度，有两种基本方式：一种是非抢先调度，它要求在任何一台设备上处理一个任务一直到完成才能处理另一任务。另一种是抢先调度，它没有以上要求，图8.1左部表示一种抢先调度，而右部则表示一种非抢先调度。作业i的完成时间fi(S)是在S调度方案下作业i的所有任务得以完成的时间。在图8.1左部,f1(S)=10，f2(S)=12。在图8.1右部,f1(S)=11，f2(S)=5。调度S的完成时间F(S)由下式给出： F(S) = max{fi(S)} (8.1) 1≤i≤n 平均流动时间MFT(S)定义为 MFT(S) = (1/n)* ∑fi(S) (8.2) 1≤i≤n 一组给定作业的最优完成时间OFT调度是一种非抢先调度S，它对所有非抢先调度而言，F(S)的值最小。可以很容易地给出抢先最优完成时间(POFT)，最优平均完成时间(OMFT)和抢先最优平均完成时间(POMFT)等调度的相应定义。 当m＞2时，得到OFT和POFT调度的一般问题是难于计算的问题，得到OMFT调度的一般问题也是难于计算的问题(见第8讲)。本节只讨论当m=2时获取OFT调度这种特殊情况的算法。 为方便起见，用aj表示t1i，bj表示t2i。在两台设备情况下容易证明：在两台设备上处理的任务若不按作业的排列次序处理，则在调度完成时间上不比按次序处理弱(注意，若m＞2则不然)。因此，调度方案的好坏完全取决于这些作业在每台设备上被处理的排列次序。当然，每个任务都应在最早的可能时间开始执行。图8.2所示的调度就完全由作业的排列次序5,1,3,2,4所确定。为讨论简单起见，假定ai≠0，l≤i≤n。事实上，如果允许有ai=0的作业，那么最优调度可通过以下方法构造出来：首先对于所有ai≠0的作业求出一种最优调度的排列，然后把所有ai=0的作业以任意次序加到这一排列的前面。 a2 b4 b2 b1 b5 p2 a4 a3 a1 a5 p1 图8.2 一种调度 容易看出，最优调度的排列具有下述性质：在给出了这个排列的第一个作业后，剩下的排列相对于这两台设备在完成第一个作业时所处的状态而言是最优的。假设对作业1,2, …, k的一种调度排列为σ1,σ2, …, σk。对于这种调度，设h1和h2分别是在设备P1和P2上完成任务(T11,T12, …, T1k)和(T21,T22, …, T2k)的时间；又设t= h2-hl，那么，在对作业1,2, …, k作了一系列决策之后，这两台设备所处的状态可以完全由t来表征。它表示如果要在设备P1和P2上处理一些别的作业，则必须在这两台设备同时处理前k个作业的不同的任务后，设备P2还要用大小为t的时间段处理前k个作业中没处理完的任务，即在t这段时间及其以前，设备P2不能用来处理别的作业的任务。记这些别的作业组成的集合为S，假设g(S,t)是上述t下S的最优调度长度，于是作业集合｛1,2, …, n｝的最优长度是g({1,2,…,n}, 0)。 由最优调度排列所具有的性质可得： g ({1,2,…,n}, 0) = min{ai + g({1,2,…,n} - {i},bi)} (8.1) 1≤i≤n 将(8.1)式推广到一般情况，对于任意的S和i可得(8.2)式。式中要求：g(Ф,t)=max{t,0}且ai≠0，1≤i≤n。 g(S,t) = min{ai + g(S-{i}, bi+max{t-ai,0})} (8.2)