Data/hora: 08/06/2024 09:57:52

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: 	--	
Registro original: 	Embrapa Agricultura Digital (CNPTIA)	
Exemplares: 	CNPTIA - (3890-1) - ADD - SP - PP -  -  - 1996.00088 - DES
CNPTIA - (3890-2) - ADD - AP - DD -  -  -  - DIS