软件算法设计
实验报告
题目:作业调度问题
院(系):计算机科学与工程
专业:
班级:
学生:
学号:
2015年11 月
问题描述:
n个作业{1,2,…,n}要在由n台机器M1,...,Mn完成加工作业调度问题,要求确定这n个作业的最优加工顺序,使得从第一个作业在机器,到最后一个作业在机器上加工完成所需的时间最少。
算法设计:
贪心算法思想:
1.贪心选择性质:
所谓贪心选择性质是指应用同一规则f,将原问题变为一个相似的。但规模更小的子问题,而后的每一步都是当前看似最佳的选择。这种选择依赖于已做出的选择,但不依赖于未作出的选择。从全局来看,运用贪心策略解决的问题在程序中无回溯过程。
2.局部最优解:
我们通过特点2向大家介绍了贪心策略的数学描述。由于运用贪心策略解题在每一步都取得了最优解,但能够保证局部最优解的不一定是贪心算法。设7个独立作业{1,2,3,4,5,6,7}由3台机器M1,M2和M3加工处理。各作业所需的处理时间分别为{2,14,4,16,6,5,3}。按算法greedy产生的作业调度如下图所示,所需的加工时间为17。
算法实现:
1.运行环境:
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)&&(pos 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(pos 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 no right child"); return 2*pos+2; } public static int parent(int pos)//return position for parent {Assert_notFalse(pos>0,"position has no parent"); return (pos-1)/2; } public static void buildheap() //Heapify contents of Heap { for(int i=n/2-1;i>=0;i--)siftdown(i);} public static void swap(jobNode[] q,int i,int j) { jobNode temp; temp=q[i];q[i]=q[j];q[j]=temp;} private static void siftdown(int pos) //put intent in itscorrent place {Assert_notFalse((pos>=0) && (pos while(! isLeaf(pos)) { int j=leftchild(pos); if(j<(n-1)&&Heap[j].key()>Heap[j+1].key()) j++;// j is now index of child with greater value if(Heap[pos].key()<=Heap[j].key()) return;// Done swap(Heap,pos,j); pos=j; } //Move down } public static void insert(jobNode val) //Insert value into heap { Assert_notFalse(n int curr=n++; Heap[curr]=val; //start t end of heap //Now sift up until curr's parent's key while(curr!=0 && Heap[curr].key() { swap(Heap,curr,parent(curr)); curr=parent(curr); } } public static jobNode removemin() //remove minimum value { Assert_notFalse(n>0,"Removing from empty heap "); swap(Heap,0,--n);//swap minimum with last value if(n!=0) //Not on last intent siftdown(0); //Put new heap root val in corrent place return Heap[n]; } //Remove intent at specified position public static jobNode remove(int pos) {