Assignment problems deal with the question of how to assign a set of n agents to a set of n tasks such that each task is performed only once and each agent is assigned to a single task so as to minimize a specific predefined objective.
In this research we define and analyze a special kind of assignment problem where the cost of assigning agent j to task i is not a constant cost but rather a function of the amount of resource allocated to this particular task.
The resources are continuous and non-renewable, such as additional money, overtime, energy, fuel, catalysts, subcontracting, and additional manpower, to the job operations. We assume the resource consumption function to be convex in order to ensure the law of diminishing marginal returns. The amount of resource allocated to each task is a continuous decision variable.
A solution for our assignment problem is defined by the assignment of agents to tasks and by a resource allocation to each agent. The quality of a solution is measured by two criteria. The first criterion is the total assignment cost and the second is the total weighted resource consumption. We address these criteria via four different problem variations. The first is the minimization of a combined cost function of the two criteria; the second is the minimization of the assignment cost under a limitation of total resource consumption; the third is the minimization of the total resource consumption under a limitation of the assignment cost and the fourth problem is to construct the trade-off curve between assignment cost and total resource consumption. It should be noted that a solution for the fourth problem variation provides a solution for the first three variations as a byproduct.
It was proven that the first problem variation can be solved polynomially whereas the three remaining variations are all NP-hard. In this research we provide a ρ-approximation algorithm to solve the second problem variation, where a ρ-approximation algorithm is an algorithm that runs in polynomial time and produces a solution with cost within a factor of at most ρ of the optimal solution.
The approximation algorithm is based on the solution method for the first, polynomial, problem variation. In this variation, the solution is a function of the ratio of the weights given to each criterion. Moreover, each such solution is a Pareto optimal solution and is a one-one correspondence function of the total resource and the assignment cost. Accordingly, we use the well-known bisection method on the value of this ratio to try and find an efficient solution in which the total resource consumption is not greater than but as close as possible to the total resource limitation.
We prove that this method is a ρ-approximation algorithm. However, ρ itself is a function of one of the problems parameters, denoted by k. This parameter defines the resource's efficiency and according to literature is usually confined within 0.5<k<2. For this range our approximation ratio is in fact confined within 1.17< ρ<1.62.
