任务分配问题.ppt

MATHEMATICA MODEL
制作: 龚劬
任务分配问题
1
假设有m个人,共同完成n项工作,(n>m≥2)。每个人可以干任何一件工作,但效率不同,任意时刻每个人只能干一件工作,每项工作只能由一人独立完成。
如果这m个人任选一项工作同时开始干,每个人干完一件工作后,立即选一项还没有人干过的工作接着干,直到所有n项工作全部完成。从开始工作到最后一项工作完成的时间称为总完成时间,简称总时间,记为T。
为使总时间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,
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,
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)
一、问题重述
3
总时间的一个下界
我们的任务是寻找一个最佳调度方案,使总完成时间最短,该问题是一个NP难题,不存在有效算法。求解大规模问题要用近似算法。最好能找到一个评价结果的指标。下面给出总时间的一个下界。设Y是最短时间向量,如果每人都用Y中的时间来干工作,中间无间息,且每人的最后一项工作都同时干完,这时的总时间T最小,为T0
因此有如下结论
定理
二、问题分析
4
总时间的一个下界
根据上述定理,计算出一个特定问题的下限很容易,对本问题的三种情形可计算出其下限。
(1)T0=
(2)T0= 807 =
(3)T0= 1395 = 465
5
引入一个0,1变量xij
设第i人完成第j项工作的时间是aij,T为从开始工作到最后一项工作完成的时间即总时间。则可得如下优化模型:
三、优化模型
6
可以用隐枚举法和分支定界方法(利用分解技术),割平面法(松弛技术)来求解,但这些方法不是有效算法,无法解规模大的问题。
三、优化模型
7
(计算机模拟)
=(2, 3, 8, 9, 10, 7, 6) , X2=(3, 8, 5, 9, 7, 6, 4)
Y=(2,3,5,9,7,6,4)
四、启发式算法(近似)
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
(计算机模拟)
四、启发式算法(近似