带有限期的作业排序带有限期的作业排序 问题的描述： 带有期限的作业排序要解决的是操作系统中单机、无资源约束且每个作业可在等量的时间内完成的作业调度问题。把这个问题形式化描述为： ① 要在一台机器上处理 n 个作业，每个作业可以在单位时间内完成 ②每个作业 i 都有一个期限值 di，di>0 ③ 当作业在它规定的期限值前完成，就可以获得的效益 pi，pi>0 问题求解的目标是：问题的可行解是这 n 个作业的一个子集合 J。J 中的每个作业都能在各自的截止期限前完成后，产生一个作业效益之和 。我们的目标就是找到一个子集 J，J 中的每个作业都能在各 自的截止期限前完成，并且使得作业效益值的和最大。这个作业的一个子集合 J 就是所求的最优解。 带有期限的作业排序的一个例子： 例 3.2 n=4，(p1,p2,p3,p4)=(100,10,15,20)，(d1,d2,d3,d4)=(2,1,2,1)。这个问题的最优解为第 7 个，所允许的处理顺序是：先处理作业 4，在处理作业 1。在时间 0 开始处理作业 4 而在时间 2 完成对作业1 的处理。 可行解 处理顺序 效益值 1 {1} 1 100 2 {2} 2 10 3 {3} 3 15 4 {4} 4 20 5 {1，2} 2，1 110 6 {1，3} 1，3 或 3，1 115 7 {1，4} 4，1 120 8 {2，3} 2，3 25 9 {3，4} 4，3 35 带有期限的作业排序贪心算法度量标准的选取： 我们的目标是作业效益值的和最大，因此首先把目标函数作为度量标准。首先把作业根据它们的效益值作一个非增次序的排序。以例 3.2 来说，作业根据效益值排序后为作业 1、4、3、2。求解时首先把作业 1 计入 J，由于作业 1 的期限值是 2，所以 J={1}是一个可行解。接下来计入作业 4。由于作业 4 的期限值是 1 而作业 1 的期限值是 2，可以先完成作业 4 后再完成作业 1，所以 J={1, 4}是一个可行的解。然后考虑作业 3，但是作业 3 的期限值是 2，计入 J 后就没有办法保证 J 中的每一个作业都在期限值内完成，因此计入作业 3 后不能构成一个可行解。同理计入 2 后也不能构成一个可行解。由分析可知，把目标函数作为度量标准能够得到问题的最优解。 作业排序算法的概略描述： 算法 3.3 procedure GREEDY-JOB(D,J,n) //作业根据 p1≥p2≥…≥pn 的次序输入，它们的期限值 D(i) ≥1, 1≤i≤n, n≥1。J 是在它们的截止期限前完成的作业集合。 J←{1} For i←2 to n do If J∪{i}的所有作业都能...
