资源描述：
《机器调度问题 大数据结构课设c++.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、学号09770210数据结构课程设计设计说明书题目机器调度问题起止日期：2009年10月20日至2009年12月14日学生艳羽班级软件二班成绩指导教师(签字)电子与信息工程系年月日附录四课程设计任务书城市建设学院课程设计任务书2009—2010学年第1学期电子与信息工程系软件工程专业2班级课程设计名称：数据结构课程设计设计题目：机器调度问题完成期限：自2009年10月20日至2009年12月14日共周设计依据、要求及主要容（可另加附页）：一、设计目的熟悉各种数据结构和运算，会使用数据结构的基本操作解决
2、一些实际问题。二、设计要求（1）重视课程设计环节，用严谨、科学和踏实的工作态度对待课程设计的每一项任务；（2）按照课程设计的题目要求，独立地完成各项任务，严禁抄袭；凡发现抄袭，抄袭者与被抄袭者皆以零分计入本课程设计成绩。凡发现实验报告或源程序雷同，涉及的全部人员皆以零分计入本课程设计成绩；（3）学生在接受设计任务后，首先要按设计任务书的要求编写设计进程表；（4）认真编写课程设计报告。三、设计容机器调度问题1)问题描述机器调度是指有m台机器需要处理n个作业，设作业i的处理时间为ti，则对n个作业进行机器
3、分配，使得：(1)一台机器在同一时间只能处理一个作业；(2)一个作业不能同时在两台机器上处理；(3)作业i一旦运行，则需要ti个连续时间单位。设计算法进行合理调度，使得在m台机器上处理n个作业所需要的处理时间最短。2)基本要求(1)建立问题模型，设计数据结构；(2)设计调度算法，为每个作业分配一台可用机器；(3)给出分配方案。3)设计思想假设有七个作业，所需时间分别为{2,14,4,16,6,5,3}，有三台机器，编号分别为m1、m2和m3。这七个作业在三台机器上进行调度的情形如图9所示，阴影区代表作
4、业的运行区间。作业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。m1m2m3时间分配作业5作业6作业3作业1作业2作业7作业41716图9三台机器
5、的调度示例654在上述处理中，采用了最长时间优先（LPT）的简单调度策略。在LPT算法中，作业按其所需时间的递减顺序排列，在分配一个作业时，将其分配给最先变为空闲的机器。四、参考文献1．王红梅．数据结构．清华大学2．王红梅．数据结构学习辅导与实验指导．清华大学3．严蔚敏，吴伟民．数据结构（C语言版）．清华大学一、需求分析（一）程序的功能为给出的作业根据时间数分配机器。将作业按其所需时间的递减顺序排列。一台机器在同一时刻只能处理一个作业，在分配一个作业时，将其分配给最先变为空闲的机器。直到所有作业分配完
6、毕。算出最短调度时间。（二）输入输出的要求每个作业的所需的时间数和机器数为输入。输出为每个作业所分配的机器（每个机器所完成的作业），以及最短调度时间。二、问题求解给出7个要完成的作业，作业所需的时间数分别为{2,14,4,16,6,5,3}，把这些作业在三台机器中完成。首先将7个作业由大到小排序，排序后为{16,14,6,5,4,3,2}，接着开始为机器分配作业。作业由大到小分配。每个机器同一时间只能分配一个作业。在分配一个作业时，将其分配给最先变为空闲的机器，把16分配给机器一，14分配给机器二,6
7、分配给机器三。比较三台机器完成作业所需时间数，机器三最小。所以机器三先空闲下来。把5分配给机器三，比较三台机器完成作业所需时间数，机器三最小。所以机器三先空闲下来。把4分配给机器三，比较三台机器完成作业所需时间数，机器二最小。所以机器二先空闲下来。把3分配给机器二，比较三台机器完成作业所需时间数，机器三最小。所以机器三先空闲下来。把2分配给机器三，到此作业分配完毕。所需时间最长的机器上的所需时间就是最短调度时间。三、总体设计程序设计组成框图：开始机器一机器二机器三机器一最小？机器二最小？机器三最小？算
8、出最短调度时间流程图：作业所需的时间数机器一机器二机器三将时间数从大到小排序1614654111531717216四、详细设计1、运用下面的代码计算哪台机器空闲intmin=machines[0];for(inti=0;i
