I'm currently working with a window cleaning company that uses it's own set of heuristics for scheduling its small set of cleaners for jobs - basically a huge spreadsheet with dates and human assigned area codes. I've stupidly said that it can be done better.
- Jobs have a 'last cleaned' date and a regularity of which they are cleaned (monthly, every two months, ..., every six months). This gives a window of time when they must next be cleaned (their scheduled date).
- Jobs must be completed within 3 days +/- of their scheduled date.
- Jobs have an associated cost of doing the work, which roughly translates to the time it takes to complete the job.
Overall the task is to minimise the time taken between jobs for multiple cleaners, whilst making sure that all jobs are eventually cleaned within the conditions above.
The company is already in operation, with customers scheduled to be cleaned. I would like to be able to use a method that slowly coaxes the scheduling of cleans towards optimal (i.e. taking jobs early/late so as to better fit an optimal schedule) as enforcing it from the start would disrupt their operation.
I've been looking at Google's Optimisation Tools for hints. It's similar to a Vehicle Routing Problem, but it's difficult to know which jobs should be chosen to be part of the route on a particular day. If the jobs are sorted by scheduled date and then popped from the queue the system will never get any better than it was before.
Any pointers towards further reading or proposed methods would be greatly appreciated!