2010-2011 第二学期08通信专业期末考查带期限的作业调度问题的算法与实现班级08通信一班学号14082300943姓名张博成绩分一、设计目的1.掌握分枝-限界法算法的解题的基本思想和设计方法;2.理解分枝-限界法算法中的限界函数应遵循正确，准确，高效的设计原则;3.掌握先进先出分枝-限界算法思想（FIFOBB）解决带期限作业调度问题。

二、设计内容1.任务描述给定一个带期限的作业排序问题, n=5, (p1,p2,p3,p4,p5)=(6,3,4,8,5),(t1,t2,t3,t4,t5)=(2,1,2,1,1), (d 1,d2,d3,d4,d5)= (3,1,4,2,4), 应用FIFOBB求使总罚款数最小的可行作业集J, 要求:1）阐述c’(X)和u(X)的设计思路，U的初始值;2）针对解向量变长格式, 画出FIFOBB的生成的部分状态空间树, 按活节点生成顺序给节点编号，在各节点位置给出c’(X)和U的值，给每条边标记选择的作业编号;3）阐述c’(X)=U的处理方案, 可行解的判断方案；4）阐述你程序中的主要数据类型、数据变量和功能模块。

5）、编成并上机实现FIFOBB程序, 实现对不同作业排序问题实例的求解，问题实例的输入数据存储在case.txt文件中，其格式为：第一行问题规模（最多10个作业）第二行各作业的罚款数，数据项之间用一个空格分隔第三行各作业的截止期限，数据项之间用一个空格分隔第四行各作业所需的运行时间，数据项之间用一个空格分隔例如：45 106 31 32 11 2 1 1从屏幕直接输出最优作业集的序号，数据项之间用逗号分隔。

三、设计思路1.几个关键数据的处理1)c'的设计思路是总共结点总成本减去当前结点的成本再减去其最小成本上界的成本。

2)在处理计算最小成本上界时，我利用了一个数组binGroup2，给它初始化为{1,1,1,1,1}，设计每个结点结构体都有一个这样的数组，每个结点做了那个作业就把对应作业的二进制数制为0；在计算最小估计成本上界时就将这个数组乘以结点成本数组，然后循环求和。

3)c’(X)=U的处理方案：U取初值一个很大的2.状态空间树： 方框：椭圆表示结点； 作业：1 2 3 4 5 六边形表示死结点。

作业：2 3 4 5 3 4 5 4 5 5作业：3 4 5 4 5 5 4 5 5 5作业：51 11 10 9 8 7 12 6 5 43 2 1615 14 13 1922 23 24 26 25估计成本： 最小上界： 17,1718,18 21， 21 13，189，22 6， 23 0，267,12 3， 16 0， 17 13，1315， 15 9,1410,15 6, 19 0，20 12，127， 7 6, 1114，1410，106, 1117 2721 20183.主要数据类型与变量Int max;//罚款总数int cost[5]={6,3,4,8,5};//罚款int timeconsumer[5]={2,1,2,1,1};//所用时间int declitime[5]={3,1,4,2,4};//截止期限#define e 0.1Int U;//存放最小成本typedef struct aa{int parent;//父亲结点int x;//表示节点所做的任务几int binGroup1[4]={0,0,0,0,0};//记录做了的作业，把做了的作业记为1int binGroup2[5]={1,1,1,1,1};//记录没有做的作业，把做了的作业记为0int time;//记录耗时总和int maycost;//估计成本float mincost;//最小成本上界} ELEM;//节点当前任务，日期，估计成本，最小上界成本ELEM Node[N];//存放活结点数组4.算法或程序模块int maycost(Elemt X) 功能：计算估计成本maycost函数int Mincost(int x[5],int y[5]) 功能：计算最小上界mincost成本，即二进制数组2乘以成本数组int comparetime(int x[5],int y[5],int z[5]) 功能:计算总耗时间与最大截止期限做比较void entergroup(int w,int E) 功能：活结点进队列int outgroup(int E) 功能：活结点出队列void BB(int T) 功能：在所有的结点中寻找最小成本四、测试1.方案建立一个文本文档case.txt与程序放在同一个文件目录下。

在里面写入：45 106 31 32 11 2 1 12.结果理论结果是作业1,4,5，作用最小罚款数是7。

五、讨论与总结讨论1.在处理计算最小成本上界时，我利用了一个数组binGroup2，给它初始化为{1,1,1,1,1}，设计每个结点结构体都有一个这样的数组，每个结点做了那个作业就把对应作业的二进制数制为0；在计算最小估计成本上界时就将这个数组乘以结点成本数组，然后循环求和。

2.判断当前结点是否是解结点时，在比较当前结点总用时间与已做结点中的最大结点时间期限时，我也利用了上面讲到的数值binGroup1，处理方法是类似的。

若当前结点总用时间小于已做结点中的最大结点时间期限，则该结点不是解结点，反之则为解结点。

3.活结的进站，与出站，我同样是利用了数组，但是定义了两个标号。

x1指向了活结点数组开头，x2指向了活结点数组末尾。

活结点进站是x2加1，出站是x1加1，当x1=x2时候结点就出站完毕。

总结通过此次期末课程设计，我对分枝限界算法比书本上的认识有了更加深刻的理解。

本课程设计中在寻找最小罚款值时，定义了一个估计成本和最小成本上界，而答案成本就在它们中间。

是的，这样的做法，大大提高了程序的效率，减少的程序的盲目性。

其中，通过比较估计成本来判断结点是否可以进活结点队列，同时在队列中的结点又可以通过比较结点的最小成本上界来判断该节点是否需要继续执行下去。

在深刻体会到分枝限界算法的优越性的同时，在自己动手的程序设计中，我锻炼了自己的程序思维，通过上面所讲的利用数字处理问题的思路中，我明白实现一个程序的路子是不同的，假如直直的走不同，我们就可以在其它的角度去思考解决的办法。

当然编程时耐人的事，调试程序的时候有可能会把一个人的耐心磨掉。

因此，我们编程的时候应该要带着兴趣，带着不达目的誓不罢休的学习态度。

当我们全心全意的投入到我们的程序学习中，我们会大收获的。

不信的话，你可以试试！附：程序模块的源代码#include <stdio.h>#define N 100#define NUll 0x7fffffff#define max 26int cost[5]={6,3,4,8,5};//罚款int timeconsumer[5]={2,1,2,1,1};//所用时间int declitime[5]={3,1,4,2,4};//截止期限#define e 0.1;int E,Z,U,ans,x1=0,x2=0;typedef struct{ int parent;int x;//表示节点所做的任务几int binGroup1[4]={0,0,0,0,0};//记录做了的作业，把做了的作业记为1int binGroup2[5]={1,1,1,1,1};//记录没有做的作业，把做了的作业记为0int time;//记录耗时总和int maycost;//估计成本float mincost;//最小成本上界}ELEM;//节点当前任务，日期，估计成本，最小上界成本ELEM Node[N];int Maycost(Elemt X){if(!isOK(X)) return NULL;maycost=max-cost[X.x]-X.mincost;}int Mincost(int x[5],int y[5])//计算最小上界mincost成本，即二进制数组2乘以成本数组{int i,t=0; for(i=0;i<5;i++) t=t+x[i]*y[i]; return t;}int comparetime(int x[5],int y[5],int z[5])//计算总耗时间与最大截止期限做比较{int a,i,t=0,;for(i=0;i<5;t++) t=t+x[i]*y[i];//求出已经做的作业的总用时间for(i=0;i<5;i++) z[i]=z[i]*x[i];//把已经做了的作业显示出来，没有做的为0a=z[0];for(i=0;i<4;i++) if(a<z[i+1]) a=z[i+1];//找出已经做的作业的最大截止期限if(t<=a) return 1;else return 0;}void entergroup(int w,int E)//活结点进队列{x1++; Node[x1].x=w;Node[x1].binGroup1[5]=Node[E].binGroup1[5];Node[x1].binGroup2[5]=Node[E].binGroup2[5];Node[x1].time=Node[E].time;Node[x1].maycost=Node[E].maycost;Node[x1].mincost=Node[E].cost;}int outgroup(int E)//活结点出队列{x2++;E=x2;return E;}void BB(int T){E=T;Z=comparetime(timeconsumer[5],Node[E].binGroup1[5],declitime[5])if(Z=0){if(Node[E].maycost>(Node.mincost[E]+e))U=Node.mincost+e;elseU=Node.maycost;ans=T;}else{U=Node.mincost+e;ans=NUll;}x1=0;x2=0;//指向链表的标号for(i=Node[E].x+1;Node[E].x+1<5;(Node[E].x+1)++)//求解当前{ Node.binGroup1[Node[E].x]=1;Node.binGroup2[Node[E].x]=0;Node.time=Node.time+timeconsumer[Node[E].x];Node.maycost=Maycost(E);Node.mincost=Mincost(cost[5],Node.binGroup2[5]);}while(1){for(i=Node[E].x+1;Node[E].x+1<5;i++)if(Node.maycost<U){entgroup(Node[E].x,E);Node[i].parent=E;Z=comparetime(timeconsumer[5],Node[i].binGroup1[5],declitime[5]);if((Z=0)&&(Node[i].maycost<U)){if(Node[i].maycost>(Node[i].mincost+e))U=Node.mincost;else U=Node.maycost;ans=i;}else if((Node[i].mincost+e)<U)U=(Node[i].mincost+e);}while(1){if(x1=x2) printf("最小罚款数为=%d\n",U);while(ans!=0) { printf("%d ",ans);E=E.parent; return;}else outgroup(E);if(Node(E).maycost<U) break;} }void main(){Node[0]={{0},{0},{0,0,0,0,0},{1,1,1,1,1},{0},{0},{26}};//结点初始化freopen("case.txt","r",stdin);scanf("%d",&n);U=0;for(i=1;i<=n;i++){scanf("%d", &cost[i]);U +=p[i];}for(i=1;i<=n;i++)scanf("%d",&timeconsumer[i]);for(i = 1; i <= n;i++)scanf("%d",&declitime[i]);BB(0);}。