Archive for August, 2010

Intentional Circular References

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.


Navigating Part Relationships – 2

In the previous post, I introduced the idea of a cursor object that allows you to navigate around a graph of component-part relationships:

Navigation could be:

  • down the ‘contains’ relationships
  • along the ‘used in’ relationships
  • back through the history of visited records.

We’ll also have a Reset operation, which jumps back to the start of the table, and clears the history.

The navigation is done using keyboard shortcuts (but could be done via a form).

The core of the design is a Class Module GraphCursor. This provides our four operations: CursorDown, CursorNextUse, CursorBack and CursorReset. When an instance of this class initializes, it points itself at ListObjects(1) on the ActiveSheet (there is only one sheet, to keep things simple), and does a CursorReset.

A GraphCursor maintains a history of visted components using a linked List class (a simple chain of ListItem objects – nothing to do with ListObject a.k.a. Table).

CursorDown and CursorNextUse use Range.Find with the currently selected cell value. I assume this is pretty efficient – and in any case is neater in code terms than iterating through rows explicitly. The Range for CursorDown is just the first column (Component); the Range for CursorNextUse is the Part columns below the row of the current selection.

Something needs to create and hold on to an instance of GraphCursor – this is a standard module Client. This also provides procedures that are called via the keyboard shortcuts.

Public gc As New GraphCursor

Sub GCDown()
End Sub

'similarly for the other three operations

The keyboard shortcuts are set up on Workbook_Open:

Private Sub Workbook_Open()
    Application.OnKey "^+d", "GCDown"
    Application.OnKey "^+n", "GCNextUse"
    Application.OnKey "^+r", "GCReset"
    Application.OnKey "^+b", "GCBack"

End Sub

Here’s the workbook (Excel 2007).

Since each navigation step is worked out dynamically, we can insert or delete records from our table as we like. This would not be the case for an indexed solution (maintaining a map of Component to row number).

You could argue that each Component-Part relationship should be a separate record – for example, [A, B], [A, C]. This would allow us to associate quantities or other information with each relationship. In this case, we would also need a CursorNextPart operation.

Navigating Part Relationships

This is something I was thinking about before a short holiday break (Strasbourg – very pretty) …

Suppose that we have an inventory of Components, perhaps in a manufacturing or engineering context. For each Component, we record its Parts (that is, sub-components). For example:

Sorry, my creativity did not extend to dreaming up meaningful data – think of car parts, or something.

So, an A is a top-level component, and consists of Bs and Cs (we do not specify quantities – an issue deferred); a B consists of Fs and Gs; E, G and H are elementary components (indicated by underscore). A component, such as B or H, can be used by multiple higher-level components. The restriction to 3 part types per component is just for simplicity.

These relationships form a directed, acyclic graph (there are top-level and bottom-level components, and no component can contain itself directly or indirectly).

Even with a very simple example, like above, it is quite difficult to see what contains what. With a realistically large inventory, say hundreds or thousands of records, it would be next to impossible.

One solution would be to support navigation around the graph of relationships:

  • Drill-down the ‘contains’ relationship: for example, [A contains B, C] >>> [B contains F, G] >>> [F contains H] >>> [H is elementary]
  • Move along the ‘used in’ relationship: for example, [B used in A] >>> [B used in D] >>> [no more uses of B]

Moving along the ‘used in’ relationship for ‘_’ (underscore) takes us through all the elementary components.

When you get the end of a ‘used in’ chain, you could have the option to start again from the beginning (as in textual searches):

In addition, we could have navigation ‘back’ through the sequence of visited Components.

We could offer these operations and the resulting ‘current record’ to a user via a form. However, it seems more lightweight to use keyboard shortcuts.

So, how might we do this? As previous postings have illustrated, I like the idea of a cursor object, which provides move operations of some kind, and access to the ‘current record’. In this case, the cursor position will be indicated visibly to the user by explicitly Selecting the relevant cell (and thus scrolling to the record).

An instance of the cursor object can be created on Workbook_Open, and linked on Class_Initialize to a the table. For simplicity, let’s assume that we have a single worksheet with a single table. As usual, there are advantages to using a v2007 Table (in VBA a ListObject), but you could get it to work in v2003.

More on the design/code in the next posting.

August 2010
« Jul   Sep »