Over a lunchtime pastie, I was recently browsing my copy of Walkenbach’s Formulas. I found myself looking at the chapter on Intentional Circular References.
Here, JW gives an example of choosing a set of unique random numbers – that is, having chosen a number once, it can not be chosen again. Each random number has an associated COUNTIF formula, which counts occurrences of the associated number; if this is 1 for each number, then we have a solution. In a random-number cell (e.g. A1), we have a formula of the form:
=IF(<no solution>, <new number using RAND>, A1)
These formulas generate candidate solutions at random, until one is found. In >Tools >Options >Calculation (v2003), you need to allow Iteration, and set a sufficient number of Maximum Iterations.
I thought I’d try my own example: allocating resources to a set of tasks (with pre-determined start and finish dates). Here’s the worksheet:
- The task durations are set out with 1 values, in C6:J9 – each column represents a day, with time increasing from left to right
- The allocated resources are identified in A6:A9 (range Alloc)
- The pool of available resources is in A12:A14 (range Resource)
- The resource utilization per-day is calculated in C12:J14, using an array formula (see below), plus some conditional formatting
- The maximum utilization for a resource is calculated in B12:B14 (range Max)
- The maximum of the maxima is calculated in B16 (range Supermax). If this is 1 – that is, no resource is multi-booked for any day – then we have a solution.
The resource utilization in C12, etc, is calculated using the array formula:
That is, the ones in C6:C9 are summed only if the resource in the corresponding row of Alloc matches the one in A12. You can see how the allocations of res2 (in rows 6 and 8 ) are unioned in row 13.
The random-allocation formula in A6 is:
=IF(SuperMax<>1, NewResource, A6)
The reference to Supermax is what creates the circularity.
NewResource is a named formula:
=INDEX(Resource, INT(RAND()*Rescount) + 1)
This generates a random index into the Resource list, whose size is Rescount.
Having found a solution, recalculation just keeps preserving the existing values. To force a new solution, you first have to ‘break’ the existing solution. This is done using the named value Started, in A2. Each of the green cells in C6:J9 has the formula ‘=Started’. Setting Started to zero makes the allocation fail to find a solution (since Supermax can never = 1), leaving Alloc with an arbitrary set of resource ids. Then setting Started = 1 allows a new solution to be found.
I’m not sure how useful this technique would be for realistically sized problems, since it’s basically trying solutions at random. Anyway, here’s the workbook, if you fancy a play.