任务时间表问题

1、4.8.3 任务时间表问题问题描述 一个单位时间任务单位时间任务是恰好需要一个单位时间来完成的任务。 给定一个单位时间任务单位时间任务的有限集S。关于S的一个时间表时间表用于描述S中单位时间任务的执行次序。时间表中第1个任务从时间0开始执行直至时间1结束，第2个任务从时间1开始执行至时间2结束，第n个任务从时间n-1开始执行直至时间n结束。具有截止时间截止时间和误时惩罚误时惩罚的单位时间任务时间表问题可描述如下。 (1) n个单位时间任务的集合S=1,2,n； (2) 任务i的截止时间di ,1in,1din，即要求任务i在时间di之前结束； (3) 任务i的误时惩罚wi,1in,即任务i未在

2、时间di之前结束将招致的wi惩罚；若按时完成则无惩罚。 任务时间表问题任务时间表问题要求确定S的一个时间表（最优时间表）使得总误时惩罚达到最小。 这个问题看上去很复杂，然而借助于拟阵拟阵，可以用带权拟阵的贪心算法带权拟阵的贪心算法有效求解。 对于一个给定的S的时间表，在截止时间之前完成的任务称为及时任务及时任务，在截止时间之后完成的任务称为误时任务误时任务。 S的任一时间表可以调整成及时优先形式及时优先形式，即其中所有及时任务先于误时任务，而不影响原时间表中各任务的及时或误时性质。 类似地，还可将S的任一时间表调整成为规范形式规范形式，其中及时任务先于误时任务，且及时任务依其截止时间的非减序排

3、列。问题描述理论基础 首先可将时间表调整为及时优先形式，然后再进一步调整及时任务的次序。 任务时间表问题等价于确定最优时间表中的及时任务子集A的问题。一旦确定了及时任务子集A，将A中各任务依其截止时间的非减序列出，然后再以任意次序列出误时任务，即S-A中各任务，由此产生S的一个规范的最优时间表。设AS是一个任务子集，若有一个时间表使得A中所有任务都是及时的，则称A为S的一个独立任务子集。 对时间t=1,2,3,.,n,设Nt(A)是任务子集A中所有截止时间是t或更早的任务数。考察任务子集A的独立性。理论基础引理4.6：对于S的任一任务子集A，下面的各命题是等价的。（1）任务子集A是独立子集。（

4、2）对于t=1,2,.n,Nt(A)t。（3）若A中任务依其截止时间非减序排列，则A中所有任务都是及时的。任务时间表问题要求使总误时惩罚达到最小，这等价于使任务时间表中的及时任务的惩罚值达到最大。下面的定理表明可用带权拟阵的贪心算法解任务时间表问题。理论基础定理4.7：设S是带有截止时间的单位时间任务表，I是S的所有独立任务子集构成的集合。则有序对（S,I）是拟阵。由定理4.5可知，用带权拟阵的贪心算法可以求的最大权（惩罚）独立任务子集A，以A作为最优时间表中的及时任务子集，容易构造最优时间表。 任务时间表问题的贪心算法的计算时间复杂性是O（nlogn+nf(n)）。其中f(n)是用于检测任务

5、子集A的独立性所需的时间。用引理4.6中性质(2)容易设计一个O(n)时间算法来检测任务子集的独立性。因此，整个算法的计算时间为O(n2).具体算法greedyJob可描述如下：GreedyJob算法public static int greedyJob(intd,intw,intjob) intn=d.length-1; d0=0;job0=0; intk=1;/当前任务个数 job1=1; for(inti=2;idi&(djobr!=r)r-; if(djobrr) for(intm=k;mr;m- ) jobm+1=jobm; jobr+1=i; k+; di1in,是n个单位

6、时间任务的截止时间，且n个单位时间任务已依其误时惩罚的非增序排列。wi误时惩罚jobi最优解中的第i个任务greedyJob算法例题给定单位时间任务集S及各任务的截止时间和误时惩罚如下：i1234567di4243146wi70605040302010最优时间表为最优时间表为2,4,1,3,7,5,6。总误时惩罚为。总误时惩罚为W5+W6=50，达到最小。，达到最小。i=2,r=1i=3,r=2i=4,r=3i=5,r=4i=6,r=4i=7,r=4job1job2,1job2,1,3job2,4,1,3舍弃5舍弃6job2,4,1,3,7 该方法教之前的greedyJob算法的不同之处在于如

7、何确定部分解的可行性方面，两者的度量标准不同。 其方法是：如果Job是任务的可行子集，那么可以使用下述规则来确定这些任务中的每一个任务的处理时间： 若还没给作业i 分配处理时间，则分配给它的时间片-1,其中应尽量取大且时间片-1,是空的。此规则就是尽可能推迟对任务的处理。于是，在将任务一个一个地装配到Job中时就不必为接纳新任务而去移动Job中哪些已经分配了时间片的任务。如果正被考虑的新作业不存在像上面那样定义的，这个作业就不能计入job。fasterJob算法fasterJob算法public static intfasterJob(intd,intw,intjob,ints) intn=d

8、.length-1; intf=newintn+1; for(inti=0;i=n;i+) fi=i;/初始化fi FastUnionFindU=newFastUnionFind(n);/创建并查集 intk=0,t=0; for(inti=1;i=n;i+) intm=(n0)/任务可放入及时任务中 k=k+1; jobk=i; if(fm1) t=U.Find(fm-1); U.Union(t,m);elset=0;fm=ft; for(inti=1;i=k;i+)wjobi=0;/及时任务惩罚清零intsum=0;for(inti=1;i0)job+k=i;sum+=wi; returnsum;/返回最小惩罚数算法fasterJob用到的find和union运算的次数都不超过n次。因此，如果不计预处理的时间，算法fasterJob所需的计算时间为O(nlog*n)。fasterJob算法fasterJob算法例题设N=5，wi=(20,15,10,5,1),di=(2,2,1,3,3)。使用fasterJob