|
Registro Completo |
|
Biblioteca(s): |
Embrapa Agricultura Digital. |
|
Data corrente: |
21/08/1996 |
|
Data da última atualização: |
12/03/2019 |
|
Autoria: |
LORENA, L. A. N.; NARCISO, M. G. |
|
Afiliação: |
LUIZ ANTONIO N. LORENA, INPE; MARCELO GONCALVES NARCISO, Inpe. |
|
Título: |
Relaxation heuristics for a generalized assigment problem. |
|
Ano de publicação: |
1996 |
|
Fonte/Imprenta: |
European Journal of Operational Research, Amsterdam, v. 91, n. 3, p. 600-610, 1996. |
|
Idioma: |
Inglês |
|
Conteúdo: |
We 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 polynominal time. Relaxation multipliers are used with an improved heuristic of Martello and Toth or a new constructive heuristic to find good feasible solutions. Six heuristics are tested with problems of the literature and random generated problems. Best results are less than 0.5% from the optimal, with reasonable computational times for an AT/386 computer. It seems promising even for problems with correlated coefficients. |
|
Palavras-Chave: |
Generalized assignment problem; Heurística; Heuristics; Lagrangian and surrogate relaxation. |
|
Categoria do assunto: |
-- |
|
Marc: |
LEADER 01603naa a2200181 a 4500
001 1003254
005 2019-03-12
008 1996 bl uuuu u00u1 u #d
100 1 $aLORENA, L. A. N.
245 $aRelaxation heuristics for a generalized assigment problem.$h[electronic resource]
260 $c1996
520 $aWe 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 polynominal time. Relaxation multipliers are used with an improved heuristic of Martello and Toth or a new constructive heuristic to find good feasible solutions. Six heuristics are tested with problems of the literature and random generated problems. Best results are less than 0.5% from the optimal, with reasonable computational times for an AT/386 computer. It seems promising even for problems with correlated coefficients.
653 $aGeneralized assignment problem
653 $aHeurística
653 $aHeuristics
653 $aLagrangian and surrogate relaxation
700 1 $aNARCISO, M. G.
773 $tEuropean Journal of Operational Research, Amsterdam$gv. 91, n. 3, p. 600-610, 1996.
Download
Esconder MarcMostrar Marc Completo |
|
Registro original: |
Embrapa Agricultura Digital (CNPTIA) |
|
