logo
Welcome Guest! To enable all features please Login or Register.

Notification

Icon
Error

Options
Go to last post Go to first unread
Offline MrChumble  
#1 Posted : 11 October 2014 12:22:25(UTC)
MrChumble
Rank: Full Duplex

Joined: 17/04/2011(UTC)
Posts: 872

Thanks: 62 times
Was thanked: 44 time(s) in 32 post(s)
This is properly random, but is anyone good at maths/algorithm type problems and able to suggest an approach for this? High level is fine, I can go research it if given some pointers. I know Lok loves maths - must be some others :)

I'm trying to write an algorithm that assigns work to people based on their skill sets.

Say for example there are two people, Bob and Carol, and two tasks, A & B

Bob can do A & B
Carol can only do A

In any given day they can complete three tasks each.

There are six tasks to be done:

A (oldest)
A
A
B
B
B (newest)

What I need to do is work out the optimal way to allocate work such that as many tasks as possible are allocated, and older tasks are allocated in preference to newer ones.

In this simple example I'd have to ensure Carol gets all the A and Carol all the B - it's simple to solve by inspection. However the real data set has over 40 people and ~200 tasks (many of which may not need to be completed on any given day). Efficiency is also critical due to geriatric hardware/network.

Offline Loknár  
#2 Posted : 11 October 2014 13:06:49(UTC)
Loknár
Rank: Gangsta

Joined: 27/08/2007(UTC)
Posts: 504
Location: Finland

Was thanked: 2 time(s) in 2 post(s)
A general approach would be to build an integer linear programming model of the problem. Your problem description is vague and ambiguous but at quick glance such an approach would be feasible here. If you need help building the model then you need to post an exact problem description.

The integer linear programming model can then be solved by known algorithms, such as LP-relaxation with Simplex algorithm (there are free high quality implementations, such as lp_solve, available for many platforms). Compared to specialized algorithms this may not be the most efficient solution (solving integer linear programming problem is NP-hard) but it is easy to set up and to make changes to the model and add new constraints etc. This is because the modified model can be solved by the same solver without any changes needed to the solver itself. On larger problems the performance may become an issue but 40 people and 200 tasks is still a small problem.
Offline Sgbnemesis  
#3 Posted : 12 October 2014 04:08:35(UTC)
Sgbnemesis
Rank: Hippie

Man
China
Joined: 11/04/2007(UTC)
Posts: 398
Location: Shenzhen, China

Thanks: 3 times
Was thanked: 8 time(s) in 7 post(s)
Fire Carol & increase Bobs paycheck for the extra workload.

Less Maths, More win.
UserPostedImage
Offline Loknár  
#4 Posted : 13 October 2014 18:04:15(UTC)
Loknár
Rank: Gangsta

Joined: 27/08/2007(UTC)
Posts: 504
Location: Finland

Was thanked: 2 time(s) in 2 post(s)
As per my discussion with Chumble, here is quick description about how to construct a model for the problem, enclosed in a PDF file due to the lack of proper support for mathematical text on the forums. As it was quickly written I take no responsibility for any possible errors! (I would have attached it to the post here on the forums but for some reason that option is only available on some subforums)
Offline MrChumble  
#5 Posted : 13 October 2014 19:40:44(UTC)
MrChumble
Rank: Full Duplex

Joined: 17/04/2011(UTC)
Posts: 872

Thanks: 62 times
Was thanked: 44 time(s) in 32 post(s)
I am suitably impressed. Confused, but impressed :)
Users browsing this topic
OceanSpiders 2.0
Similar Topics
Fun maths problem for 8 year olds (Technical Issues and Geeky Stuff)
by MrChumble 20/05/2015 19:57:57(UTC)
Forum Jump  
You cannot post new topics in this forum.
You cannot reply to topics in this forum.
You cannot delete your posts in this forum.
You cannot edit your posts in this forum.
You cannot create polls in this forum.
You cannot vote in polls in this forum.

Privacy Policy | MO Pink Theme Modded By Tyf (Mystical Odour)
Powered by YAF.NET | YAF.NET © 2003-2021, Yet Another Forum.NET
This page was generated in 0.417 seconds.