最佳调度问题.docx

《最佳调度问题.docx》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验八：分支限界法最佳调度问题一、实验目的与要求1、掌握最佳调度问题的算法；2、初步掌握分支限界法二、实验题： 问题描述：假设有n个任务由k个可并行工作的机器完成。完成任务i需要的时间为ti。试设计一个算法找出完成这n个任务的最佳调度，使得完成全部任务的时间最早。#include#includeusingnamespacestd;classMinHeapNode{friendclassFlowshop;public:booloperator<(constMinHeapNode&a)const{returna.bb

2、(int);voidNewNode(MinHeapNode,int,int,int,int);ints;//已安排作业数intf1;//机器1上最后完成时间intf2;//机器2上最后完成时间intsf2;//当前机器2上的完成时间和intbb;//当前完成时间和下界int*x;//当前作业调度};voidMinHeapNode::Init(intn){//最小堆结点初始化x=newint[n];for(inti=0;i

3、intEf2,intEbb,intn){//最小堆新结点x=newint[n];for(inti=0;i

4、ntbestc;bool**y;};Flowshop::Flowshop(intn){//M=newint*[n];b=newint*[n];a=newint*[n];y=newbool*[n];bestx=newint[n];bestc=10000;for(inti=0;i

5、e[]y[i];}deletebestx,M,b,a,y;}voidFlowshop::Sort(){//对各作业在机器1和2上所需时间进行冒泡排序int*c=newint[n];for(intj=0;j<2;j++){for(inti=0;ii;k--)if(b[k][j]

6、;}intFlowshop::Bound(MinHeapNodeE,int&f1,int&f2,bool**y){//计算完成时间和下界for(intk=0;kE.f2)?f1:E.f2)+M[E.x[E.s]][1];intsf2=E.sf2+f2;ints1=0,s2=0,k1=n-E.s,k2=n-E.s,f3=f2;//计算s1的值

7、for(intj=0;jf1+b[j][0])?f2:f1+b[j][0];s1+=f1+k1*b[j][0];}//计算s2的值for(j=0;js2)?s1:s2);}int