Generalized assignment problem: Difference between revisions

Revision as of 22:04, 29 October 2014

Revision as of 13:53, 24 April 2015

Line 3:

This problem in its most general form is as follows:

There are a number of agents "n" and a number of tasks "m". Any agent can be assigned to perform any task, incurring some cost and profit that may vary depending on the agent-task assignment. Moreover, each agent has a budget and the sum of the costs of tasks assigned to it cannot exceed this budget. It is required to find an assignment in which all agents do not exceed their budget and total profit of the assignment is maximized.

==Special cases==

In the special case in which all the agents' budgets and all tasks' costs are equal to 1, this problem reduces to the maximum [[assignment problem]]. When the costs and profits of all agents-task assignment are equal, this problem reduces to the multiple knapsack problem. If there is a single agent, then, this problem reduces to the [[Knapsack problem]].

==Definition==