A vehicle scheduling algorithm using non-serial discrete dynamic programming with space shuttle applications

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.