Premise and Conclusion

Best-Fit Decision Points ~ How They Fit into the Business Rule Approach

by Ronald G. Ross

The business rule approach generally assumes immediate enforcement of rules.  However, conducting allocation on that basis -- i.e., allocating one instance at a time immediately as they become available -- often produces far-from-optimal results from a business perspective.  Fortunately, commercial inference engines offer special (and powerful) rule-based capability to optimize such allocations.  The nature of such 'best fit' problems is the subject of this month's column.

Allocation problems of all kinds generally involve two or more sets of instances that must be matched in optimal fashion ('best fit').  Allocation problems often appear in process or workflow models as a special kind of decision point, called best-fit decision points.

By default, the business rule approach generally assumes immediate enforcement of rules.  However, allocation of instances in real time (i.e., one by one, as they become available) often does not produce optimal results from a business perspective.  This important observation is illustrated by an example below.

Fortunately, some commercial inference engines offer special (and powerful) rule-based capability to optimize such allocations.  This capability, sometimes called 'pattern matching,' operates on a set-at-a-time basis, rather than an instance at a time.

Packing Boxes

As an example, suppose that multiple items must be packed in optimal fashion into multiple boxes of a certain size.  Every item has both a volume and a dollar-value.  'Optimal' is defined as follows:

• Try to pack all items into boxes.

• If that proves impossible (e.g., because there are not enough boxes, the items are too bulky, etc.), then pack only the items that will maximize the total dollar value packed in the boxes.

Suppose six items arrive one at a time by conveyor belt.  There are just three boxes.  By coincidence, the first three items off the conveyor belt are very bulky, filling the three boxes completely.  Unfortunately, these first three items are of considerably less total value than the next three items (which might happen to be quite small).  Instance-at-a-time allocation clearly will not produce the best packing results given the goals of optimization.

A better approach is to wait until all six items have arrived via the conveyor belt (or as long as possible, anyway), and then perform the allocation on a set-at-a-time basis in order to achieve the best fit possible.

Specifying Criteria for Best-Fit Decision Points

Specifications for best-fit decision points should encompass the following:

• Best-Fit Goals.  Even though some best-fit problems have only a single goal, the more interesting (and complex) best-fit problems are multi-goal.  At some level, these goals will often conflict.  The box packing example above, for instance, has two best-fit goals -- pack all items vs. maximize total packed item value.  Other examples of best-fit problems and the types of goals they entail include the following.
  1. Rental car allocation at an airport branch of a rental car agency.

     Satisfy all reservations and upgrade rules vs. maximize profits.

  2. Airline rebooking of all passengers on a cancelled flight.

     Select the best flights for customers vs. minimize the company's financial loss.

  3. Medical diagnosis.

     Match the most symptoms of the patient vs. match the most discriminating ones.

• Acceptable Best-Fit Delay.  Generally speaking, optimization with respect to best-fit goals will be better the longer you wait to perform the optimization.  For example, in the box packing example, waiting for all six items to come off the conveyor belt will often produce a better solution than waiting for only three, four or five items.  However, business circumstances generally preclude waiting indefinitely.  For example, suppose the items are perishable and can remain unpacked for no more than 30 minutes.  This critical timing threshold is called the acceptable best-fit delay.

• Best-Fit Rules.  The best-fit solution (as well as any less-than optimal solution) must usually comply with certain basic rules.  These rules can be expressed in declarative fashion.  Examples for the box packing example might include the following.

Rule:  An item may be packed in a box only if the volume of the item is less than or equal to the volume of an available space within the box.

Rule:  A space within a box may be considered available only if each of its dimensions is greater than or equal to the corresponding dimension of the smallest unpacked item in any possible orientation within that space.

• Best-Fit Algorithm.  Generally, someone in the organization must have some knowledge and experience about how to optimize the best-fit allocation.  For example, the most experienced personnel in the shipping department may be able to describe the steps or decision sequence they follow in performing the optimization manually.  Their step-by-step approach will include heuristics (e.g., always pack the most valuable item first) to be applied in some sequence, called the best-fit algorithm.  A commercial inference engine cannot implement rule-based optimization unless such an algorithm is captured and encoded.

Final Note

Best-fit specifications need not always be developed from scratch.  Instead, a more generalized solution for the basic pattern, called a framework, might be available that can be specialized for the problem at hand.  For example, there are all kinds of things in the world that need to be packed, loaded, bundled, or stored -- not just items-into-boxes.  Call this best-fit re-usability.

standard citation for this article: Ronald G. Ross, "Best-Fit Decision Points ~ How They Fit into the Business Rule Approach," Business Rules Journal, Vol. 5, No. 7 (July 2004), URL:  http://www.BRCommunity.com/a2004/b200.html