Is there an algorithm for the AssignmentProblem where not every task can be performed by every agent and some tasks are more important than others?

Question

My problem is very similar to the Assignment problem (http://en.wikipedia.org/wiki/Assignment_problem), with three exceptions:

1. Not every task can be performed by every agent.
2. Some tasks are more important than other tasks.
3. There is definitely a possibility that not every task will be fulfilled.

The real world story behind this is a fire department running on volunteers. Throughout the day volunteers can say they are available or not and we have to re-evaluate if every task is sufficiently filled. If not someone needs to be notified that there is a problem. We already want to notify if we only have the minimum amount. Generally, a small fire department usually needs to have a leader, a driver, and 4 regular firemen available at all times.

Translating this to the assignment problem, we say that the leader, driver, fireman are tasks and every fireman is an agent. What we want to do is find out if there is a problem (i.e. we don't have 2 possible leaders, 2 possible drivers, and 5 regular firemen), how big the problem is (i.e. we have the minimum amount, or we are in trouble) and where the problem is (i.e. we need another fireman or we need another leader, where needing another leader is more important than needing another fireman).

So what we want to do is given a set of tasks and a set of agents that each can perform a variable set of tasks, divide the agents so that every task is fulfilled OR the most important tasks are fulfilled.

Where the algorithms that solve the assignment problem that I've checked out end up going wrong is in the situation where you don't have enough people to fulfill all tasks. They then seem to get assigned to the lower priority tasks, where it would have been 'better' to have them on higher priority task.

Does this sound familiar to anyone? Is there maybe a name for this problem that I have missed in all the different variations I've looked at? Or does someone maybe have a brilliant idea on how to solve this efficiently?

Answer 1

You can basically use a greedy algorithm that schedules the highest priority tasks first. I would do something like:

• Take highest priority task
• For each agent who can do this task, determine what other as-yet-unassigned tasks they can do ("capabilities")
• If an agent has no other capabilities, assign them to this task
• Otherwise [all agents have other capabilities] count how many other as-yet-unscheduled agents also have those other capabilities
• Select the resource who has the most "duplicated" effort for their other capabilities
• Repeat for next highest priority task

So for a specific example, suppose you have 5 agents as follows:

A - leader, fireman
B - leader, driver
C - driver, fireman
D - fireman
E - fireman

Your highest priority task is leader, so select agents A and B. A can also do "fireman" which is duplicated by 3 others, and B can also do "driver" which is duplicated by 1 other. So the agent with the most duplicated tasks is A, and A gets assigned to leader.

Next highest task is driver. B can only do "driver" because leader has already been assigned, so B gets driver.

Etc.

This is a bit brute force and I'm sure there are edge cases it doesn't catch, but at least it's an approach that is usable...