带期限的作业调度问题的算法与实现

《带期限的作业调度问题的算法与实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、2010-2011第二学期08通信专业期末考查带期限的作业调度问题的算法与实现班级08通信一班学号14082300943_姓名张博成绩一、设计目的1.掌握分枝-限界法算法的解题的基本思想和设计方法；2.理解分枝-限界法算法中的限界函数应遵循正确，准确，高效的设计原则；3.掌握先进先出分枝-限界算法思想(FTF0BB)解决带期限作业调度fu)题。二、设计内容1.任务描述给定一个带期限的作业排序问题，n=5,(pi,p2,p3,p4,p5)=(6,3,4,8,5),(tl,t2,t3,t4,t5)=(2,1,2,1,1),(d1,d2,d3,d4,d

2、5)=(3,1,4,2,4),应用FIFOBB求使总罚款数最小的可行作业集J,要求：1)阐述c’(X)和u(X)的设计思路，U的初始值；2)针对解向量变长格式，M出HF0BB的生成的部分状态空间树，按活节点生成顺序给节点编号，在各节点位置给出c’(X)和U的值，给每条边标记选择的作业编号；3)阐述c’(X)=U的处理方案，可行解的判断方案；4)阐述你程序中的主要数据类型、数据变量和功能模块。5)、编成并上机实现HF0BB程序，实现对不同作业排序问题实例的求解，问题实例的输入数据存储在case,txt文件中，其格式为：第一行问题规模(最多10个作业

3、)第二行各作业的罚款数，数据项之间用一个空格分隔第三行各作业的截止期限，数据项之间用一个空格分隔第四行各作业所需的运行时间，数据项之间用一个空格分隔例如：45106313211211从屏幕直接输出最优作业集的序号，数据项之间用逗号分隔。三、设计思路1.几个关键数据的处理1)c’的设汁思路是总共结点总成本减去当前结点的成本再减去其®小成本上界的成本。2)在处理计算最小成本上界时，我利用了一个数组binGr0Up2,给它初始化为｛1，1,1,1，1｝，设计每个结点结构体都有一个这样的数组，每个结点做了那个作业就把对应作业的二进制数制为0；在计算S小估

4、计成本上界时就将这个数组乘以结点成本数组，然后循环求和。3)c’(X)=U的处理方案：U取初值一个很大的273.主要数据类型与变量Intmax;//罚款总数int0031;[5]={6,3,4,8,5};//罚款inttimeconsumer[5]={2,1,2,1,1};//所用时间intdeciitime[5]={3,1,4,2,4};//截止期限#definee0.1IntU;//存放最小成木typedefstructaa{intparent;//父亲结点intx;//表示节点所做的任务几intbinGroupl[4]={0,0,0,0,0

5、};//记录做了的作业，把做了的作业记为1intbinGrOUp2[5]={l，l，1,1,1};//记录没有做的作业，把做了的作业记为0inttime;//记录轾时总和intmaycost;//估计成本floatmincost;//最小成本上芥}ELEM;//节点当前任务，日期，估计成本，S小上界成本ELEMNode[N];//存放活结点数组4.算法或程序模块intmaycost(ElemtX)功能:计算估计成本maycost函数intMincost(intx[5],inty[5])功能：计算最小上界mincost成本，即二进制数姐2乘以成本数

6、组intcomparetime(intx[5]，inty[5],intz[5])功能:计算总耗时间与最大截止期限做比较voidentergroup(intw,intE)功能:活结点进队列intoutgroup(intE)功能：活结点出队列voidBB(intT)功能：在所有的结点中寻找最小成本四、测试1.方案建立一个文本文I当case,txt与程序放在同一个文件R录下。在里而写入：451063132112111.结果理论结果是作业1,4,5,作用最小罚款数是7五、讨论与总结讨论1.在处理计算最小成本上界时，我利用了一个数组binGr0Up2,给它

7、初始化为{1,1,1,1,1},设计每个结点结构体都有一个这样的数组，每个结点做了那个作业就把对应作业的二进制数制为0;在计算S小估计成本上界时就将这个数组乘以结点成本数组，然后循环求和。2.判断当前结点是否是解结点时，在比较当前结点总用时间与己做结点屮的最大结点时间期限时，我也利用了上面讲到的数值binGroupl,处理方法是类似的。若当前结点总用时间小于己做结点中的最大结点时间期限，则该结点不是解结点，反之则为解结点。3.活结的进站，与出站，我同样是利用了数组，但是定义了两个标号。xl指向了活结点数组开头，x2指向了活结点数组末尾。活结点进站

8、是x2加1，出站是xl加1，当xl=x2吋候结点就出站完毕。总结通过此次期末课程设计，我对分枝限界算法比书本上的认识有了更加深刻的理解。