A SURVEY OF ALGORITHMS FOR THE GENERALIZED ASSIGNMENT PROBLEM
A SURVEY OF ALGORITHMS FOR THE GENERALIZED ASSIGNMENT PROBLEM
复制标题
DOI：
10.1016/0377-2217(92)90077-m
复制
发表时间：
1992-08-10
影响因子：
6.4
通讯作者：
VANWASSENHOVE, LN
中科院分区：
文献类型：
--
作者：
CATTRYSSE, DG;VANWASSENHOVE, LN
本文调查算法的知名问题，找到最低成本的工作分配给代理，使每个工作被分配一次，代理不超载。所有的方法似乎都是基于分支定界法，并通过简化和放松原始问题的表述来提供边界。从调查中，人们可以选择构建模块来设计自己的定制算法。调查还显示，虽然几乎每一个数学规划技术尝试在这个问题上，仍然缺乏一组有代表性的测试问题，竞争枚举算法可以比较，以及缺乏有效的算法。
This paper surveys algorithms for the well-known problem of finding the minimum cost assignment of jobs to agents so that each job is assigned exactly once and agents are not overloaded. All approaches seem to bc based on branch-and-bound with bounds supplied through heuristics and through relaxations of the primal problem formulation. From the survey one can select building blocks for the design of one's own tailor-made algorithm. The survey also reveals that although just about every mathematical programming technique was tried on this problem, there is still a lack of a representative set of test problems on which competing enumeration algorithms can be compared, as well as a shortage of effective heuristics.