Methods for scheduling

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.

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

I'd approach it like this. First a database table that links schedule slots to available carers...

Table schedules_shiftsid   service_user_schedules_id   carer_available_shifts_id

Now a function that matches available carers to required schedule slots and populates the table...

* Fetch service_user_schedules for the next week* For each service_user_schedules row * Fetch carer_available_shifts that match the schedule slot * For each carer_available_shift row  * If results   * Fetch schedules_shifts rows where carer_available_shifts_id is already used   * If no results    * Insert a row in the schedules_shifts table for each carer   * Otherwise carer is busy, do nothing and continue  * If no results, flag for review or trigger e-mail to manager, or other action* Trigger e-mail or save log of completion for peace of mind

The new table now has possible carer matches for schedule slots with no duplicate allocation of a carer's time. It does however match multiple carer's shifts with a schedule slot. This could be a feature! Leave them as-is and add a confirmed column on schedules_shifts so a manager can manually assign the work, or carers can volunteer, or automatically mark the first match as confirmed and keep the other rows as alternatives in case the first carer can't make it.

This can all be triggered by a cron every week, or when the final career updates their week's schedule. Probably the first because users are often unpredictable.

Now the automated data is in a table you can open it up for editing. Create a normal admin console as you would to change the rows in schedules_shifts as appropriate, or flag different rows "confirmed".

Translating it into a generic class shouldn't be too difficult - just a matter of using generic terminology. It's late and I can't think of any though :)

It's possible to do all the data sifting in PHP arrays rather than the database dance I've created above, but I think SQL is more appropriate for sorting through the data and making amendments.

Genetic algorithms sound interesting though, and if you've got the time investigate them ^_^

Hope that helps?