In my first year of system development, we were discussing whether it would be possible to create an algorithm for page layout in news papers, and particularily placing ads inbetween journalistic content. Ad space was sold for a specified section of the publication, like going in "sports pages", "news section", etc.. The journalistic content varied from day to day, so you would not know the exact resulting size before layout was finished. Just imagining the number of possible combinations made us dizzy, and we all thought this would be an undoable task. No attempt was made.
Few years later I saw this post in one of my regular my usenet groups; a guy was asked by his employer if he could write a piece of software to plan best utilisation of their machinery. There would exist a number of machines (that would all accomplish all types of tasks), there would be a task list, some absolute requirements and some factors to measure best utilisation:
- Whenever a new, different job was initiated, setting up machine would take some 20 minutes.
- All tasks would have to be finished by the end of each 8-hour shift
- Some tasks would gain from earlier completion
- Outcome would be measured by maximum utilisation (hence, earliest completion) adjusted by to which degree the urgent tasks were finished early.
A similar problem to the previous problem of automatic page layout, you soon realise that the algoritm itself would either have to check a huge number of different combinations (effectively limiting the number of managable items), or do complex calculations to limit the set combinations to do only the sensible ones. It could remind of the classical Travelling Salesman's Problem (although one could argue that this is quite near solved through e.g. Google Maps, they sometimes produce silly results like telling you to go an extra round in a roundabout).
It struck me: "Do randomisation!"
The big problem with testing a huge number of combinations is if you start working your way through all possible permutations - it may take just too long and your best combination may be amongst the very last ones. Randomisation helps you avoid this, as picking one of the last permutation combinations would actually soon happen.
Random picking would not be a good concept for determining the ideal combination, but you could end up with a pretty good combination within a fraction of the time.
There is of course one requirement when doing a maxim utilisation calculation regardless of method: A way to rate results, so you can pick the best one.
Take a simpler example, an algorithm for buying planks from the timber store with lowest possible waste. Specifying a list of required lengths and input lengths actually found at the shop and suggest a good selection and instruction to what piece to cut from which plank.
If you only need a few pieces, you could actually test all combinations. But - with e.g. 10 different piece lengths to cut from 6 planks, there would be some 2,3 billion combinations to test:
Required lengths (mm): 2450, 2300, 2200, 2000, 1350, 1100, 1000, 980, 750, 550
Lengths found at store (mm): 4230, 4119, 3860, 3720, 3650, 2470
Permutations of planks / pieces could be:
Planks: 4230, 4119, 3860, 3720, 3650, 2470
Pieces:
- 2450, 2300, 2200, 2000, 1350, 1100, 1000, 980, 750, 550
- 2450, 2200, 2300, 2000, 1350, 1100, 1000, 980, 750, 550
- 2450, 2000, 2300, 2200, 1350, 1100, 1000, 980, 750, 550
- 2450, 1350, 2000, 2300, 2200, 1100, 1000, 980, 750, 550
...etc, all 3,628,800 possible combinations before permutating plank order and repeat the whole process.
Now, the problem could be that this particular order of permutations would leave the possibly sensible choice, using the 2470mm plank for the 2450mm piece, not to appear until the last ~1% of permutations. Testing a random sequence would statistically make this combination appear every 30 attempt, ruling out the problem.
The downside with doing random tests is that you probably wouldn't find the ideal combination, as you have no way to test them all - unless you create a list of all possible combinations and pick tests in random order until they're all tested. But that's another algorithm - this one is about getting a fair result within an acceptable time frame.
A JavaScript implementation of this example will be published soon