How to optimize assignment of tasks to agents with

Question

I have an assignment problem as a part of my Master's Thesis, and I am looking for general direction in solving the same.

So, there is a list of agents, and a list of tasks, with number of tasks being greater than the number of agents.

The agents submit a prioritized ordered list of tasks they can/want to do. The length of the list is fixed to a number much smaller than the total number of tasks.

Every agent must be assigned a task. A task once assigned cannot be assigned to another agent.

The objective is to find an assignment such that the average priority/preference of the assigned tasks is the lowest. Additionally, if it is complete solution i.e. every agent is assigned a task, it is even better.

I have looked at the generalized assignment problems, and the Hungarian algorithm, but these do not cater to the specific situation where there is a cost to a task and also the possibility of the agent being unable to do some of the tasks.

Please help. Thank you.

Answer 1

If you want a general approach, you can model the problem as Mixed Integer Program, introducing binary variables for the assignment of tasks to agents and putting the priority costs and (very high) non-assignment costs into the objective function. Mixed Integer Programs can be solved using a variety of solver programs, including CPLEX or Gurobi which are free for academic purposes.