Problem Analysis and Structure II
Multi-frame problems

Composite Frames
Using only elementary frames means
Decomposing problems such that each subproblem fits one elementary frame
Don’t build repository of experience about problem and solution composition
Building a car is about more than understanding its component parts
We need composite frames

Package Router Problem
See Jackson, M.A. “Problem Analysis and Structure” from where this example is taken (pointer on web site)
A realistic problem
See the problem description on the handout
Package router delivers packages to different bins by scanning bar codes on the packages and routing them accordingly
What frame does this seem to fit?

Frame Diagram
C1 = flip
C2 = read, hit, position of switches
C3 = arrive, package, bin, destination

Recognising sub-problems
Looks like a control problem
M/c must flip switches to ensure correct destination
Switch is flipped when package passes a sensor at bottom of a pipe
However, consideration of the phenomena exposes difficulties

Connection difficulties
Destination read at the source station
Destination no longer available when package passes the sensor
M/c and sensors share only the penomena
SensorOpen and SensorClosed [state]
Pckg causing state change is unknown
We need a dynamic model

Dynamic model
State of pckgs and pipes regarded as a set of queues
Pckg arriving at a sensor above switch is at the head of the queue in the pipe to which sensor is attached
Destinations (read at source station) are attached to pckg objects in this queue model
To flip a switch, m/c consults queue model to identify destination and hence switch setting

Dynamic Model
Use model to answer question: what is the barcoded destination of the package that participated in the most recent hit event in which this particular sensor participated?

Further problem
The switch to be set is determined by the router topology
i.e. the positioning of sensors on pipes, and the pipe and switch layout.
We need a static model here
i.e. a map of the router and its bins
Using the map, m/c can determine the correct route and hence set the switch correctly.

Static Model
Provides necessary information
Which sensors are on which ends of which pipes? Which pipes feed and leave which switches? Which pipe leaves the reading station? Which bins guarded by which sensors?

Information Display
Signalling arrival of package at wrong bin is a Simple Information System Display problem

Composing the Solution
How do we schedule the machines from each sub-problem?
Run the static-model machine to completion first
Run the other machines in parallel synchronised by the read and hit events

Summary
Problems located in real world not computer
Large (realistic) problems can be seen as compositions of small problems
Small problems must be of recognised classes
Problem structure often a parallel composition of subproblems