Methods for scheduling

Question

I am working on a PHP application for an at home care company. They have x amount of carers that are scheduled every week to attend the houses of x amount of service users (clients). Each service user has a set 'schedule' of when they are to be visited which includes periods plus the visit duration in minutes.

So for example, a service user could have the following schedule.

      AM   Lunch   Tea   Late   Night   Respite
Mon   30m  -       30m   60m    -       -
Tue   30m  -       -     60m    -       -
Wed   20m  25m     30m   60m    120m    -
Thu   -    -       30m   -      -       -
Fri   30m  25m     -     -      -       -
Sat   -    -       -     -      -       -
Sun   20m  25m     -     -      -       -

These periods are currently stored in a database in the following format:

Table: Service_user_schedules
id   service_user_id   day   period   duration

Every week, the carers fill out a table of what periods they are available to work. This data is then input into the system and is stored in the database in the following format:

Table: Carer_available_shifts
id   carer_id   day   period

Now the problem is, I need to create a controller that will take this data and automatically assign carers to service users based on the availability they have supplied. This needs to be editable so that in the event that nobody is available for a particular carer, the user can select one that isn't available and they will still be added to the database.

At the moment, I have a mess of loops, functions and echo's to check if carers are available for a particular service user and to make it editable.

Has anyone performed this sort of task before and if so, did you find a simple way to complete it. I would prefer to make it object orientated so I could reuse the same generic class but at the moment, I'm at a complete loss!

EDIT: I have now added a bounty to this question. I am currently researching genetic algorithms (something that I have never even heard of let alone used!) as a solution to this problem based on some of the answers. I would like to know if any of you have used other methods of solving this type of problem or if you have used genetic algorithms, could you provide a less general explanation on how you applied them to this particular issue.

I would assume that this hurdle would be fairly common in many "staffing" type applications and am surprised at how little discussion there is on this anywhere on the web!

UPDATE

For this particular project, I think I may end up using the database method as described by Tak but may possibly convert to the use of GA's in the future when I have more development time set aside.

I am now at a bit of a loss as to who to award the bounty to. duedl0r put alot of effort into his (or her) answer. It has given me a great insight into the world of Genetic Algorithm's - a problem solving method that I had never come across before. However, the answer provided by Tak provides the solution that I will be using for this project. Therefore, I have awarded the bounty to Tak.

Answer 1

Sounds like the employee shift rostering problem, which is NP-complete.

If you think metaheuristics (such as genetic algorithms, tabu search, simulated annealing, ...) is overkill, then just go for a simple First Fit Decreasing algorithm.

Answer 2

Maybe you can use a genetic algorithm. This has the advantage that you can do really crazy stuff (if you have set up the basics), e.g. you could also say that a carer should optimally visit a service user he used to visit before, or minimize the distance between visits :)

Doing it like that every service user gets a carer even if there is no available schedule. The algorithm just tries to create a optimal solution..

Probably it's a bit overkill, but it's an interesting topic.. :) I wanted to mention it because it may be a new way to tackle your problem. At least worth a thought ;)

Some Links: Genetic Algorithm Resource, Genetic Algorithm Tutorial, Wikipedia

---

Edit: More concrete explanation of genetic algorithms.

A genetic algorithm consists of modelling the theory of evolutionary development. Evolutionary development needs a population of certain creatures. Then you simulate the development of the population using certain biological effects like mutation, selection, crossing etc.. Like darwin found out a few years ago :)

Now you have to map your problem to such a creature (or a DNA). This means every creature represents a solution in your problem space (every DNA is a solution to your problem).

So the phrase "survival of the fittest" just means "I get a solution to my problem which might be optimal" (not guaranteed though).

A mapping from your problem to such a DNA can be done very differently. First you need an array to represent your DNA. You can specify for example this:

You create chunks of 42 elements for every service user (6 slots per day, 7 days a week). Then your first entry in the array is the "AM"/Mon slot for service user 1. Your second entry the "Lunch"/Mon slot for service user 1. Your 43th entry is the "AM"/Mon slot for service user 2. This defines the DNA of your creature. Then you let them hump each other so they can develop :)

In order to find out which creature is well fitted, you also need a formula which calculates the fittness. You create a formula which has a DNA as input and a number as output. This is depending on your rules. For example you can give some plus or minus points if there are certain rules holding or not. If a carer is used for two different service user at the same time you give some minus points, if a carer has actually time for a slot and he is really scheduled for a service user you can give plus points.

You can also say: A genetic algortihm tries to find out how to maximize this formula using a genetic approach.

Very short introduction to genetic algorithms..if you have enough time and if you're also interested in the topic it's really worth digging into it.. you can some really cool stuff with it. But keep in mind, it can get also messy and complicated :)