|Abstract or Summary
- Algorithms capable of automatically drawing Resource Planning
and Management (RPM) network models from standard Linear Programming
data files are developed.
An RPM network is a unique graphical representation that is
capable of representing both the primal and the dual model of a
mathematical programming problem on a same network model. Each
primal decision variable and each dual (Lagrange Multiplier) variable
is represented by a node in an RPM network. Unlike a CPM-PERT
network, an RPM network must be able to include feedback loops, three
different types of nodes, and two types of arrows connecting these
The algorithms presented in this thesis can replace the tedious
task of manually drawing an RPM network by an automated computer
plotting system which includes a node location algorithm and an
arrow routing algorithm.
Five different types of algorithms were investigated for the node
location problem: rectilinear model, directionaly weighted model,
acyclic convergence model, squared distance model, and two-phase model.
The two-phase model, the final choice of algorithm, is based upon the
basic idea of "pairwise interchange" procedure commonly used for
optimizing a facility layout location problem. A special cost
evaluation function is developed to realize the technological
ordering of nodes. The first phase checks the relative locations
of nodes in terms of technological order, while the second phase
evaluates the optimality of the resulting configuration.
The arrow routing algorithm also consists of two phases: a
pin-position ordering model and an open space routing model. The
former deals with the ordering of all arrow connections at a node,
while the latter uses the concept of macro-routing and macro-tracking
to funnel the flows through the open space. The two phases are
treated independently but are used jointly to provide a visually
balanced and easily understood network drawings.
The feasibility of these algorithms was verified by constructing
a computerized RPM Network Designer (RAMNED) on a Control Data
Corporation Computer Cyber-70 Model 73 and a Gerber flatbed plotter.
The program accepts an industry standard input data (IBM's MPS,
CDC's APEX, or OSU's REX) for Linear Programming, and automatically
produces a finished copy of the network on the flat-bed plotter.
The current version of RAMNED is capable of handling up to 70 nodes.
Each node may have up to five inflow and five outflow arrows in addition
to a flow to an objective function. Computational time requirement varied from 7.9 to 126.0 cpu
seconds for a number of problems ranging from 9 to 68 nodes.