LAWS@IU.AI.SRI.COM (Ken Laws) (04/27/88)
Triangular Scheduling for Depletion-Process Control
Kenneth Laws
SRI International
There exist phenomena in which resource depletion rate is proportional
to the amount of material available. Control of such processes can be
exerted through replenishment of consumable resources or through
manipulation of the proportionality function. I propose an application
of triangular numbers to such control in a simple discrete system.
Consider the ingestion of m&m's. Unless the consumer process employs
appropriate feedback, the supply of these expensive units will be
exhausted before full psychogustatory satisfaction has been achieved.
This side-effect of the well-known greedy algorithm can be overcome
by a stict discipline of triangularization. The steps are as follows:
1) Arrange the units in a triangular pattern, with distribution
of colors optional. Start with one element at the top, then
increase the number in each successive row by one. Any leftover
units may be scheduled for immediate consumption.
2) Queue rows for removal in inverse order of their creation.
A row may be deleted right to left, left to right, or in random
order, but not from the middle outward. The rate of consumption
will depend on numerous parameters, including attentional factors,
but is typically limited by sequential transport and processing--
the so-called Laws bottleneck.
3) A delay of approximately one minute should separate removal of any
two rows. This enhances perception of the immanent depletion crisis,
with possible dynamic replanning to mitigate its effects. The
active agent may wish to increase the delay in inverse proportion
to the number of units remaining, possibly selecting such delays
from the set of triangular numbers.
This simple algorithm admits many obvious variations, such as hierarchical
control systems with triangular arrangements substituting for the rows
(or even units) described above. The demonstrated efficacy of the
technique leads to speculation about related depletion processes --
e.g., peanuts, peppermints, and Chex party mix -- but extension to
these domains has not yet been attempted. There may be difficulties
in transferring the triangular scheduling approach to the real world,
particularly for area-intensive elements such as potato chips.