| The Deep Space Network (DSN) consists of a set of antennas and support facilities located in California, Australia, and Spain, which communicate with and collect data from spacecraft exploring the solar system. The DSN spacecraft scheduling problem refers to the problem of assigning antennas to a set of spacecraft over a specified period of time, given the view periods of the spacecraft and spacecraft tracking requirements. The problem is complicated by the fact that the view periods frequently overlap, resulting in conflicting requests for assignment.; The DSN spacecraft scheduling problem is formulated as a mixed integer-linear program. In this formulation, the scheduling problem is separated into two subproblems: a continuous variable fixed-order scheduling subproblem and a nonlinear sequencing subproblem. The fixed-order scheduling subproblem is modeled as a linear program, while the sequencing subproblem is modeled as a 0/1 integer program.; A solution to the mixed integer-linear program is developed as an application of Benders decomposition procedure. Benders decomposition is chosen as a research tool because it leaves the continuous and noncontinuous subproblems intact, allowing experimentation by taking advantage of the problem's special structure and by heuristic procedures. Solution of the scheduling model using a commercial mixed integer-linear program is described.; Other solution strategies for the DSN spacecraft scheduling model are discussed. A heuristic algorithm based on the specific characteristics of the DSN spacecraft scheduling model is presented. Computational improvements to the Benders decomposition algorithm are considered. An innovative algorithm is developed to substantially reduce computer execution time. Benders convergence results are presented, and recommended solutions strategies are presented for quickly determining good suboptimal solutions.; An interactive computer program, DSNSCHD, which is based on the mathematical model and solution procedures presented, is described. Computational results are provided using data from an actual DSN 7-day Operations schedule. |
