کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418195 | 681617 | 2015 | 7 صفحه PDF | دانلود رایگان |
In this paper the resource dependent assignment problem (RDAP) is considered. In the RDAP the cost of assigning agent jj to task ii is a multiplication of task ii’s cost parameter by a cost function of agent jj and the cost function of agent jj is a linear function of the amount of resource allocated to the agent. A solution for the RDAP 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 one is the total weighted resource consumption. Yedidsion et al. showed that the bicriteria variations of the problem are all NPNP-hard for any given set of task costs. However, whether these problems are strongly or ordinarily NPNP-hard remained an open question. In this paper we close this gap by providing pseudo-polynomial time algorithms for solving these problems.
Journal: Discrete Applied Mathematics - Volume 182, 19 February 2015, Pages 115–121