机器调度问题-数据结构课设c++.doc

机器调度问题 数据结构课设c++
学 号 09770210

数据结构课程设计
设计说明书

题目
机器调度问题

起止日期： 2009年 10月 20 日 至 2009 年 12月14日

学生姓名
张艳羽
班级
软件二班
成绩

指导教师(签字)

电子与信息工程系
年 月 日
附录四 课程设计任务书
天津城市建设学院
课程设计任务书
2009—2010学年第1学期
电子与信息工程 系 软件工程 专业 2 班级
课程设计名称： 数据结构课程设计
设计题目： 机器调度问题
完成期限：自 2009 年 10 月 20 日至 2009 年 12 月 14 日共 周
设计依据、要求与主要内容（可另加附页）：
一、设计目的
熟悉各种数据结构和运算，会使用数据结构的基本操作解决一些实际问题。
二、设计要求
（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
作业3
作业1
作业2
作业7
作业4
17
16
图9 三台机器的调度示例
6
5
4

在上述处理中，采用了最长时间优先（LPT）的简单调度策略。在LPT算法中，作业按其所需时间的递减顺序排列，在分配一个作业时，将其分配给最先变为空闲的机器。

四、参考文献
1．王红梅．数据结构．清华大学出版社
2．王红梅．数据结构学习辅导与实验指导．清华大学出版社
3．严蔚敏，吴伟民．数据结构（C语言版）．清华大学出版社

一、 需求分析
（一） 程序的功能
为给出的作业根据时间数分配机器。将作业按其所需时间的递减顺序排列。一台机器在同一时刻只能处理一个作业，在分配一个作业时，将其分配给最先变为空闲的机器。直到所有作业分配完毕。算出最短调度时间。
（二） 输入输出的要求
每个作业的所需的时间数和机器数为输入。输出为每个作业所分配的机器（每个机器所完成的作业），以与最短调度时间。

二、问题求解
给出7个要完成的作业，作业所需的时间数分别为{2, 14, 4, 16, 6, 5, 3}，把这些作业在三台机器中完成。首先将7个作业由大到小排序，排序后为{16, 14, 6, 5, 4, 3, 2}，接着开始为机器分配作业。作业由大到小分配。每个机器同一时间只能分配一个作业。在分配一个作业时，将其分配给最先变为空闲的机器，
把16分配给机器一，14分配给机器二, 6分配给机器三。比较三台机器完成作业所需时间数，机器三最小。所以机器三先空闲下来。
把5分配给机器三，比较三台机器完成作业所需时间数，机器三最小。所以机器三先空闲下来。
把4分配给机器三，比较三台机器完成作业所需时间数，机器二最小。所以机器二先空闲下来。
把3分配给机器二，比较三台机器完成作业所需时间数，机器三最小。所以机器三先空闲下来。
把2分配给机器三，到此作业分配完毕。所需时间最长的机器上的所需时间就是最短调度时间。

三、总体设计

程序设计组成框图：

开始
机器一
机器二
机器三
机器一最小？
机器二最小？
机器三最小？
算出最短调度时间

流程图：

作业所需的时间数
机器一
机器二
机器三
将时间数从大到小排序
16
14
6
5
4
11
15
3
17
17
2
16

四、详细设计
1、运用下面的代码计算哪台机器空闲
int min=machines[0];
for(int i=0;i<machines.length;i++){
if(machines[i]<min){
min=machines[i];
}
}
if(machines[0]==min) System.out.println("第"+1+"个机器空闲，可以开始下一个作业！");
if(machines[1]==min) System.out.println("第"+2+"个机器空闲，可以开始下一个作业！");
if(machines[2]==min) System.out.println("第"+3+"个机器空闲，可以开始下一个作业！");

2、运用下面源代码计算最短调度时间
int max=machines[0];
for(int i=0;i<machines.length;i++){
if(machines[i]>max){
max=machines[i];
}
}

五、调试与测试
直接运行此程序。在控制台输出此程序的结果。

每当出现机器（）空闲后，输入空闲的机器，继续下一步操作。直到作业分配完毕。

六、关键源程序清单和执行结果

源代码：
import java.util.Arrays;
import java.util.Scanner;

public class MyData {

public MyData(){

}
public static void main(String[] args) {
int[] works={2,14,4,16,6,5,3}; //准备调度的作业
int N=works.length;
System.out.print("准备调度的作业的时间数分别为：");
for(int i=0;i<N;i++){
System.out.print(works[i]+" ");
}
System.out.println();
int temp=0;

Scanner input=new Scanner(System.in);
for(int i=0;i<N-1;i++){ //对给出的作业时间数从大到小冒泡排序
for(int j=0;j<N-i-1;j++){
if(works[j]<works[j+1]){
temp=works[j];
works[j]=works[j+1];
works[j+1]=temp;
}
}
}

int[] machines=new int[3];
machines[0]=works[0];
System.out.println("开始作业！！");
System.out.println("机器1完成时间数为"+works[0]+"的作业");
machines[1]=works[1];
System.out.println("机器2完成时间数为"+works[1]+"的作业");
machines[2]=works[2];
System.out.println("机器3完成时间数为"+works[2]+"的作业");
int min=machines[0];
for(int i=0;i<machines.length;i++){
if(machines[i]<min){
min=machines[i];
}
}
if(machines[0]==min) System.out.println("第"+1+"个机器空闲，可以开始下一个作业！");
if(machines[1]==min) System.out.println("第"+2+"个机器空闲，可以开始下一个作业！");
if(machines[2]==min) System.out.println("第"+3+"个机器空闲，可以开始下一个作业！");
///////////////////////////////////////////////////////////////////////////
System.out.println("开始下一个作业的机器是：");
int shuru1=input.nextInt();
System.out.println("机器"+shuru1+"完成时间数为"+works[3]+"的作业");
machines[shuru1-1]=machines[shuru1-1]+works[3];

min=machines[0];
for(int i=0;i<machines.length;i++){
if(machines[i]<min){
min=machines[i];
}
}
if(machines[0]==min) System.out.println("第"+1+"个机器空闲，可以开始下一个作业！");
if(machines[1]==min) System.out.println("第"+2+"个机器空闲，可以开始下一个作业！");
if(machines[2]==min) System.out.println("第"+3+"个机器空闲，可以开始下一个作业！");
////////////////////////////////////////////////////////////////////
System.out.println("开始下一个作业的机器是：");
int shuru2=input.nextInt();
System.out.println("机器"+shuru2+"完成时间数为"+works[4]+"的作业");
machines[shuru2-1]=machines[shuru2-1]+works[4];

min=machines[0];
for(int i=0;i<machines.length;i++){
if(machines[i]<min){
min=machines[i];
}
}
if(machines[0]==min) System.out.println("第"+1+"个机器空闲，可以开始下一个作业！");
if(machines[1]==min) System.out.println("第"+2+"个机器空闲，可以开始下一个作业！");
if(machines[2]==min) System.out.println("第"+3+"个机器空闲，可以开始下一个作业！");
/////////////////////////////////////////////////////////////////////////
System.out.println("开始下一个作业的机器是：");
int shuru3=input.nextInt();
System.out.println("机器"+shuru3+"完成时间数为"+works[5]+"的作业");
machines[shuru3-1]=machines[shuru3-1]+works[5];

min=machines[0];
for(int i=0;i<machines.length;i++){
if(machines[i]<min){
min=machines[i];
}
}
if(machines[0]==min) System.out.println("第"+1+"个机器空闲，可以开始下一个作业！");
if(machines[1]==min) System.out.println("第"+2+"个机器空闲，可以开始下一个作业！");
if(machines[2]==min) System.out.println("第"+3+"个机器空闲，可以开始下一个作业！");
/////////////////////////////////////////////////////////////////
System.out.println("开始下一个作业的机器是：");
int shuru4=input.nextInt();
System.out.println("机器"+shuru4+"完成时间数为"+works[6]+"的作业");
machines[shuru4-1]=machines[shuru4-1]+works[6];
System.out.println("到此为止作业分配完毕！");
int max=machines[0];
for(int i=0;i<machines.length;i++){
if(machines[i]>max){
max=machines[i];
}
}
System.out.println("最短调度时间为："+max);

}

}

输出结果：

14 / 14