Algorithm for resource allocation by project (Bin Packing?)

0
votes

Please let me know which algorithm is appropriate for the problem below:

We have a finite number of projects in a given 3 month period (typically < 50). Each project has a number of hours.

We have a finite number of resources (typically < 100) in the same 3 month period.

Each resource can consume a unique amount of hours per month (accounting for holidays, personal vacations, and such-- this number of hours per month is already pre-calculated for each resource and is available).

It is possible to allocate one resource to multiple projects.

This is like a bin packing problem turned on its head, I think, if we consider projects as bins, resources as objects, and hours as object volume. At least two things make it deviate from the formal bin packing problem:

  1. Resources are fluid objects which can drip a few hours in one bin and a few in another.
  2. Optimal solution is not to minimize number of bins (projects) used, but rather to minimize the number of times a resource has to split themselves between projects and ensure all projects are used.

I feel like I might be chasing geese with the bin packing angle. Is there an algorithm that is more appropriate for this?

1
algorithmallocationbin-packing
But what is the actual problem? What is the result you want? An allocation list for resources, saying which resource is allocated by each project for every hour in the 3 month period? Do you want to know if such an allocation is possible, or find a best allocation? If so, what makes an allocation 'best'? – zmbq

1 Answers

1
votes

If the world is truly as simple as you portray it, it seems like a simple queue would satisfy your constraints: as projects arrive, put them on the queue. As developers become available, they take from the head of the queue. Only if you have projects that are large enough not to get completed this way would you ever need to assign more than one developer to them, and you can detect this, and backtrack and assign two developers.

But all of this ignores coordination between developers, handoffs, dependencies (what needs to be done first before something else can be), the fact that competent developers have different skills and experience, and even similarly experienced developers, without being incompetent or superstars, can have up to 10x differences in speed.