Search

This paper describes the development and operation of a vehicle scheduling algorithm which has applications to the NASA problem of assigning payloads to space delivery vehicles. The algorithm is based on a discrete, integer-valued, non-serial, dynamic programming solution to the classical problem of developing resource utilization plans with limited resources. The algorithm places special emphasis on incorporating interpayload (precedence) relationships; maintaining optimal alternate schedule definitions (a unique feature of dynamic programming) in the event of contingencies (namely, resource inventory changes) without problem resolution; and, by using a special information storage technique, reducing the computational complexity of solving realistic problems. This information storage technique is demonstrated with a brief example. Reference is made to an operational computer program which solves the problem of assigning payloads to space delivery vehicles.

The "deadlock" problem is a logical problem which may occur in a system in which resources are shared among users. Deadlock is a situation in which two or more jobs cannot be completed because of conflicting resource requirements. In this paper we assume that advance information about future resource requirements of jobs is available. In particular, we assume that jobs are represented as a sequence of "job steps" during which the resource usage remains constant. An algorithm which uses this information to determine whether a request can be granted without causing a deadlock is presented.

It is generally recognized that asynchronous operation of logic networks offers specific advantages over synchronous operation controlled by a central clock when the network is subject to large or widely varying inter-module propagation delays. In this paper we characterize several previously described techniques for achieving asynchronous operation by a single model. Essential to the model is the bi-directional exchange of control information to control a one-directional data flow. A second important concept is that of detecting the completion of logical operations. The model readily generalizes to permit the control of modules that are sequential machines of arbitrary complexity. As a vehicle to demonstrate several characteristics of asynchronous networks, the design of a modular, asynchronous multiplier is described. One of its characteristics, termed "self-steering," entails the use of special symbols on the data paths to control dynamic reconfiguration of the network. Another characteristic, "flow mode" operation, is exemplified by the apparent flow of activity through the network. At, any given time, portions of several independent multiplication processes can be flowing through different portions of the network.

This paper is concerned with the behavior of an adaptive routing system in a large communications network. The adaptive routing algorithm described uses stochastic switching matrices to automatically find and complete the traffic paths through a system. A realistic network and traffic which were derived from military field exercises are used to illustrate the real time behavior of the algorithm. Simulation experiments indicate that adaptive routing techniques can be effective in large communications networks.