一类最优指派问题的动态规划算法

摘要

考虑一类指派问题：欲把m项工作指派n个人去完成（m≥n）。要求每项工作只能由一个人来做，第i个人可以同时做bi项工作，其中bi(bi≥1）是待求的未知数；i=1,2,…,n，满足∑ni=1bi=m，假定已知第i人做第j项工作所用的时间cij≥0，i=1，2，…，m。文中给出了求解上述问题最优指派（即使总耗用时间最小）的动态规划解法。