Relaxation heuristics for a generalized assignment problem

Relaxation heuristics for a generalized assignment problem

0.00 Avg rating0 Votes
Article ID: iaor1999329
Country: Netherlands
Volume: 91
Issue: 3
Start Page Number: 600
End Page Number: 610
Publication Date: Jun 1996
Journal: European Journal of Operational Research
Authors: ,
Keywords: programming: assignment
Abstract:

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 polynomial 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. Bests 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.

Reviews

Required fields are marked *. Your email address will not be published.