Finding a solution to a real world assignment/routing problem

Question

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.

Conditions:

• 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!

Answer 1

HaHa :) its NP-Hard

https://en.wikipedia.org/wiki/Job_shop_scheduling

But your main problem are the humans involved, who will go on holiday, become ill and change shifts at inconvenient times.

Your best bet is to forget about optimal and go for ease of use. Automate the calculations that people do in their heads to work out which job to allocate to whom, eg order lists by distance from last job, make things go red if there aren't enough people to go round, Let the user drag and drop stuff and show travel time etc.

Let the user fiddle and just show them the costs rather than attempt to calculate the optimal and then force them to change it because you cant take into account the human factors

Answer 2

Have you taken a look at genetic / evolutionary algorithms, or simulated annealing? Or ant colony optimization? Or particle swarm optimization?

As @Ewan found, the problem is NP-hard. But as it turns out, many NP-hard problems can be solved with excellent results using these algorithms that only approximate the optimal solution instead of finding the true optimum.

I'm pretty sure you will find some algorithm that finds a genuinely excellent solution to your problem, even if it isn't the optimal solution. It will just require a lot of work. You are not dealing with the simplest of software engineering problems here.

Oh, and depending on the complexity of the problem, you may need to throw a lot of CPUs at the problem and still wait for a long amount of time for the computations to finish. These algorithms differ in how easy they are to parallelize. Simulated annealing is hard to parallelize, whereas genetic and evolutionary algorithms are easy to parallelize.