Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

This is more of mathematical question than an algorithmic one; nevertheless it will be implemented in php.

I have an array of N tasks. Each task has taken t time to complete(e.g. task 1 has taken 5 hours to complete.) Now, in order to review that these tasks were completed correctly, I have to assign a certain number of users U to review each of them. Each user will be assigned a certain number of tasks, ideally, with each user having roughly the same amount of hours assigned as the other.

E.G. There are 10 tasks. task 1 took 4 hours, task 2 took 18 hours, task 3 took 6 hours...etc... totaling 80 hours.

There are 8 users. If each of the 8 users is to ideally have the same amount of hours (some users get more, yet less lengthier tasks, some users get less, yet lengthier tasks), what is a good way to automatically sort assign the tasks?

share|improve this question

migrated from stackoverflow.com Feb 7 '12 at 19:03

This question came from our site for professional and enthusiast programmers.

2  
You need to look in to Knapsack Algorithms. –  Will Hartung Feb 7 '12 at 18:43
1  
@Mchl: belongs in a closevote –  Lightness Races in Orbit Feb 7 '12 at 18:45
    
As the implementation isn't relevant to the question at hand, I vote to close this as off-topic, but relating to Mathematics. It could use a bit of rewording too. After @John understands the algorithm involved, he can take some time to mess around in code, and ask questions specifically related to the code involved on Stack Overflow. –  zzzzBov Feb 7 '12 at 18:48
    
If the problem you are talking about is actually servers doing any amount of distributed work, I would let them 'pull' tasks rather then 'push' tasks. Requires polling after every single task to get the next one, and no 'queue' at the users end. It would however not necessarily mean every server does the same amount of work, just probably as fast as can be done. Disregard this comment is you really need a fair distribution ;) –  Wrikken Feb 7 '12 at 18:52
    
To complete your description, you need to specify: How many users could review a given task (min, max). –  Emmad Kareem Feb 7 '12 at 21:14

3 Answers 3

The algorithm shown below provides a solution. I have not tested it throughly, but it should give you an idea. It could only be used only if the sum(resources available time) >= sum(required task review time).

The process starts by examining Task1's required review time and resource 1 availalble time. If the available time is less than or equal the time required by the task, the intersection cell of T1, U1 is filled with the the number of hours that would either fulfill the required review time or the available time for user 1.

Next, we go to task 2 and repeat the process.

If the allocation exhausts a given resource's available time, logic moves to the next resource.

The iterations should stop when this condition is violated or when all resources have been allocated.

In the image below, step 0 is the initial step. I have used an Orange color to show the changes at each step, hoping you can discover the process.

Note:

This process is biased to the way users are listed from left to right and does not distribute work evenly across users. That is, one user may work harder than the rest just because he/she appears before the others.

enter image description here

share|improve this answer

This is an instance of the open shop scheduling problem. The problem is NP-complete, so you'll want to apply some heuristic, such as the one described in the Wikipedia or perhaps one of the genetic algorithms in this paper.

share|improve this answer

Perhaps you may be over-thinking this. Arrange tasks in a simple queue and order according to priority. Having each user take the first task available should be enough. Longer tasks might take longer to review, and short ones less time, therefore the order in which users appear to collect the next task will change as they finish the previous task and come forward for the next. This doesn't really need to be too complicated.

Pre-allocating tasks can have some serious drawbacks. This is basically a push system, and it tends to result in "waste" more often than not. Implementing a pull system would be much more efficient, and less wasteful in terms of scheduling and resources, as you won't end up needing to manage synchronization issues if work estimates are either wrong, or become interrupted by changing circumstances within the team.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.