m维瓶颈指派问题的动态规划模型

m维瓶颈指派问题:把m个人指派到n项工作上(m>n),要求每人只做一件工作,已知每人做每件工作的效益,问题是如何把m人划分成n组m1,m2,…,mn,nΣj=1mj=m,让mj组人去做第j件工作,可使效益最低的一组效益达到最大。本文对此问题建立了动态规划模型,并利用黄金分割律作为工具给出了动态规划模型的解。最后,文章给出一个算例以说明该方法的可行性和有效性。

Dynamic Programming Model for Problem of m-Dimensional Bottleneck Assignment

The problem of m-dimensional bottleneck assignment is that m persons are assigned to n pieces jobs(m>n)and each person only does one piece of job,here the benefit of someone does some job is known,the aim is how to divide m persons into n groups m-1,m-2,…,m-n,Σj=1m-j=m and let the m-j group to do the j-th job(j=1,2,…n)in order to make the group with the minimum benefit obtain the maximum benefit.In this paper,a dynamic programming model of the m-dimensional bottleneck assignment problem is established;also a suitable solution to this model is given based on golden section rule.Finally,a numerical example is used to illustrate the proposed method.