Package Router Problem
The package router is a system for distributing
packages into destination bins. The packages arrive at a source station,
which is connected to the bins via a series of pipes. A single pipe leaves
the source station. The pipes are linked together by two-position
switches. A switch enables a package sliding down its input pipe to be
directed to either of its two output pipes. There is a unique path from
the source station to any particular bin.
Packages arriving at the source station are scanned by
a reading device which determines a destination bin for the package. The
package is then allowed to slide down the pipe leaving the source station.
The package router must set its switches ahead of each package sliding
through the pipes so that each package is routed to the bin determined for
it by the source station.
After a package's destination has been determined, it
is delayed for a fixed time before being released into the first pipe.
This is done to prevent packages from following one another so closely
that a switch cannot be reset between successive packages when necessary.
However, if a package's destination is the same as that of the package
which preceded it through the source station, it is not delayed, since
there will be no need to reset switches between the two packages.
There will generally be many packages sliding down the
pipes at once. The packages slide at different and unpredictable speeds,
so it is impossible to calculate when a given package will reach a
particular switch. However, the switches contain sensors strategically
placed at their entries and exits to detect the packages.
The sensors are placed in such a way that it is safe
to change a switch setting if and only if no packages are present between
the entry sensor of a switch and either of its exit sensors. The pipes are
bent at the sensor locations in such a way that the sensors are guaranteed
to detect a separation between two packages, no matter how closely they
follow one another.
Due to the unpredictable sliding characteristics of
the packages, it is possible, in spite of the source station delay, that
packages will get so close together that it is not possible to reset a
switch in time to properly route a package. Misrouted packages may be
routed to any bin, but must not cause the misrouting of other packages.
The bins too have sensors located at their entry, and upon arrival of a
misrouted package at a wrong bin, the routing machine is to signal that
package's intended destination bin and the bin it actually reached.