3、期限di>0(整数)，并可在等量的时间内完成；仅当作业i在其截止期限内完成时，才获得效益值pi；要求确定一个作业子集和最优调度序列，获得最大的总效益值，即求使最大化的可行作业集J，J中的每个作业均可在其截止期限内完成。例已知n=4,p=(100,10,15,20),d=(2,1,2,1),其中的九个可行解：(1)1100(2)210(3)315(4)420(1,2)2,1110(1,3)1,3或3,1115(1,4)4,1120(2,3)2,325(3,4)4,335序号可行解调度顺序总效益值二、基本贪心算法贪心选择标准直接以作为选择标
4、准，即按全体作业pi值的非升次序排序，在使获得最大增量的前提下，逐个并入可调度的下一个作业，即使每个并入的作业均能在其截止期限内完成。概略描述GreedyJobScheduling(int*d,float*p,int*J,intn){i=1;J[0]=i;k=1;J[k:n-1]=0;/*J[n]为作业集数组,p[0]≥p[1]≥…≥p[n-1]*/for(i=2;i<=n;i++)if(J[0:k-1]∪i为可行解)J[k++]=i;}可行作业集的充要条件σ=i1i2…ik为可行调度序列的充要条件di1≤di2≤…≤dik;dij≥j
5、，1≤j≤k。定理设J是k个作业的集合，σ=i1i2…ik是J中作业的一种排列，它使得di1≤di2≤…≤dik，当且仅当作业集J中的作业可以按照σ的次序来处理而又不违反任何一个截止期限，J是一个可行解，即σ是一个可行调度序列。逐步求精位置01…k-1k…n-1J[n]i0i1…ik-10…0条件D[J[0]]≤D[J[1]]≤…≤D[J[k-1]];D[J[i]]≥i+1,0≤i≤k-1.对作业ik令r=k-1,当r≥0,D[k]r+1时,逆向查找r,找到满足D[k]≥D[J[r]]的插入点r+1;在
6、位置r+1可插入作业ik的条件是先前的k-r个作业延迟一个时间单位后不超过截止期限,否则,不能插入.插入后J[n]i0i1…ik-1ik0…循环,直到余下的n-(k+1)个作业处理完毕GreedyJobScheduling(int*D,float*p,int*J,intn){J[0]=i=1;k=1;J[k:n-1]=0;for(i=2;i<=n;i++){r=k-1;while((r>=0)&&(D[i-1]r+1))r=r-1;if((r==-1)
7、
8、((D[i-1]>=D[J[r]])&&(
9、D[i-1]>r+1))){for(m=k-1;m>=r+1;m--)J[m+1]=J[m];J[r+1]=i;k=k+1;}}}算法和时间复杂度基本贪心算法的缺陷－作业移动三、快速贪心算法n个作业需要的最多时间片k已知n个作业,作业j的截止期限为dj,所需要的最多时间片为k+1个时间片为:[-1,0],[0,1],[1,2],…,[k-1,k]标识为:012…kk=min{n,max{dj}}减少作业移动－分配最晚时间片原则例3.3已知n=5,p=(20,15,10,5,1),d=(2,2,1,3,3).J动作已分配的时间片Ф无无{1
10、}分配2号时间片2{1,2}分配1号时间片1，23号作业已无法在截止期限内完成,舍弃{1,2,4}分配3号时间片1，2，35号作业已无法在截止期限内完成,舍弃最晚空闲时间片的竞争竞争分配最晚可行空闲时间片最
