[其他] 任務分配問題的證明
問題：
有n個難易不同的任務，越難的需時越久。現在有k個工人要完成這n個任務，
每個工人一次只能做一個任務，做完才能做下一個，不可分段做，
且每個工人的能力完全相同，解任務的時間完全依據任務本身。
任務本身沒有相依性完全獨立，不同工人可以解不同任務。
現在要問如何分配任務才能在最短時間完成全部任務？
有個直觀的想法是，任何一個工人挑現有未認領的任務中最難的，做完就依
同樣方式選任務，直到所有任務完成。
請問這個方式是否可得最短時間解？是的話要怎麼證明？
不是的話可否舉出一個反例(某一種任務組合)。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.135.36.190
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1496687025.A.22A.html
推
06/06 02:33, , 1F
06/06 02:33, 1F
→
06/06 02:35, , 2F
06/06 02:35, 2F
→
06/06 12:23, , 3F
06/06 12:23, 3F
※ 編輯: Arton0306 (220.130.177.154), 06/06/2017 12:23:42