Generalized assignment problem: Difference between revisions

Revision as of 21:03, 16 April 2007

Revision as of 14:34, 6 May 2007

Line 1:

TheIn economics, the maximum '''general assignment problem''' is a problem in [[combinatorial optimization]]. This problem is a [[generalization]] of the assignment problem in which both [[task]] and [[agents]] have a size. Moreover, thisthe size of each task might vary from one agent to the other.

This problem in its most general form, the problem is as follows:

There are a number of agents and a number of tasks. 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 task 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.