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.
I'd approach it like this. First a database table that links schedule slots to available carers...
Table schedules_shifts
id 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?