作业调度贪心算法讲述.doc

软件算法设计 实验报告 题目：作业调度问题 院(系)： 计算机科学与工程 专 业： 班 级： 学 生： 学 号： 2015年 11 月 问题描述： n个作业{1，2，…，n}要在由n台机器M1,...,Mn完成加工作业调度问题,要求确定这n个作业的最优加工顺序，使得从第一个作业在机器，到最后一个作业在机器上加工完成所需的时间最少。 算法设计： 贪心算法思想： 贪心选择性质： 所谓贪心选择性质是指应用同一规则f,将原问题变为一个相似的。但规模更小的子问题，而后的每一步都是当前看似最佳的选择。这种选择依赖于已做出的选择，但不依赖于未作出的选择。从全局来看，运用贪心策略解决的问题在程序中无回溯过程。 局部最优解： 我们通过特点2向大家介绍了贪心策略的数学描述。由于运用贪心策略解题在每一步都取得了最优解，但能够保证局部最优解的不一定是贪心算法。 设7个独立作业{1,2,3,4,5,6,7}由3台机器M1，M2和M3加工处理。各作业所需的处理时间分别为{2,14,4,16,6,5,3}。按算法greedy产生的作业调度如下图所示，所需的加工时间为17。 序号1234567时间214416653 序号4256371时间161465432假设有三台机器，建立最小堆 程序中标识符说明 类别名称作用类Fac4_7_1?类MinHeap最小堆类用于优先队列类jobNode 定义作业结点（序号及加工时间）类MachineNode定义机器结点（机器号和可用时间）方法mergesort按处理作业加工时间降序排序方法greedy贪心法解多机调度问题数组a[]按作业顺序填写加工时间 算法实现: 运行环境： Myeclipse 8.5 java project 2.源代码： //基于最小堆的贪心算法解多机调度问题, //heapsort on minheap import java.io.*; class MinHeap { //Min-heap impmentation static jobNode[] Heap; //Pointer to the heap array static int size; //Maximum size of the heap static int n; //Number of intents now in heapheapsoet public MinHeap(jobNode[] h,int num,int max)//constructor { Heap=h;n=num;size=max;buildheap();} public int heapsize()//return current size of the heap { return n;} public static boolean isLeaf(int pos)//true if pos is a leaf position { return(pos=n/2)(posn);} public static void Assert_notFalse(boolean p,String q) {if(!p)System.out.println((String)q);} public static int key( int [] q,int p) { return q[p];} //return position for left child of pos public static int leftchild(int pos) { Assert_notFalse(posn/2,position has no left child); return 2*pos+1; } //return position for right child of pos public static int rightchild(int pos) {Assert_notFalse(pos(n-1)/2,position has