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

Dynamic programming algorithm of a sort of optimal assignment problem

考虑一类较一般的最优指派问题 :欲把m项工作指派n个人去完成 (m≥n) ,要求每项工作只能由一个人来做 ,第i个人可以同时做bi 项工作 ,其中bi 是待求未知数 ,满足di ≤bi≤ei(ei,di 为第i个人所需工作数的上下限 )及∑ni=1bi =m为已知常数 (i=1,2 ,… ,n) ,第i个人做第j项工作所用的时间为cij≥ 0 (i =1,2 ,… ,n ;j=1,2 ,… ,m) .本文给出了求解上述最优指派问题 (使总耗用时间最小 )的动态规划算法 .

This paper presents a sort of dynamic programming algorithm for the following generalized optimal assignment problem.There aren persons to be assigned to dom jobs.Each job can only be done by one person,and thei~ th person can dob i job,at the same time,where b i is an unknown positive integer to be calculated,and thatd i≤b i≤e i,d i ande i are upper and lower limits of job number required by i~ th person,and ni=1b\-i=m(m≥n)is a known constant(i=1,2,...,n).The time ofi~ th person′s doingj~ th job isc ij≥0(i=1,2,...,n;j=1,2,...,m).This paper establishes the dynamic programming algorithm for the above problem.