haku: @indexterm heuristic methods / yhteensä: 556
viite: 109 / 556
| 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