1. 设有

n

n

n 个独立的作业

1

,

2

,

…

,

n

{1, 2, …, n}

1,2,…,n，由

m

m

m 台相同的机器

M

1

,

M

2

,

…

,

M

m

{M_1, M_2, …, M_m}

M1​,M2​,…,Mm​ 进行加工处理，作业

i

i

i 所需的处理时间为

t

i

(

1

≤

i

≤

n

)

t_i(1≤i≤n)

ti​(1≤i≤n)，每个作业均可在任何一台机器上加工处理，但不可间断、拆分。多机调度问题要求给出一种作业调度方案，使所给的

n

n

n 个作业在尽可能短的时间内由

m

m

m 台机器加工处理完成。

 2. 解决思路：（1）如果

n

<

m

nm

n>m，则用贪心算法求解。

 3. 贪心算法求解多机调度问题的贪心策略是最长处理时间的作业优先，即把处理时间最长的作业分配给最先空闲的机器，这样可以保证处理时间长的作业优先处理，从而在整体上获得尽可能短的处理时间。

 设

7

7

7 个独立作业

1

,

2

,

3

,

4

,

5

,

6

,

7

{1, 2, 3, 4, 5, 6, 7}

1,2,3,4,5,6,7 由

3

3

3 台机器

M

1

,

M

2

,

M

3

{M1, M2, M3}

M1,M2,M3 加工处理，各作业所需的处理时间分别为

2

,

14

,

4

,

16

,

6

,

5

,

3

{2, 14, 4, 16, 6, 5, 3}

2,14,4,16,6,5,3。贪心算法产生的作业调度如下图所示。所需要的加工时间为17。