算法导论之贪心算法：带惩罚的任务调度算法

旧城等待， 2022-08-23 00:57 166阅读 0赞

**带惩罚的任务调度问题**：

单处理器上带截止时间和惩罚的单位时间任务调度问题有以下输入：

1、n个单位时间任务的集合S=\{a1,a2,……,an\}；

2、n个整数截止时间d1,d2,……,dn，每个di满足1<=di<=n，我们期望任务ai在时间di之前完成。

3、n个非负权重或者惩罚w1,w2,……,wn，若任务ai在时间di之前没有完成，我们就会受到wi这么多的惩罚，如果任务在截止时间之前完成，则不会受到惩罚。

（单位时间任务是严格需要一个时间单位来完成的作业）

在算法中我们定义**延迟**：如果方案中一个任务在截止时间后完成。都则就是**提前**。

**提前优先形式**：将提前的任务都置于延迟任务之前。

**调度方案有规范形式**：提前任务都在延迟任务之前，且提前任务按截止时间单调递增的顺序排列。

**代码实现**如下：

package cc.wsyw126.algorithms;
    
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.Collections;
    import java.util.Comparator;
    import java.util.List;
    
    /*
     问题描述：
     在单处理器上具有期限和惩罚的单位时间任务调度问题（课本P239）
     实验要求：
     （1）实现这个问题的贪心算法
     （2）将每个wi 替换为 max{w1,w2,...,wn}-wi，运行算法比较结果
     */
    
    /** * @author WSYW126 * @version 创建时间：2016年6月4日 下午8:29:32 类说明：Alljava */ public class TaskSchedul {
        private List<Task>       tasks        = null; // 所有任务
        private List<Task>       earlyTasks   = null; // 早任务
        private List<Task>       lateTasks    = null; // 晚任务
        private Comparator<Task> comparator_d = null;
        private Comparator<Task> comparator_w = null;
    
        public static void main(String[] args) {
            //int[] d = {4, 2, 4, 3, 1, 4, 6}; // 各个任务的deadline
            //int[] w = {70, 60, 50, 40, 30, 20, 10}; // 各个任务的惩罚
    
            int[] d = {
      5, 3, 1, 4, 6, 4, 2, 2}; // 各个任务的deadline
            int[] w = {
      60, 70, 40, 50, 10, 30, 20, 5}; // 各个任务的惩罚
    
            TaskSchedul ts = new TaskSchedul(d, w);
            ts.scheduleTask(); // 任务调度
            ts.printList(); // 输出信息
            System.out.println("----------------------------用max{w1,12,...,wn}-wi替换后的结果-----------------------------");
            ts.rescheduleTask(); // 用max{w1,12,...,wn}-wi替换wi后，任务调度
            ts.printList(); // 输出信息
        }
    
        public void rescheduleTask() { // 用max{w1,12,...,wn}-wi替换wi
            int max = tasks.get(0).getWeight(); // 在init()函数中已经将tasks中的任务按惩罚大小降序排序
            for (Task task : tasks) {
                task.setWeight(max - task.getWeight());
            }
            System.out.print("任务集为：");
            for (Task task : tasks) {
                System.out.print("a" + (task.getId() + 1) + "(d:"
                        + task.getDeadLine() + ",w:" + task.getWeight() + ") ");
            }
            System.out.println();
            Collections.sort(tasks, comparator_w); // 将任务按惩罚大小降序排序
            earlyTasks = new ArrayList<Task>();
            lateTasks = new ArrayList<Task>();
            scheduleTask();
        }
    
        public void scheduleTask() { // 时间复杂度为O(n^2)
            int n = tasks.size();
            int[] NA = new int[n]; // 标记，用来判断任务集是否独立
            int[] count = new int[n]; // 标记，ai之前，截止时间小于ai的个数
            Arrays.fill(count, 0);
            for (int i = 0; i < n; i++) { // NA[0..n-1];
                NA[i] = 0;
            }
            for (int i = 0; i < n && NA[i] == 0; i++) {
                int flag = count[i] + 1;
                Task task = tasks.get(i);
                for (int j = i + 1; j < n; j++) {
                    if (NA[i] != 0 || NA[j] != 0) continue;
                    Task temp = tasks.get(j);
                    if (task.getDeadLine() >= temp.getDeadLine()) {
                        flag++;
                        if (flag > task.getDeadLine()) {
                            lateTasks.add(temp);
                            NA[j] = 1;
                        }
                    }
                    if (task.getDeadLine() <= temp.getDeadLine()) {
                        count[j] = count[j] + 1;
                    }
                }
            }
            for (int i = 0; i < n; i++) {
                if (NA[i] == 0) {
                    earlyTasks.add(tasks.get(i));
                }
            }
            Collections.sort(earlyTasks, comparator_d);
        }
    
        public TaskSchedul(int[] d, int[] w) {
            initComparator();
            init(d, w);
        }
    
        public void init(int[] d, int[] w) { // 导入初始任务
            tasks = new ArrayList<Task>();
            earlyTasks = new ArrayList<Task>();
            lateTasks = new ArrayList<Task>();
            int n = d.length;
            for (int i = 0; i < n; i++) {
                Task t = new Task();
                t.setId(i);
                t.setDeadLine(d[i]);
                t.setWeight(w[i]);
                tasks.add(t);
            }
            System.out.print("任务集为：");
            for (Task task : tasks) {
                System.out.print("a" + (task.getId() + 1) + "(d:"
                        + task.getDeadLine() + ",w:" + task.getWeight() + ") ");
            }
            System.out.println();
            Collections.sort(tasks, comparator_w); // 将任务按惩罚大小降序排序
        }
    
        public void initComparator() {
            comparator_d = new Comparator<Task>() { // 按deadline升序排列任务
                public int compare(Task t1, Task t2) {
                    if (t1.getDeadLine() > t2.getDeadLine()) {
                        return 1;
                    } else if (t1.getDeadLine() == t2.getDeadLine()) {
                        return 0;
                    } else {
                        return -1;
                    }
                }
            };
            comparator_w = new Comparator<Task>() { // 按(惩罚)w降序排列任务
                public int compare(Task t1, Task t2) {
                    if (t2.getWeight() > t1.getWeight()) {
                        return 1;
                    } else if (t2.getWeight() == t1.getWeight()) {
                        return 0;
                    } else {
                        return -1;
                    }
                }
            };
        }
    
        public void printList() {
            int punish = 0;
            System.out.print("贪心算法选择任务为：");
            for (Task t : earlyTasks) {
                System.out.print("a" + (t.getId() + 1) + " ");
            }
            System.out.print("\n被惩罚任务为：");
            for (Task t : lateTasks) {
                System.out.print("a" + (t.getId() + 1) + " ");
            }
            System.out.print("\n总的惩罚数为：");
            for (Task t : lateTasks) {
                punish += t.getWeight();
            }
            System.out.println(punish + "");
        }
    }
    
    class Task { // 任务定义
        private int id;
        private int deadLine;
        private int weight;
    
        public int getId() {
            return id;
        }
    
        public void setId(int id) {
            this.id = id;
        }
    
        public int getDeadLine() {
            return deadLine;
        }
    
        public void setDeadLine(int deadLine) {
            this.deadLine = deadLine;
        }
    
        public int getWeight() {
            return weight;
        }
    
        public void setWeight(int weight) {
            this.weight = weight;
        }
    }

**时间复杂度分析**：

在上面的过程中，我们使用scheduleTask函数，它的时间复杂度为O(n^2)。

因此由scheduleTask决定我们的算法的时间复杂度为O(n^2)。

**参考资料**：  
算法导论  
  
**备注**：  
转载请注明出处：http://blog.csdn.net/wsyw126/article/details/51586443  
作者：WSYW12