任务分配问题

MATHEMATICAMODEL制作:龚劬任务分配问题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=403.5（3）T0=1395=465

5引入一个0，1变量xij设第i人完成第j项工作的时间是aij，T为从开始工作到最后一项工作完成的时间即总时间。则可得如下优化模型：三、优化模型6可以用隐枚举法和分支定界方法（利用分解技术），割平面法（松弛技术）来求解，但这些方法不是有效算法，无法解规模大的问题。三、优化模型71.贪婪算法（计算机模拟）例.X1=(2,3,8,9,10,7,6),X2=(3,8,5,9,7,6,4)Y=(2,3,5,9,7,6,4)四、启发式算法（近似）1122334455667781.贪婪算法（计算机模拟）

四、启发式算法（近似）1122334455667791.贪婪算法（计算机模拟）

四、启发式算法（近似）11223344556677101.贪婪算法（计算机模拟）

四、启发式算法（近似）11223344556677111.贪婪算法（计算机模拟）

四、启发式算法（近似）1234567123456712345672345761121.贪婪算法（计算机模拟）向量Y=

(b1,b2,…,bn)，其中bj=min{a1j,a2j,…,amj},称Y为各项工作的最短时间向量。称向量Zi=Xi–Y为第i人对Y的误差向量。算法步骤：1）令t=0；2）对当前无工作做的i,任选Zi中未做的一个最小分量所对应的工作干；3）令t为当前所有在干的工作中最先结束的结束时间；4）重复2),3)直到所有工作干完为止。四、启发式算法（近似）131.贪婪算法（计算机模拟）(改进)设Y1为各项工作的第二短时间向量。令

Y=Y1-Y称为罚数向量。算法步骤：1）令t=0；2）对当前无工作做的i,在Zi里未做的最小分量所对应的工作中选择

Y尽可能大的分量所对应的工作干；3）令t为当前所有在干的工作中最先结束的结束时间；4）重复2),3)直到所有工作干完为止。四、启发式算法（近似）1