4

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.

  • 1
    I recommend sharing what you have so far. That tends to be more productive: we can see what you have done and identify areas of improvement. – user22815 Sep 26 '14 at 23:29
  • 4
    You are describing the nurse scheduling problem with a different set of constraints. This is a rather well known (and difficult) problem. There is an entire industry around this problem. Typically one uses a rules engine and lets it do the work rather than trying to write it oneself. – user40980 Sep 27 '14 at 0:05
  • @MichaelT - That's what I was after, could you mark it as the answer please. I thought there would be some general information about the problem. Thanks. – webnoob Sep 27 '14 at 8:01
5

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).

2

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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