含关系。这是因为算法 Greedy Job的特性和假定I产生的效益值比J 的效益值更大。假设a是J中具有最大效益的作业,于是,J中比 a具有更多效益的作业都应该在I中。对于任何元素b∈IJ,我们有 pa≥pb。否则,由p^pb可推出b∈J,因为按照算法 GreedyJob,b将先 于a被考虑是否该加入J中。而J中那些效益比a效益大的作业也允 许将b加入J,因为它们在I中是相容的。 如果用S1和S分别记对应于I和J的调度表,并且i∈I∩J,i项 作业在S和S1中分别属于时间段t,t1和t,t+1]。若t<t',则在S 中将i项作业与S1在时间段[t,t+1]内排序的作业(如果有的化)交 换,这样得到的调度表S还是相容的。同样讨论tt'情形。由此,我 们可以假设I∩J中作业在S1和S中有相同的排序时间表。现在假设 排序时间表S中,作业a被安排在时间片[ta,t+中。则排序时间表 S1一定有某个作业b∈Ⅳ被安排在时间片[ta,ta+1]中。不然,在排序表 S1中,时间片[ta,t+1空闲,将作业a安排在这个时间片调度,将会 得到效益值更大的相容作业子集,这与Ⅰ的假设矛盾。现在,将S1 中的时间片[ta,t+1]换成调度作业a,则得到新的相容作业集合 I'=(Ⅳ{b}){a}。显然I的效益值不低于I的效益值,但I⌒J比I⌒J 的元素至少少一个,与前面的假设矛盾。证毕 在上述算法中,每次新的作业i填入之前,都要做一次判断,实 际上是检查在[0,1]12,……,[f1,f中是否还有空闲的时间片?若有, 则选择其中之一安排作业i;否则,作业i将被搁置。实现的方法有 两种。含关系。这是因为算法 GreedyJob 的特性和假定 I 产生的效益值比 J 的效益值更大。 假设 a 是 J\I 中具有最大效益的作业，于是，J 中比 a 具有更多效益的作业都应该在 I 中。对于任何元素 b∈I\J，我们有 pa≥pb。否则，由 pa<pb可推出 b∈J，因为按照算法 GreedyJob，b 将先 于 a 被考虑是否该加入 J 中。而 J 中那些效益比 a 效益大的作业也允 许将 b 加入 J，因为它们在 I 中是相容的。 如果用 SI和 SJ分别记对应于 I 和 J 的调度表，并且 i∈I ∩ J，i 项 作业在 SJ和 SI中分别属于时间段[t, t+1]和[t’, t’+1]。若 t<t’，则在 SJ 中将 i 项作业与 SJ在时间段[t’, t’+1]内排序的作业（如果有的化）交 换，这样得到的调度表 SJ’还是相容的。同样讨论 t>t’情形。由此，我 们可以假设 I ∩ J 中作业在 SI和 SJ中有相同的排序时间表。现在假设 排序时间表 SJ中，作业 a 被安排在时间片[ta, ta+1]中。则排序时间表 SI一定有某个作业 b∈I\J 被安排在时间片[ta, ta+1]中。不然，在排序表 SI中，时间片[ta, ta+1]空闲，将作业 a 安排在这个时间片调度，将会 得到效益值更大的相容作业子集，这与 I 的假设矛盾。现在，将 SI 中的时间片[ta, ta+1]换成调度作业 a，则得到新的相容作业集合 I’=(I\{b})∪{a}。显然 I’的效益值不低于 I 的效益值，但 I’ ∩ J 比 I ∩ J 的元素至少少一个，与前面的假设矛盾。 证毕 在上述算法中，每次新的作业 i 填入之前，都要做一次判断，实 际上是检查在[0,1],[1,2], ⋅⋅⋅⋅⋅，[fi-1,fi]中是否还有空闲的时间片？若有， 则选择其中之一安排作业 i；否则，作业 i 将被搁置。实现的方法有 两种