C、C++数据结构代码代写、机器调度C++代写

日期：2018-05-02 10:14

机器调度问题

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

42 / 43

在上述处理中，采用了最长时间优先（LPT）的简单调度策略。在 LPT 算法

中，作业按其所需时间的递减顺序排列，在分配一个作业时，将其分配给最先变

为空闲的机器。

下面设计完成 LPT 算法的存储结构。

· 为每个机器设计数据类型：

struct MachineNode

{

int ID; //机器号

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 将堆 H1 的堆顶元素删除；

3. 堆 H2 的堆顶元素就是最短调度时间；

43 / 43

31. 简单商品分类管理系统（树结构的应用）

1．问题描述

设计一个简单商品分类管理系统，对商品进行分类管理.

2．基本要求

1、浏览当前商品分类目录的所有内容(子分类和当前目录下的商品)

2、切换当前分类目录到上一级分类目录或下一级子分类目录（扩展，切

换到任何一个目录）或直接切换到根目录

3、在当前分类目录下添加新商品目录，或者添加新商品信息。

4、在当前目录下删除某个子商品分类或某个商品信息

5、在当前目录下修改某个商品或分类目录的信息

6、根据某个商品编号（或名称）在整个系统中查找某个商品并显示全部

信息

7、设计合适的交互界面

8、管理系统数据的永久性保存。(选作)

3.设计要求

a) 数据描述：设计合适的数据信息，比如商品，分类目录等等

b) 设计合适的数据结构组织数据，以及设计算法实现需求