1 3
1395
=
465
-5-
三、优化模型
引入一个0，1变量xij
1 第j项工作由第i人做 xij 0 否则
设第i人完成第j项工作的时间是aij，T为从开始工作到 最后一项工作完成的时间即总时间。则可得如下优化模型：
n
min
T
max{
1im
j
1
aij
xij
}
m
39, 45, 56, 52, 12, 38, 56, 32, 44, 36, 36, 34, 28, 31, 24, 13, 23, 59, 14, 30, 29, 35, 18, 34, 23, 42, 38, 18, 57, 43, 36, 30, 16, 50, 33, 48, 40, 52, 11, 21, 14, 16, 27, 17), X2=(11, 37, 43, 38, 52, 15, 20, 44, 33, 28, 18, 46, 57, 37, 15, 48, 31, 34, 35, 21, 27, 15, 40, 19, 57, 15, 33, 24, 54, 48, 24, 44, 23, 15, 12, 27, 50, 25, 22, 35, 23, 28, 13, 35, 21, 54, 40, 48, 57, 27, 38, 15, 42, 31, 59, 16, 57, 42, 28, 18, 34, 21)。 X3=(46, 37, 39, 25, 26, 49, 11, 49, 51, 46, 13, 31, 35, 50, 29, 59, 54, 13, 58, 29, 37, 15, 13, 40, 34, 25, 42, 43, 24, 24, 52, 52, 40, 60, 21, 22, 45, 60, 23, 37, 16, 60, 44, 11, 39, 16, 16, 50, 25, 13, 25, 30, 26, 58, 59, 31, 24, 19, 19, 43, 31, 31)
MATHEMATICA MODEL
任务分配问题
制作: 龚劬
一、问题重述
假设有m个人，共同完成n项工作，(n>m≥2)。每 个人可以干任何一件工作，但效率不同，任意时刻每个 人只能干一件工作，每项工作只能由一人独立完成。
如果这m个人任选一项工作同时开始干，每个人干完 一件工作后，立即选一项还没有人干过的工作接着干， 直到所有n项工作全部完成。从开始工作到最后一项工 作完成的时间称为总完成时间，简称总时间，记为T。
58, 29, 37, 49, 13, 40, 34, 25, 42, 43, 24, 24, 52), X2=(52, 37, 60, 56, 22, 45，60, 23, 37, 16, 60, 44, 11, 39, 16, 16, 50, 25,
13, 25, 30, 26, 58, 59, 31, 24, 19, 19, 43, 31, 31)。 （3） X1=(46, 27, 42, 21, 20, 40, 15, 33, 56, 24, 50, 29, 25, 56, 42, 42, 32, 15,
s.t.
xij 1 j 1,2,, n
i 1
xij 0或1， i 1,m, j 1,n
-6-
三、优化模型
可以用隐枚举法和分支定界方法（利用分解技术）， 割平面法（松弛技术）来求解，但这些方法不是有效算 法，无法解规模大的问题。
-7-
四、启发式算法（近似）
1.贪婪算法（计算机模拟） 例.X1=(2, 3, 8, 9, 10, 7, 6) , X2=(3, 8, 5, 9, 7, 6, 4) Y=(2,3,5,9,7,6,4)
11 22
33
44
55
66 77
-8-
四、启发式算法（近似）
1.贪婪算法（计算机模拟）
11 22
33
44
55
66
77
-9-
四、启发式算法（近似）
1.贪婪算法（计算机模拟）
11 22
33
44
55
66 77
-10-
四、启发式算法（近似）
1.贪婪算法（计算机模拟）
11 22
33
44
55
66 77
-11-
-3-
二、问题分析
总时间的一个下界
我们的任务是寻找一个最佳调度方案，使总完成时
间最短，该问题是一个NP难题，不存在有效算法。求解
大规模问题要用近似算法。最好能找到一个评价结果的
指标。下面给出总时间的一个下界。设Y是最短时间向量，
如果每人都用Y中的时间来干工作，中间无间息，且每人
的最后一项工作都同时干完，这时的总时间T最小，为T0
算法步骤： 1）令t=0； 2）对当前无工作做的i,任选Zi中未做的一个最小分量
所对应的工作干； 3）令t为当前所有在干的工作中最先结束的结束时间； 4）重复2),3)直到所有工作干完为止。
-13-
四、启发式算法（近似）
1.贪婪算法（计算机模拟） (改进) 设Y1为各项工作的第二短时间向量。令Y=Y1-Y称为 罚数向量。
因此有如下结T论0
1 m
n
j
1
min
1im
(
aij
)
定理
T
1 m
n
j
1
min
1im
(aij
)
-4-
总时间的一个下界
根据上述定理，计算出一个特定问题的下限很容易， 对本问题的三种情形可计算出其下限。
（1）T0=
1 2
(2
3
5
9
7
6
4)
18
（2）T0=
1 2
31
yi
i 1
1 2
807
=
403.5
为使总时间T尽量小，请对以下三种情况，分别确定 每个人应干哪几项工作？顺序如何？并求出T。
对一般情况进行讨论
-2-
一、问题重述
（1） X1=(2, 3, 8, 9, 10, 7, 6) , X2=(3, 8, 5, 9, 7, 6, 4)。 （2） X1=(44, 37, 39, 25, 26, 49, 11, 49, 51, 46, 13, 31, 11, 50, 29, 16, 54, 13,
四、启发式算法（近似）
1.贪婪算法（计算机模拟）
13
25
47
23
2 1
45
4
4 6
5
3
2 5
6
6
1
67
7
7
3
1
-12-
四、启发式算法（近似）
1.贪婪算法（计算机模拟） 向量Y= (b1,b2,…,bn)， 其中bj=min{a1j,a2j,…,amj},称Y为各项工作的最短时 间向量。称向量Zi=Xi–Y为第i人对Y的误差向量。