haku: @indexterm assignment problem / yhteensä: 21
viite: 7 / 21
Tekijä: | Lorena, L. Narciso |
Otsikko: | Relaxation heuristics for a generalized assignment problem |
Lehti: | European Journal of Operational Research
1996 : JUN 21, VOL. 91:3, p. 600-610 |
Asiasana: | OPERATIONAL RESEARCH HEURISTIC METHODS ASSIGNMENT PROBLEM |
Kieli: | eng |
Tiivistelmä: | The authors propose relaxation heuristics for the problem of maximum profit assignment of n tasks to m agents (n>m), such that each task is assigned to only one agent subject to capacity constraints on the agents. Using Lagrangian or surrogate relaxation, the heuristics perform a subgradient search obtaining feasible solutions. Relaxation considers a vector of multipliers for the capacity constraints. The resolution of the Lagrangian is then immediate. For the surrogate, the resulting problem is a multiple choice knapsack that is again relaxed for continuous values of the variables and solved in polynomial time. |
SCIMA