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

Dynamic Programming Model for Problem of m-Dimensional Bottleneck Assignment

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

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 m1, m2, …, mn ,∑j=1 mj=m and let the mj 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.