I have a project where I must map employees to a schedule. The basic concept is:
- Company Opens between 08:30 and 17:00.
- Employee 1 can work from 08:30 to 12:00 then from 13:00 to 1700;
- Employee 2 can work from 12:00 to 13:00.
- Employee 3 can work from 17:30 to 00:00
I would then want the employees mapped to the company object based on when they can work. So if I require one employee on at all times, in the example above Employee 1 and 2 would be working on that day.
I’ve got a couple of ideas in my head on how to approach this but wanted to check to see if there are any algorithms designed around this kind of task.
3
This is written from the pragmatic point of view. Don’t reinvent the wheel. You are better off learning and using a known piece of software than writing your own scheduling program that likely won’t preform as well and will be ‘fun’ to maintain – both for you and the next guy.
Scheduling problems are hard… and not just hard, but they can often be NP-hard. The problem described is a modification of the nurse scheduling problem which is a classic one that has been studied for several decades because of its difficulty.
If one wants to try to code it oneself, there are a number of techniques. Those mentioned in the wikipedia article include decomposition, parallel computing, stochastic optimization, genetic algorithms, colony optimization, simulated annealing, Tabu search, and coordinated descent.
I should also point out that there is an entire industry of software programs around the nurse scheduling program. A search for nurse scheduling software turns up numerous results from different companies.
All of these fall into the area of constraint programming, and while one could sit down with prolog (or write your own), this tends to be the area where one would grab a rules engine appropriate to your platform and let it do the work. One such example is that of drools, which has an example of employe shift rostering using nurses (there are some other examples too including patient admission schedule, exam timetabling, and a traveling tournament problem).
Brute force may not be feasible for even small datasets.
I have written something like this in my beginnings, in C#. I used a genetic algorithm.
The source code (hosted at Codeplex) is awful, I didn’t know any better at the time. But you can take a look at the video presentation: http://vimeo.com/20610875
I start talking about the subject of your interest around 6:00.
Personally I got the idea from http://mkweb.bcgsc.ca/carpalx/?simulated_annealing which is an interesting read. Nevermind the math, you can ignore it.
The solution yields really good results, as demonstrated in my video.