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