数据结构程序设计机器调度问题.doc-资料库

ae8b061b-bc59-4ec1-8018-4cefc9cd04df.doc.pdf-第1页.png

第1页 / 共11页

ae8b061b-bc59-4ec1-8018-4cefc9cd04df.doc.pdf-第2页.png

第2页 / 共11页

ae8b061b-bc59-4ec1-8018-4cefc9cd04df.doc.pdf-第3页.png

第3页 / 共11页

ae8b061b-bc59-4ec1-8018-4cefc9cd04df.doc.pdf-第4页.png

第4页 / 共11页

ae8b061b-bc59-4ec1-8018-4cefc9cd04df.doc.pdf-第5页.png

第5页 / 共11页

ae8b061b-bc59-4ec1-8018-4cefc9cd04df.doc.pdf-第6页.png

第6页 / 共11页

ae8b061b-bc59-4ec1-8018-4cefc9cd04df.doc.pdf-第7页.png

第7页 / 共11页

ae8b061b-bc59-4ec1-8018-4cefc9cd04df.doc.pdf-第8页.png

第8页 / 共11页

数据库系统原理课程设计设计说明书机器调度问题起止日期： 2016 年 1 月 12 日至 2016 年 12 月 16 日学生姓名班成级绩指导教师 ( 签字 ) 电子与信息工程系 2016 年 1 月 16 日

课程设计任务书 2011—2012 学年第 1 学期电子与信息工程系软件工程专业班级课程设计名称：数据结构课程设计设计题目：机器调度问题完成期限：自年 12 月 12 日至年 12 月 16 日共 1 周设计依据、要求及主要内容（可另加附页）：一、设计目的熟悉各种数据结构和运算，会使用数据结构的基本操作解决一些实际问题。二、设计要求（1）重视课程设计环节，用严谨、科学和踏实的工作态度对待课程设计的每一项任务；（2）按照课程设计的题目要求，独立地完成各项任务，严禁抄袭；凡发现抄袭，抄袭者与被抄袭者皆以零分计入本课程设计成绩。凡发现实验报告或源程序雷同，涉及的全部人员皆以零分计入本课程设计成绩；（3）学生在接受设计任务后，首先要按设计任务书的要求编写设计进程表；（4）认真编写课程设计报告。三、设计内容机器调度问题 1)问题描述机器调度是指有 m 台机器需要处理 n 个作业，设作业 i 的处理时间为 ti，则对 n 个作业进行机器分配，使得： (1) 一台机器在同一时间内只能处理一个作业； (2) 一个作业不能同时在两台机器上处理； (3) 作业 i 一旦运行，则需要 ti 个连续时间单位。设计算法进行合理调度，使得在 m 台机器上处理 n 个作业所需要的处理时间最短。 2) 基本要求 (1) 建立问题模型，设计数据结构； (2) 设计调度算法，为每个作业分配一台可用机器； (3) 给出分配方案。

3) 设计思想假设有七个作业，所需时间分别为{2, 14, 4, 16, 6, 5, 3}，有三台机器，编号分别为 m1、m2 和 m3。这七个作业在三台机器上进行调度的情形如图 9 所示，阴影区代表作业的运行区间。作业 4 在 0 到 16 时间被调度到机器 1 上运行，在这 16 个时间单位中，机器 1 完成了对作业 4 的处理；作业 2 在 0 到 14 时间被调度到机器 2 上处理，之后机器 2 在 14 到 17 时间处理作业 7；在机器 3 上，作业 5 在 0～6 时间完成，作业 6 在 6～11 时间完成，作业 3 在 11～15 时间完成，作业 1 在 15～17 时间完成。注意到作业 i 只能在一台机器上从 si 时刻到 si +ti 时间完成且任何机器在同一时刻仅能处理一个作业，因此最短调度长度为 17。 m1 m2 m3 时间分配作业 5 6 作业 4 作业 2 作业 7 作业 6 作业 3 作业 1 4 5 16 17 图 9 三台机器的调度示例在上述处理中，采用了最长时间优先（LPT）的简单调度策略。在 LPT 算法中，作业按其所需时间的递减顺序排列，在分配一个作业时，将其分配给最先变为空闲的机器。下面设计完成 LPT 算法的存储结构。 · 为每个机器设计数据类型： struct MachineNode { int ID; int avail; //机器号 //机器可用时刻 }; · 为每个作业设计数据类型： JobNode struct { int ID; int time; //作业号 //处理时间 }; LPT 算法用伪代码描述如下： 1. 如果作业数 n≤机器数 m，则 1.1 将作业 i 分配到机器 i 上； 1.2 最短调度长度等于 n 个作业中处理时间最大值； 2. 否则，重复执行以下操作，直到 n 个作业都被分配： 2.1 将 n 个作业按处理时间建成一个大根堆 H1；

2.2 将 m 个机器按可用时刻建立一个小根堆 H2； 2.3 将堆 H1 的堆顶作业分配给堆 H2 的堆顶机器； 2.4 将 H2 的堆顶机器加上 H1 的堆顶作业的处理时间重新插入 h2 中； 2.5 将堆 H1 的堆顶元素删除； 3. 堆 H2 的堆顶元素就是最短调度时间；四、参考文献 1．王红梅．数据结构．清华大学出版社 2．王红梅．数据结构学习辅导与实验指导．清华大学出版社 3．严蔚敏，吴伟民．数据结构（C 语言版）．清华大学出版社

一、需求分析本系统主要针对机器、工作数，等问题的分配调度而开发设计，系统中输入工作数、完成时间，以及机器数量，就可以计算出完成工作所需的最短时间。此系统可以广泛的应用于各个领域的生产型企业，以及各行各业中涉及到工作分配的问题。二、问题求解 1、一个钻石加工工厂要加工 5 颗钻石，按照钻石规格的不同 5 颗钻石分别需要 1 天、2 天、3 天、4 天、5 天。加工完成。现在一共有三名加工工人。问完成这批钻石加工最短需要多长时间。对于这个问题首先建立一个模型。给 5 个钻石编号 A、B、C、D、E A——1 天、B——2 天、C——3 天、D——4 天、E——5 天工人：甲、乙、丙三名。要想做到能在最短的时间能完成该问题，就涉及到一个工作分配的问题。实现最短时间完成工作，首先在工作分配上应该将工作的优先级别划分一下。按照时间的长短我们可以将其划分为。 E>D>C>B>A 那么在完成工作的时候就应该按照优先级来考虑，首先将 EDC 三个任务交给甲乙丙三个工人完成。甲——E(5 天) 乙——D(4 天) 丙——C(3 天) 在第三天的时候丙完成了任务 C 因此再将任务 B 分配给丙来完成。丙——C（3 天）——B（2 天）在第四天的时候乙完成了任务 D，因此再将最后一个工作 A 交给乙乙——D（4 天）——A(1 天) 至此在第五天的时候 A、B、C、D、E 五颗钻石全部加工完成。即：甲——E(5 天) 乙——D(4 天)——A(1 天) 丙——C(3 天)——B(2 天) 最短完成时间：5 天 15

三、总体设计输入工作数量设定每项工作所需的工作时间系统根据每一项工作所需的时间分配优先级输入机器数量按照优先级别从高到底依次分配当有机器完成一项工作是如还有工作按优先级继续分配输出工作机器的分配 16

四、详细设计 1、输入：输入工作数、每个工作需要的时间、以及机器数量包括定义输入项目、定义输入类型 #include #define N 10 using namespace std; 限定机器数和作业数的范围 N，不超过 10 struct MachineNode { int ID; int avail; }; struct JobNode { int ID; int time; }; 输入机器号、机器可用时间、作业数、每项作业完成所需时间 2、工作排序：按照时间长短的顺序将工作划分优先级，即所需时间最长的优先安排机器开工。 void assign(MachineNode M[],JobNode J[],int m,int j) 任务的分配 if(m>=j) 机器数量和作业量的对比 3、机器工作分配：当有机器完成工作时，如果还留有未被分配的工作，则仍按照优先级开始完成工作。 for(int q=j;j>=1;q--) 剩余作业的分配。 4、计算工作天数，以最后完成工作的机器作为标准，计算该机器从完成第一个工作开始，直至完成最后一个工作所需的时间总和。 M[1].avail+=J[1].time; 将小根堆的堆顶机器加上大根堆的堆顶作业的处理时间，重新插入小根堆（循环执行 HeapSortX(M,m)时完成）（模块功能说明（如函数功能、入口及出口参数说明，函数调用关系描述等）；五、调试与测试 1、大根堆、小根堆的建立（网络查资料解决） 2、关于机器工作时间的设定 3、最后计算总时间时输出有误原因：时间计算错误改正方法：M[1].avail+=J[1].time; 将小根堆的堆顶机器加上大根堆的堆顶作业的处理时间，重新插入小根堆（循环执行 HeapSortX(M,m)时完成） 17

插入一个循环执行命令计算时间。六、关键源程序清单和执行结果 #include #define N 10 using namespace std; //****************************************** struct MachineNode { //限定机器数和作业数不超过 N 个，这里 N 取 10 int ID; int avail; //机器可用时间 //机器号 }; struct JobNode { int ID; //作业号 int time; //处理时间 }; //******************************************* //建立大根堆 void SiftD(JobNode r[],int k,int m) { int i,j; i=k; j=2*i; while(j<=m) { if(jr[j].time)break; else { int temp1,temp2; temp1=r[i].time; r[i].time=r[j].time; r[j].time=temp1; temp2=r[i].ID; r[i].ID=r[j].ID; r[j].ID=temp2; } } } void HeapSortD(JobNode r[],int n) { for(int i=n/2;i>=1;i--) SiftD(r,i,n); } 18

资料库

数据结构程序设计机器调度问题.doc

相关推荐

课程资源

热门标签

最新资料