Published on November 25th, 2013 | by Emily Corbett0
The Puzzle That Runs A Factory
By Simon Bowly, Monash University
This student took part in the 2012/13 AMSI Vacation Research Scholarship program. For more information on this years program please click here
Let’s say you’re in charge of a factory. You have a certain number machines for specific tasks and workers who are needed to complete your production. It turns out a simple sounding maths puzzle can be used to make the best use of your available workers and complete production in the shortest time.
This puzzle is called Graph Colouring. A graph is a series of nodes, which in our factory represent tasks, and edges which connect them. An edge connects two nodes if the tasks they represent require the same person or piece of machinery to complete.
In Graph Colouring, every node is assigned a colour, such that any two nodes connected by an edge do not have the same colour. For our factory, colouring the graphs in this way ensures no one has to do two tasks at once. Each colour represents a time slot, so our aim is to use as few colours as possible, so production is completed in the shortest time.
This sounds like an extremely simple problem in principle, but it is among a class of problems in computational mathematics called NP-complete. This means that the only sure way to find the best solution to a graph colouring problem is to check every possible solution.
To get around this, there are a number of fast algorithms called heuristics which are guaranteed to find a solution (not necessarily the best solution) in reasonable time. The challenge then is to decide which heuristic is the best one to use for the problem you have to solve.
To help decide this, we need a useful body of data against which we can compare a new graph. We classify these graphs based on their features, some easy to calculate values which quickly tells which graphs in our body of data are the closest matches.
Generating this body of data is an interesting task: it has been found that simply generating random graphs does not produce enough graphs which really challenge the available heuristics. So we turned to a biologically inspired process called a Genetic Algorithm. All a Genetic Algorithm needs is a way to measure how ‘fit’ a graph is (how well it suits our purposes), and a way to breed new instances from old ones, and we can let nature run its course.
If defined properly, eventually the genetic algorithm evolves graphs with the properties we want. Most of this hinges on the fitness function. In the case of this project, the fitness function compares the performance of two heuristics on the same graph, giving a higher score to graphs which are hard for one heuristic. The scores are also weighted by target values of the graph features we want to explore.
The result is a group of graphs with a wide range of features which challenge the capabilities of the heuristics we’re testing. With this data available, any new graph colouring problem can simply be compared to the known graphs, which tells us which heuristic to use for the best result.
Thanks to Graph Colouring, things will be running smoothly in no time!