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

《数据结构程序设计机器调度问题》由会员分享，可在线阅读，更多相关《数据结构程序设计机器调度问题（11页珍藏版）》请在装配图网上搜索。

1、学 号 数据库系统原理课程设计设计说明书机器调度问题起止日期： 2011 年 12月 12 日 至 2011 年 12 月 16 日学生姓名 班级 成绩指导教师(签字) 电子与信息工程系2011年12月16日天津城市建设学院课程设计任务书20112012学年第1学期 电子与信息工程 系 软件工程 专业 班级课程设计名称： 数据结构课程设计 设计题目： 机器调度问题 完成期限：自 2011 年 12 月 12 日至 2012 年 12 月 16 日共 1 周设计依据、要求及主要内容（可另加附页）：一、设计目的熟悉各种数据结构和运算，会使用数据结构的基本操作解决一些实际问题。二、设计要求 （1）重

2、视课程设计环节，用严谨、科学和踏实的工作态度对待课程设计的每一项任务；（2）按照课程设计的题目要求，独立地完成各项任务，严禁抄袭；凡发现抄袭，抄袭者与被抄袭者皆以零分计入本课程设计成绩。凡发现实验报告或源程序雷同，涉及的全部人员皆以零分计入本课程设计成绩；（3）学生在接受设计任务后，首先要按设计任务书的要求编写设计进程表；（4）认真编写课程设计报告。三、设计内容机器调度问题1)问题描述机器调度是指有m台机器需要处理n个作业，设作业i的处理时间为ti，则对n个作业进行机器分配，使得：(1) 一台机器在同一时间内只能处理一个作业；(2) 一个作业不能同时在两台机器上处理；(3) 作业i一旦运行，则

3、需要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

4、上，作业5在06时间完成，作业6在611时间完成，作业3在1115时间完成，作业1在1517时间完成。注意到作业i只能在一台机器上从si时刻到si +ti时间完成且任何机器在同一时刻仅能处理一个作业，因此最短调度长度为17。m1m2m3时间分配 作业5作业6 作业3作业1作业2 作业7 作业41716图9 三台机器的调度示例654 在上述处理中，采用了最长时间优先（LPT）的简单调度策略。在LPT算法中，作业按其所需时间的递减顺序排列，在分配一个作业时，将其分配给最先变为空闲的机器。 下面设计完成LPT算法的存储结构。 为每个机器设计数据类型： struct MachineNode int I

5、D; /机器号int avail; /机器可用时刻 ; 为每个作业设计数据类型： struct JobNode 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 将

6、堆H1的堆顶元素删除；3. 堆H2的堆顶元素就是最短调度时间；四、参考文献1王红梅数据结构清华大学出版社2王红梅数据结构学习辅导与实验指导清华大学出版社3严蔚敏，吴伟民数据结构（C语言版）清华大学出版社一、需求分析本系统主要针对机器、工作数，等问题的分配调度而开发设计，系统中输入工作数、完成时间，以及机器数量，就可以计算出完成工作所需的最短时间。此系统可以广泛的应用于各个领域的生产型企业，以及各行各业中涉及到工作分配的问题。二、问题求解1、一个钻石加工工厂要加工5颗钻石，按照钻石规格的不同5颗钻石分别需要1天、2天、3天、4天、5天。加工完成。现在一共有三名加工工人。问完成这批钻石加工最短需要

7、多长时间。对于这个问题首先建立一个模型。给5个钻石编号A、B、C、D、EA1天、B2天、C3天、D4天、E5天工人：甲、乙、丙三名。要想做到能在最短的时间能完成该问题，就涉及到一个工作分配的问题。实现最短时间完成工作，首先在工作分配上应该将工作的优先级别划分一下。按照时间的长短我们可以将其划分为。EDCBA那么在完成工作的时候就应该按照优先级来考虑，首先将EDC三个任务交给甲乙丙三个工人完成。甲E(5天)乙D(4天)丙C(3天)在第三天的时候丙完成了任务C因此再将任务B分配给丙来完成。丙C（3天）B（2天）在第四天的时候乙完成了任务D，因此再将最后一个工作A交给乙乙D（4天）A(1天)至此在第

8、五天的时候A、B、C、D、E五颗钻石全部加工完成。即：甲E(5天)乙D(4天)A(1天)丙C(3天)B(2天)最短完成时间：5天三、总体设计输入工作数量设定每项工作所需的工作时间系统根据每一项工作所需的时间分配优先级输入机器数量按照优先级别从高到底依次分配当有机器完成一项工作是如还有工作按优先级继续分配输出工作机器的分配四、详细设计1、输入：输入工作数、每个工作需要的时间、以及机器数量 包括定义输入项目、定义输入类型#include#define N 10 using namespace std;限定机器数和作业数的范围N，不超过10struct MachineNode int ID; int

9、 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、计算工作天数，以最后完成工作的机器作为标准，计算该机器从完成第一个工作开始，直至完成

10、最后一个工作所需的时间总和。M1.avail+=J1.time; 将小根堆的堆顶机器加上大根堆的堆顶作业的处理时间，重新插入小根堆（循环执行HeapSortX(M,m)时完成）（模块功能说明（如函数功能、入口及出口参数说明，函数调用关系描述等）；五、调试与测试1、大根堆、小根堆的建立（网络查资料解决）2、关于机器工作时间的设定3、最后计算总时间时输出有误原因：时间计算错误改正方法：M1.avail+=J1.time; 将小根堆的堆顶机器加上大根堆的堆顶作业的处理时间，重新插入小根堆（循环执行HeapSortX(M,m)时完成）插入一个循环执行命令计算时间。六、关键源程序清单和执行结果#incl

11、ude#define N 10 /限定机器数和作业数不超过N个，这里N取10using namespace std;/*struct MachineNode 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(jm&rj.timerj.time)break; else int temp1,temp2; temp1=ri.time;ri.time

12、=rj.time;rj.time=temp1;temp2=ri.ID;ri.ID=rj.ID;rj.ID=temp2; void HeapSortD(JobNode r,int n) for(int i=n/2;i=1;i-) SiftD(r,i,n);/*/*/建立小根堆void SiftX(MachineNode r,int k,int m) int i,j; i=k; j=2*i; while(j=m) if(jrj+1.avail)j+; if(ri.avail=1;i-) SiftX(r,i,n);/*void assign(MachineNode M,JobNode J,int m

13、,int j) /完成任务分配 if(m=j) /如果机器数m大于或等于作业数j cout一台机器完成一个作业，最大工作时间为:; HeapSortD(J,j); /以各作业所需时间建立大根堆，堆顶元素即为最大耗时的作业 coutJ1.timeendl; /最大工作时间即为最大耗时的作业的所需时间 else /如果机器数m小于作业数j for(int i=1;i=m;i+) /先为每台机器分配一个作业，先把所需时间最大的m个作业分配给m台机器。 HeapSortD(J,j); /建立大根堆求堆顶元素确定其中耗时最大的作业 Mi.avail=J1.time; /机器i的处理时间即为作业的所需时间

14、 cout机器Mi.ID完成作业J1.IDendl; for(int k=1;k=1;q-) /把剩余的j-m个作业分配下去（j=j-m） HeapSortX(M,m); /将m机器个机器按可用时建立小根堆 HeapSortD(J,j); /将j个作业按处理时间建立大根堆 cout机器M1.ID完成作业J1.IDendl; /将大根堆的堆顶作业分配给小根堆的堆顶机器 M1.avail+=J1.time; /将小根堆的堆顶机器加上大根堆的堆顶作业的处理时间，重新插入小根堆（循环执行HeapSortX(M,m)时完成） for(int k=1;kj;k+) /减去已分配的作业 Jk=Jk+1; j

15、=j-1; cout最短调度时间为：M1.availendl; /小根堆的堆顶元素就是最短调用时间 void main() int j=0; /作业个数 int m=0; /机器个数 int i; MachineNode MN; /机器的结构体数组 JobNode JN; /作业的结构体数组 coutj; cout请输入每个作业需要的处理时间:endl; for(i=1;i=j;i+) Ji.ID=i; /为每个作业确定序号 cout第iJi.time; /输入每个作业的用时 coutm; for(i=1;i=m;i+) Mi.ID=i; /为每台机器确定序号 assign(M,J,m,j); /调用完成分配任务的函数程序运行截图：输入作业个数、每个作业需要的处理时间输入机器的个数机器完成作业情况111