The Resource Dependent Assignment Problem and Its Applications in Scheduling
Professor Dvir Shabtay, Ben Gurion University of Negev, Israel
23rd Aug 2013 11:00 am - Room 498 Merewether Building H04
We extend the classical linear assignment problem to the case where the cost of assigning agent j to task i is a multiplication of task i's cost parameter by a cost function of agent j. The cost function of agent j is a either a linear or a convex function of the amount of resource allocated to the agent. 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. For both assignment cost function (linear and convex) we obtained similar results (also the analysis is completely different). For both functions, we prove that (i) our assignment problem is NP-hard for three of the four variations even if all the resource consumption weights are equal and that (ii) the fourth variation is solvable in polynomial time. For the linear assignment cost function, we also provide a pseudo polynomial time algorithm to solve the NP-hard variations. In addition, we find that our assignment problem is equivalent to a large set of important scheduling problems whose complexity has heretofore been an open question for three of the four variations.