作業(yè)調(diào)度貪心算法

軟件算法設(shè)計實驗報告題目：作業(yè)調(diào)度問題 院(系)：計算機科學(xué)與工程專業(yè)：班級：學(xué)生：學(xué)號： 2015年11月問題描述：n個作業(yè){1，2，…，n}要在由n臺機器M1,...,Mn完成加工作業(yè)調(diào)度問題,要求確定這n個作業(yè)的最優(yōu)加工順序，使得從第一個作業(yè)在機器，到最后一個作業(yè)在機器上加工完成所需的時間最少。算法設(shè)計：貪心算法思想：貪心選擇性質(zhì)：所謂貪心選擇性質(zhì)是指應(yīng)用同一規(guī)則f,將原問題變?yōu)橐粋€相似的。但規(guī)模更小的子問題，而后的每一步都是當(dāng)前看似最佳的選擇。這種選擇依賴于已做出的選擇，但不依賴于未作出的選擇。從全局來看，運用貪心策略解決的問題在程序中無回溯過程。局部最優(yōu)解：我們通過特點2向大家介紹了貪心策略的數(shù)學(xué)描述。由于運用貪心策略解題在每一步都取得了最優(yōu)解，但能夠保證局部最優(yōu)解的不一定是貪心算法。設(shè)7個獨立作業(yè){1,2,3,4,5,6,7}由3臺機器M1，M2和M3加工處理。各作業(yè)所需的處理時間分別為{2,14,4,16,6,5,3}。按算法greedy產(chǎn)生的作業(yè)調(diào)度如下圖所示，所需的加工時間為17。序號1234567時間214416653序號4256371時間161465432假設(shè)有三臺機器，建立最小堆程序中標(biāo)識符說明類別名稱作用類Fac4_7_1

類MinHeap最小堆類用于優(yōu)先隊列類jobNode定義作業(yè)結(jié)點（序號及加工時間）類MachineNode定義機器結(jié)點（機器號和可用時間）方法mergesort按處理作業(yè)加工時間降序排序方法greedy貪心法解多機調(diào)度問題數(shù)組a[]按作業(yè)順序填寫加工時間算法實現(xiàn):運行環(huán)境：Myeclipse8.5 javaproject2.源代碼：//基于最小堆的貪心算法解多機調(diào)度問題,//heapsortonminheapimportjava.io.*;classMinHeap{//Min-heapimpmentationstaticjobNode[]Heap;//Pointertotheheaparraystaticintsize;//Maximumsizeoftheheapstaticintn;//NumberofintentsnowinheapheapsoetpublicMinHeap(jobNode[]h,intnum,intmax)//constructor{Heap=h;n=num;size=max;buildheap();}publicintheapsize()//returncurrentsizeoftheheap{returnn;}publicstaticbooleanisLeaf(intpos)//trueifposisaleafposition{return(pos>=n/2)&&(pos<n);}publicstaticvoidAssert_notFalse(booleanp,Stringq){if(!p)System.out.println((String)q);}publicstaticintkey(int[]q,intp){returnq[p];}//returnpositionforleftchildofpospublicstaticintleftchild(intpos){Assert_notFalse(pos<n/2,"positionhasnoleftchild");return2*pos+1;}//returnpositionforrightchildofpospublicstaticintrightchild(intpos){Assert_notFalse(pos<(n-1)/2,"positionhasnorightchild");return2*pos+2;}publicstaticintparent(intpos)//returnpositionforparent{Assert_notFalse(pos>0,"positionhasnoparent");return(pos-1)/2;}publicstaticvoidbuildheap()//HeapifycontentsofHeap{for(inti=n/2-1;i>=0;i--)siftdown(i);}publicstaticvoidswap(jobNode[]q,inti,intj){jobNodetemp;temp=q[i];q[i]=q[j];q[j]=temp;}privatestaticvoidsiftdown(intpos)//putintentinitscorrentplace{Assert_notFalse((pos>=0)&&(pos<n),"illegalheapposition");while(!isLeaf(pos)){intj=leftchild(pos);if(j<(n-1)&&Heap[j].key()>Heap[j+1].key())j++;//jisnowindexofchildwithgreatervalueif(Heap[pos].key()<=Heap[j].key())return;//Doneswap(Heap,pos,j);pos=j;}//Movedown}publicstaticvoidinsert(jobNodeval)//Insertvalueintoheap{Assert_notFalse(n<size,"Heapisfull");intcurr=n++;Heap[curr]=val;//starttendofheap//Nowsiftupuntilcurr'sparent'skey<curr'skeywhile(curr!=0&&Heap[curr].key()<Heap[parent(curr)].key()){swap(Heap,curr,parent(curr));curr=parent(curr);}}publicstaticjobNoderemovemin()//removeminimumvalue{Assert_notFalse(n>0,"Removingfromemptyheap");swap(Heap,0,--n);//swapminimumwithlastvalueif(n!=0)//Notonlastintentsiftdown(0);//PutnewheaprootvalincorrentplacereturnHeap[n];}//RemoveintentatspecifiedpositionpublicstaticjobNoderemove(intpos){Assert_notFalse((pos>0)&&(pos<n),"illegalheapposition");swap(Heap,pos,--n);//swapwithlastvalueif(n!=0)//Notonlastintentsiftdown(pos);//putnewheaprootvalincorrentplacereturnHeap[n];}publicstaticvoidoutMinHeap(){for(inti=0;i<=n-1;i++)System.out.print(Heap[i].time+"");System.out.println();}staticvoidheapsort()//heapsort{System.out.println("建最小堆之后排序");for(inti=1;i<size-1;i++)//nowsortSystem.out.print(removemin()+"");System.out.println();//removeminplacesminvalueatendofheap}}//classMinHeapclassjobNodeimplementsComparable{intid;inttime;jobNode(inti,inttt){id=i;time=tt;}publicintcompareTo(Objectx){intxt=((jobNode)x).time;if(time<xt)return-1;if(time==xt)return0;return1;}publicintkey(){returntime;}}publicclassFac4_7_1{publicstaticvoidmergeSort(jobNode[]a,intleft,intright){jobNode[]b=newjobNode[a.length];if(left<right){inti=(left+right)/2;mergeSort(a,left,i);mergeSort(a,i+1,right);merge(a,b,left,i,right);copy(a,b,left,right);}}publicstaticvoidcopy(jobNode[]a,jobNode[]b,inti,intj){for(intk=i;k<=j;k++)a[k]=b[k];}publicstaticvoidmerge(jobNode[]c,jobNode[]d,intl,intm,intr){//合并c[l:m]和c[m+1:r]到d[l:m]inti=l,j=m+1,k=l;while((i<=m)&&(j<=r))if(c[i].time-c[j].time>0)d[k++]=c[i++];elsed[k++]=c[j++];if(i>m)for(intq=j;q<=r;q++)d[k++]=c[q];elsefor(intq=i;q<=m;q++)d[k++]=c[q];}publicstaticvoidmain(Stringargs[]){intm1=0,m=3;inta[]={2,14,4,16,6,5,3};intn1=a.length-1;intsum=0;if(n1<m){for(inti=0;i<=n1;i++)if(sum<a[i])sum=a[i];System.out.println("為每個作業(yè)分配一臺機器,最長時間為");System.out.println(sum);}else{jobNode[]d=newjobNode[n1+1];for(inti=0;i<=n1;i++)d[i]=newjobNode(i,a[i]);mergeSort(d,m1,n1);MinHeapabc=newMinHeap(d,m1,3);for(inti=m1;i<m;i++){jobNodex1=d[i];abc.insert(x1);